Теория чисел: делимость и простые числа - очень сложные задачи с решениями

Решение:
Заметим, что [tex]11111=41\cdot 271[/tex]. Поэтому для любой цифры [tex]d[/tex] пятизначное число
[tex]\overline{ddddd}=d\cdot 11111=41d\cdot 271[/tex]
кратно [tex]271[/tex].
Написанное число содержит [tex]37[/tex] цифр, каждая из которых — одна из девяти цифр от [tex]1[/tex] до [tex]9[/tex]. Если бы каждая цифра встречалась не более [tex]4[/tex] раз, в числе было бы не более [tex]9\cdot 4=36\lt 37[/tex] цифр. Следовательно, некоторая цифра [tex]d[/tex] встречается не менее [tex]5[/tex] раз (принцип Дирихле).
Запрян оставляет пять цифр [tex]d[/tex] и стирает все остальные [tex]32[/tex] цифры. Остаётся число [tex]\overline{ddddd}[/tex], которое делится на [tex]271[/tex]. Итак, какое бы число ни написал Страхил, Запрян всегда может получить число, кратное [tex]271[/tex].

Решение:
Оценки. Число [tex]A[/tex] имеет [tex]26[/tex] цифр, поэтому
[tex]10^{25}\le p^{13}\lt 10^{26}=100^{13}\Rightarrow p\lt 100[/tex]
Кроме того, [tex]80^{13}=8^{13}\cdot 10^{13}=2^{39}\cdot 10^{13}[/tex], где
[tex]2^{39}=\frac{1024^4}{2}\lt \frac{1100^4}{2}=\frac{14641\cdot 10^{8}}{2}\lt 10^{12}[/tex]
Следовательно, [tex]80^{13}\lt 10^{25}\le p^{13}[/tex], т.е. [tex]p\gt 80[/tex].
Последняя цифра. Последняя цифра числа [tex]p^{13}[/tex] зависит только от последней цифры [tex]p[/tex], а последние цифры степеней любой цифры повторяются с периодом [tex]1[/tex], [tex]2[/tex] или [tex]4[/tex] (например, степени [tex]7[/tex] оканчиваются на [tex]7[/tex], [tex]9[/tex], [tex]3[/tex], [tex]1[/tex], а затем это повторяется). Так как [tex]13=1+3\cdot 4[/tex], числа [tex]p^{13}[/tex] и [tex]p[/tex] оканчиваются одной и той же цифрой. Число [tex]A[/tex] оканчивается на [tex]9[/tex], значит, и [tex]p[/tex] оканчивается на [tex]9[/tex], и вместе с [tex]80\lt p\lt 100[/tex] остаются [tex]p=89[/tex] или [tex]p=99[/tex].
Делимость на [tex]3[/tex]. Сумма цифр числа [tex]A[/tex] равна [tex]107[/tex] и не делится на [tex]3[/tex], поэтому [tex]A[/tex] не делится на [tex]3[/tex]. Если [tex]p=99[/tex], то [tex]A=99^{13}[/tex] делилось бы на [tex]3[/tex] — противоречие. Следовательно, [tex]p=89[/tex].

Решение:
Пусть [tex]D=53^m-37^n[/tex]. Числа [tex]53^m[/tex] и [tex]37^n[/tex] — степени различных простых чисел, поэтому они не равны и [tex]D\ne 0[/tex].
По модулю [tex]4[/tex] имеем [tex]53\equiv 37\equiv 1[/tex], поэтому
[tex]D\equiv 1-1=0\pmod 4[/tex]
По модулю [tex]9[/tex] имеем [tex]53\equiv -1[/tex] и [tex]37\equiv 1[/tex], поэтому
[tex]D\equiv (-1)^m-1\pmod 9[/tex]
т.е. [tex]D\equiv 0\pmod 9[/tex] при чётном [tex]m[/tex] и [tex]D\equiv -2\equiv 7\pmod 9[/tex] при нечётном [tex]m[/tex]. Итак, [tex]D[/tex] — ненулевое число, кратное [tex]4[/tex], которое при делении на [tex]9[/tex] даёт остаток [tex]0[/tex] или [tex]7[/tex].
Ненулевые числа, кратные [tex]4[/tex], с модулем меньше [tex]16[/tex] — это [tex]\pm 4[/tex], [tex]\pm 8[/tex], [tex]\pm 12[/tex], и по модулю [tex]9[/tex]
[tex]4\equiv 4,\quad -4\equiv 5,\quad 8\equiv 8,\quad -8\equiv 1,\quad 12\equiv 3,\quad -12\equiv 6[/tex]
Ни один из этих остатков не равен [tex]0[/tex] или [tex]7[/tex], поэтому [tex]|D|\ge 16[/tex]. При [tex]m=n=1[/tex] получаем [tex]|53-37|=16[/tex], значит, наименьшее значение равно [tex]16[/tex].

