Теория на числата - делимост и прости числа - много трудни задачи с решения

Решение:
Забелязваме, че [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]