Решение:
Показатели степеней [tex]5[/tex] и [tex]2[/tex] в разложении [tex]34![/tex] на простые множители равны
[tex]\left\lfloor\frac{34}{5}\right\rfloor+\left\lfloor\frac{34}{25}\right\rfloor=6+1=7[/tex]
[tex]\left\lfloor\frac{34}{2}\right\rfloor+\left\lfloor\frac{34}{4}\right\rfloor+\left\lfloor\frac{34}{8}\right\rfloor+\left\lfloor\frac{34}{16}\right\rfloor+\left\lfloor\frac{34}{32}\right\rfloor=17+8+4+2+1=32[/tex]
Следовательно, [tex]34!=10^7\cdot M[/tex], где [tex]M[/tex] не делится на [tex]5[/tex] (значит, его последняя цифра не [tex]0[/tex]) и [tex]M[/tex] делится на [tex]2^{25}[/tex]. Значит, [tex]34![/tex] оканчивается ровно семью нулями. В данной записи за [tex]b[/tex] следуют шесть нулей, поэтому [tex]b=0[/tex], а [tex]a[/tex] — последняя цифра числа [tex]M[/tex].
Так как [tex]8\mid M[/tex], число, образованное тремя последними цифрами [tex]M[/tex], делится на [tex]8[/tex]:
[tex]8\mid\overline{35a}=350+a=8\cdot 43+6+a\ \Rightarrow\ 8\mid 6+a\ \Rightarrow\ a=2[/tex]
Далее, [tex]9\mid 34![/tex], поэтому сумма его цифр делится на [tex]9[/tex]. Сумма известных цифр (при [tex]a=2[/tex], [tex]b=0[/tex]) равна [tex]141=9\cdot 15+6[/tex], следовательно,
[tex]c+d\equiv 3\pmod 9,\quad 0\le c+d\le 18\ \Rightarrow\ c+d=3\text{ или }c+d=12[/tex]
Также [tex]11\mid 34![/tex], поэтому разность суммы цифр на нечётных местах и суммы цифр на чётных местах (считая справа, цифра единиц стоит на месте [tex]1[/tex]) делится на [tex]11[/tex]. Известные цифры дают сумму [tex]80[/tex] на нечётных местах и [tex]61[/tex] на чётных, а [tex]d[/tex] стоит на месте [tex]29[/tex] (нечётном) и [tex]c[/tex] — на месте [tex]30[/tex] (чётном). Следовательно,
[tex]11\mid (80+d)-(61+c)=19+d-c\ \Rightarrow\ d-c\equiv 3\pmod{11}[/tex]
[tex]-9\le d-c\le 9\ \Rightarrow\ d-c=3\text{ или }d-c=-8[/tex]
Числа [tex]c+d[/tex] и [tex]d-c[/tex] одной чётности (их сумма равна [tex]2d[/tex]), поэтому возможны только два случая:
[tex]\begin{cases}c+d=3\\ d-c=3\end{cases}\Rightarrow\ c=0,\ d=3[/tex]
[tex]\begin{cases}c+d=12\\ d-c=-8\end{cases}\Rightarrow\ c=10,\ d=2[/tex]
Во втором случае [tex]c=10[/tex] не является цифрой. Следовательно, [tex]a=2[/tex], [tex]b=0[/tex], [tex]c=0[/tex], [tex]d=3[/tex].

Решение:
Обозначим через [tex]S(m)[/tex] сумму цифр числа [tex]m[/tex], и пусть [tex]n[/tex] оканчивается ровно на [tex]k\ge 0[/tex] девяток. При прибавлении [tex]1[/tex] эти девятки превращаются в нули, а предшествующая цифра (не равная [tex]9[/tex], возможно, ведущий нуль) увеличивается на [tex]1[/tex], поэтому
[tex]S(n+1)=S(n)+1-9k[/tex]
Если обе суммы цифр делятся на [tex]7[/tex], то
[tex]7\mid 9k-1=7k+(2k-1)\ \Rightarrow\ 7\mid 2k-1\ \Rightarrow\ k\in\{4; \,11; \,18; \,\ldots\}[/tex]
В частности, [tex]n[/tex] оканчивается по крайней мере четырьмя девятками. При [tex]k=4[/tex] имеем [tex]n=10000m+9999[/tex], где [tex]m\ge 0[/tex] не оканчивается на [tex]9[/tex], и
[tex]S(n)=S(m)+36,\qquad 7\mid S(m)+36\ \Leftrightarrow\ S(m)\equiv 6\pmod 7[/tex]
При [tex]0\le m\le 5[/tex] имеем [tex]S(m)=m\lt 6[/tex], поэтому наименьшее подходящее значение [tex]m=6[/tex], откуда [tex]n=69999[/tex]. Любое [tex]n[/tex] с [tex]k\ge 11[/tex] имеет не менее [tex]11[/tex] цифр и больше этого числа. Проверка:
[tex]S(69999)=42=7\cdot 6,\qquad S(70000)=7[/tex]
Следовательно, искомое наименьшее число [tex]n=69999[/tex].

Решение:
Пусть [tex]8n+1=a^2[/tex] и [tex]24n+1=b^2[/tex], где [tex]a[/tex] и [tex]b[/tex] — натуральные числа. Тогда
[tex]3a^2-b^2=3(8n+1)-(24n+1)=2[/tex]
Следовательно,
[tex]8n+3=a^2+2=a^2+\left(3a^2-b^2\right)=4a^2-b^2=(2a-b)(2a+b)[/tex]
Так как [tex]8n+3\gt 0[/tex] и [tex]2a+b\gt 0[/tex], то [tex]2a-b\ge 1[/tex]. Предположим, что [tex]2a-b=1[/tex], т.е. [tex]b=2a-1[/tex]. Подставим в [tex]3a^2-b^2=2[/tex]:
[tex]3a^2-(2a-1)^2=2\ \Rightarrow\ a^2-4a+3=0\ \Rightarrow\ a=1\text{ или }a=3[/tex]
Тогда [tex]8n+1=1[/tex] или [tex]8n+1=9[/tex], т.е. [tex]n=0[/tex] или [tex]n=1[/tex], что противоречит условию [tex]n\gt 1[/tex]. Следовательно, [tex]2a-b\ge 2[/tex], а также [tex]2a+b\gt 2a-b\ge 2[/tex].
Значит, [tex]8n+3[/tex] — произведение двух целых чисел, больших [tex]1[/tex], т.е. оно составное. (Условие [tex]n\gt 1[/tex] существенно: при [tex]n=1[/tex] число [tex]8n+3=11[/tex] простое.)

Решение:
Последовательно применяя [tex]\left(2^{2^k}-1\right)\left(2^{2^k}+1\right)=2^{2^{k+1}}-1[/tex] и учитывая, что [tex]2^{2^0}-1=1[/tex], получаем
[tex]F_0F_1\ldots F_{n-1}=\left(2^{2^0}-1\right)F_0F_1\ldots F_{n-1}=2^{2^n}-1=F_n-2[/tex]
Следовательно, числа Ферма попарно взаимно просты: если [tex]m\lt n[/tex] и [tex]d[/tex] делит [tex]F_m[/tex] и [tex]F_n[/tex], то [tex]d[/tex] делит [tex]F_0F_1\ldots F_{n-1}=F_n-2[/tex] (один из множителей равен [tex]F_m[/tex]) и [tex]F_n[/tex], значит, [tex]d\mid 2[/tex]; все [tex]F_n[/tex] нечётны, поэтому [tex]d=1[/tex].
Поэтому НОК чисел [tex]F_2, F_3, \ldots, F_{1985}[/tex] равно их произведению, в котором [tex]1985-1=1984[/tex] множителя. При [tex]n\ge 2[/tex]
[tex]2^{2^n}=\left(2^4\right)^{2^{n-2}}=16^{2^{n-2}}[/tex]
а любая степень числа, оканчивающегося на [tex]6[/tex], оканчивается на [tex]6[/tex] (так как [tex]6\cdot 6=36[/tex]). Значит, [tex]2^{2^n}[/tex] оканчивается на [tex]6[/tex], а [tex]F_n[/tex] — на [tex]7[/tex]; поэтому произведение оканчивается той же цифрой, что и [tex]7^{1984}[/tex].
Последние цифры чисел [tex]7^1, 7^2, 7^3, 7^4, \ldots[/tex] равны [tex]7; \ 9; \ 3; \ 1[/tex] и повторяются с периодом [tex]4[/tex]. Так как [tex]1984=4\cdot 496[/tex], число [tex]7^{1984}[/tex] оканчивается на [tex]1[/tex]. Значит, последняя цифра НОК равна [tex]1[/tex].

Решение:
Обозначим число через [tex]R[/tex]; тогда [tex]9R=10^{2^n}-1[/tex]. Многократно применяя [tex]x^2-1=(x-1)(x+1)[/tex], получаем
[tex]10^{2^n}-1=\left(10^{2^{n-1}}-1\right)\left(10^{2^{n-1}}+1\right)=\ldots[/tex]
[tex]\ldots=(10-1)(10+1)\left(10^2+1\right)\left(10^4+1\right)\ldots\left(10^{2^{n-1}}+1\right)[/tex]
Значит, [tex]R=A_0A_1\ldots A_{n-1}[/tex], где [tex]A_k=10^{2^k}+1[/tex]. Эти множители попарно взаимно просты. Действительно, пусть [tex]i\lt j[/tex]. По тому же разложению (с [tex]j[/tex] вместо [tex]n[/tex]) число [tex]10^{2^j}-1=9A_0A_1\ldots A_{j-1}[/tex] делится на [tex]A_i[/tex], поэтому
[tex]A_j=\left(10^{2^j}-1\right)+2\equiv 2\pmod{A_i}[/tex]
так что любой общий делитель [tex]A_i[/tex] и [tex]A_j[/tex] делит [tex]2[/tex]; поскольку [tex]A_i[/tex] нечётно, числа [tex]A_i[/tex] и [tex]A_j[/tex] взаимно просты.
Каждое [tex]A_k\gt 1[/tex] имеет простой делитель [tex]p_k[/tex]. Так как числа [tex]A_k[/tex] попарно взаимно просты, простые числа [tex]p_0, p_1, \ldots, p_{n-1}[/tex] попарно различны, и все они делят [tex]R[/tex].
Для каждого подмножества множества [tex]\left\{p_0, p_1, \ldots, p_{n-1}\right\}[/tex] произведение его элементов (для пустого подмножества оно равно [tex]1[/tex]) является делителем [tex]R[/tex], а в силу единственности разложения на простые множители разные подмножества дают разные произведения. Подмножеств [tex]2^n[/tex], поэтому [tex]R[/tex] имеет не менее [tex]2^n[/tex] различных делителей.

Решение:
При [tex]N=1[/tex] возьмём [tex]M=1[/tex] (не делится на [tex]2[/tex], [tex]3[/tex], [tex]4[/tex]); при [tex]N=2[/tex] возьмём [tex]M=2[/tex] (не делится на [tex]3[/tex], [tex]4[/tex], [tex]5[/tex]). Значит, [tex]N=1[/tex] и [tex]N=2[/tex] возможны.
Пусть теперь [tex]N\ge 3[/tex] и [tex]k[/tex] — одно из чисел [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex]. Если [tex]k[/tex] не является степенью простого числа, то [tex]k=uv[/tex] с взаимно простыми [tex]u, v\gt 1[/tex] (в качестве [tex]u[/tex] возьмём полную степень одного простого делителя [tex]k[/tex]). Тогда
[tex]u, v\le\frac{k}{2}\le\frac{N+3}{2}\le N[/tex]
поэтому [tex]u\mid M[/tex] и [tex]v\mid M[/tex], а так как [tex]u[/tex] и [tex]v[/tex] взаимно просты, [tex]k=uv\mid M[/tex] — противоречие. Следовательно, каждое из чисел [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex] — степень простого числа.
Одно из этих трёх последовательных чисел делится на [tex]3[/tex], значит, оно равно [tex]3^b[/tex], [tex]b\ge 1[/tex]; хотя бы одно из них чётно, значит, оно является степенью [tex]2[/tex]. Если бы [tex]N+1[/tex] и [tex]N+3[/tex] были чётными, они были бы степенями [tex]2[/tex], отличающимися на [tex]2[/tex], т.е. [tex]2[/tex] и [tex]4[/tex], откуда [tex]N=1\lt 3[/tex]. Следовательно, [tex]N+2=2^a[/tex], где [tex]a\ge 3[/tex], так как [tex]N+2\ge 5[/tex], а степенью [tex]3[/tex] является [tex]N+1[/tex] или [tex]N+3[/tex]:
[tex]3^b=2^a-1\text{ или }3^b=2^a+1[/tex]
Если [tex]3^b=2^a-1[/tex], то [tex]2^a\equiv 1\pmod 3[/tex]; так как [tex]2\equiv -1\pmod 3[/tex], показатель [tex]a=2c[/tex] чётный, [tex]c\ge 2[/tex], и
[tex]\left(2^c-1\right)\left(2^c+1\right)=3^b[/tex]
Оба множителя — степени [tex]3[/tex], отличающиеся на [tex]2[/tex], значит, это [tex]1[/tex] и [tex]3[/tex], откуда [tex]c=1[/tex] — противоречие.
Если [tex]3^b=2^a+1[/tex], то [tex]3^b\equiv 1\pmod 4[/tex] (так как [tex]a\ge 3[/tex]); поскольку [tex]3\equiv -1\pmod 4[/tex], показатель [tex]b=2d[/tex] чётный и
[tex]\left(3^d-1\right)\left(3^d+1\right)=2^a[/tex]
Оба множителя — степени [tex]2[/tex], отличающиеся на [tex]2[/tex], значит, это [tex]2[/tex] и [tex]4[/tex]. Отсюда [tex]d=1[/tex], [tex]b=2[/tex], [tex]a=3[/tex] и [tex]N=2^3-2=6[/tex]. Проверка: [tex]M=60[/tex] делится на [tex]1; \ 2; \ \ldots; \ 6[/tex], но не делится на [tex]7[/tex], [tex]8[/tex], [tex]9[/tex]. Следовательно,
[tex]N\in\{1; \,2; \,6\}[/tex]

Решение:
Пусть простые числа равны [tex]a_k=a+kd[/tex], [tex]0\le k\le 14[/tex], где [tex]d\gt 0[/tex].
Ключевое наблюдение: если простое число [tex]p[/tex] не делит [tex]d[/tex], то любые [tex]p[/tex] последовательных членов [tex]a_i, a_{i+1}, \ldots, a_{i+p-1}[/tex] дают попарно различные остатки по модулю [tex]p[/tex], так как
[tex]a_j-a_k=(j-k)d,\quad 0\lt |j-k|\lt p\ \Rightarrow\ p\nmid (j-k)d[/tex]
Значит, эти [tex]p[/tex] членов дают все [tex]p[/tex] возможных остатков; один из них делится на [tex]p[/tex], и так как он простой, он равен [tex]p[/tex].
Шаг [tex]1[/tex]: [tex]p\in\{2; \,3; \,5; \,7\}[/tex]. Если [tex]p\nmid d[/tex], применим наблюдение к блокам [tex]a_0, \ldots, a_{p-1}[/tex] и [tex]a_p, \ldots, a_{2p-1}[/tex] (они существуют, так как [tex]2p-1\le 13[/tex]). Каждый блок содержит член, равный [tex]p[/tex], значит, два члена с разными номерами равны, что невозможно в строго возрастающей прогрессии. Следовательно, [tex]2[/tex], [tex]3[/tex], [tex]5[/tex] и [tex]7[/tex] делят [tex]d[/tex], т.е. [tex]210\mid d[/tex] и [tex]d\ge 210[/tex].
Шаг [tex]2[/tex]: [tex]p\in\{11; \,13\}[/tex]. Если [tex]p\nmid d[/tex], то один из членов [tex]a_0, \ldots, a_{p-1}[/tex] равен [tex]p[/tex]. При [tex]k\ge 1[/tex] имеем [tex]a_k\ge 2+210\gt 13[/tex], поэтому это [tex]a_0=p[/tex]. Но тогда член
[tex]a_p=p+pd=p(1+d)[/tex]
(он существует, так как [tex]p\le 13\lt 14[/tex]) делится на [tex]p[/tex] и больше [tex]p[/tex], значит, не является простым — противоречие. Итак, [tex]11\mid d[/tex] и [tex]13\mid d[/tex]. Следовательно, [tex]d[/tex] делится на
[tex]2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13=30030[/tex]
и потому [tex]d\ge 30030\gt 30000[/tex].

Решение:
Воспользуемся малой теоремой Ферма: [tex]5^r\equiv 5\pmod r[/tex] для любого простого [tex]r[/tex]. Условие симметрично относительно [tex]p[/tex] и [tex]q[/tex].
Случай [tex]1[/tex]: [tex]p=5[/tex]. Если [tex]q=5[/tex], то [tex]25\mid 2\cdot 5^5[/tex], значит, [tex](5; 5)[/tex] — решение. Если [tex]q\ne 5[/tex], то делимость на [tex]5[/tex] выполнена, а [tex]5[/tex] и [tex]q[/tex] взаимно просты, поэтому нужно [tex]q\mid 5^5+5^q[/tex]. Так как [tex]5^q\equiv 5\pmod q[/tex], это означает
[tex]q\mid 5^5+5=3130=2\cdot 5\cdot 313[/tex]
значит, [tex]q=2[/tex] или [tex]q=313[/tex] (число [tex]313[/tex] простое). Оба значения подходят: [tex]5^5+5^2=3150=10\cdot 315[/tex], а [tex]5^5+5^{313}[/tex] делится на [tex]5[/tex] и, так как [tex]5^5+5^{313}\equiv 3130\equiv 0\pmod{313}[/tex], также на [tex]313[/tex]. Получаем [tex](5; 2)[/tex], [tex](5; 313)[/tex] и по симметрии [tex](2; 5)[/tex], [tex](313; 5)[/tex].
Случай [tex]2[/tex]: [tex]p=2[/tex], [tex]q\ne 5[/tex]. Сумма [tex]5^2+5^q[/tex] чётна, а по модулю [tex]q[/tex]
[tex]5^2+5^q\equiv 25+5=30\pmod q\ \Rightarrow\ q\mid 30[/tex]
значит, [tex]q\in\{2; \,3; \,5\}[/tex], т.е. [tex]q=2[/tex] или [tex]q=3[/tex]. При [tex]q=2[/tex]: [tex]4\nmid 50[/tex] — не подходит. При [tex]q=3[/tex]: [tex]5^2+5^3=150=6\cdot 25[/tex], поэтому [tex](2; 3)[/tex] и по симметрии [tex](3; 2)[/tex] — решения.
Случай [tex]3[/tex]: [tex]p, q\notin\{2; \,5\}[/tex]. Из [tex]p\mid 5^p+5^q[/tex] и [tex]5^p\equiv 5\pmod p[/tex] следует [tex]p\mid 5\left(5^{q-1}+1\right)[/tex], а так как [tex]p\ne 5[/tex], то [tex]p\mid 5^{q-1}+1[/tex]. Аналогично [tex]q\mid 5^{p-1}+1[/tex]:
[tex]5^{q-1}\equiv -1\pmod p,\qquad 5^{p-1}\equiv -1\pmod q[/tex]
Пусть [tex]d[/tex] — наименьшее натуральное число, для которого [tex]5^d\equiv 1\pmod p[/tex]; тогда [tex]5^k\equiv 1\pmod p[/tex] в точности тогда, когда [tex]d\mid k[/tex]. Имеем [tex]d\mid p-1[/tex] (по теореме Ферма), [tex]d\mid 2(q-1)[/tex] (так как [tex]5^{2(q-1)}\equiv 1[/tex]) и [tex]d\nmid q-1[/tex] (так как [tex]5^{q-1}\equiv -1\not\equiv 1[/tex] при [tex]p\gt 2[/tex]).
Пусть [tex]2^s[/tex] — наибольшая степень [tex]2[/tex], делящая [tex]q-1[/tex], и [tex]d=2^t d'[/tex] с нечётным [tex]d'[/tex]. Из [tex]d\mid 2(q-1)[/tex] получаем [tex]d'\mid q-1[/tex] и [tex]t\le s+1[/tex]; если [tex]t\le s[/tex], то [tex]d\mid q-1[/tex], что неверно. Значит, [tex]t=s+1[/tex], и так как [tex]d\mid p-1[/tex], то [tex]2^{s+1}\mid p-1[/tex]: показатель [tex]2[/tex] в [tex]p-1[/tex] больше, чем в [tex]q-1[/tex].
Поменяв ролями [tex]p[/tex] и [tex]q[/tex], получаем, что показатель [tex]2[/tex] в [tex]q-1[/tex] больше, чем в [tex]p-1[/tex] — противоречие. Значит, в этом случае решений нет (в том числе при [tex]p=q[/tex]). Все решения:
[tex](2; 3),\ (3; 2),\ (2; 5),\ (5; 2),\ (5; 5),\ (5; 313),\ (313; 5)[/tex]