Teorija brojeva - deljivost i prosti brojevi - veoma teški zadaci sa rešenjima

Rešenje:
Primetimo da je [tex]11111=41\cdot 271[/tex]. Zato je za svaku cifru [tex]d[/tex] petocifreni broj
[tex]\overline{ddddd}=d\cdot 11111=41d\cdot 271[/tex]
deljiv sa [tex]271[/tex].
Napisani broj ima [tex]37[/tex] cifara, a svaka od njih je jedna od devet cifara od [tex]1[/tex] do [tex]9[/tex]. Kada bi se svaka cifra pojavljivala najviše [tex]4[/tex] puta, broj bi imao najviše [tex]9\cdot 4=36\lt 37[/tex] cifara. Dakle, neka se cifra [tex]d[/tex] pojavljuje bar [tex]5[/tex] puta (Dirihleov princip).
Zaprjan ostavlja pet cifara [tex]d[/tex] i briše sve ostale [tex]32[/tex] cifre. Ostaje broj [tex]\overline{ddddd}[/tex], koji je deljiv sa [tex]271[/tex]. Dakle, ma koji broj Strahil napisao, Zaprjan uvek može da dobije broj deljiv sa [tex]271[/tex].

Rešenje:
Granice. Broj [tex]A[/tex] ima [tex]26[/tex] cifara, pa je
[tex]10^{25}\le p^{13}\lt 10^{26}=100^{13}\Rightarrow p\lt 100[/tex]
Osim toga, [tex]80^{13}=8^{13}\cdot 10^{13}=2^{39}\cdot 10^{13}[/tex], gde je
[tex]2^{39}=\frac{1024^4}{2}\lt \frac{1100^4}{2}=\frac{14641\cdot 10^{8}}{2}\lt 10^{12}[/tex]
Dakle, [tex]80^{13}\lt 10^{25}\le p^{13}[/tex], tj. [tex]p\gt 80[/tex].
Poslednja cifra. Poslednja cifra broja [tex]p^{13}[/tex] zavisi samo od poslednje cifre broja [tex]p[/tex], a poslednje cifre stepena svake cifre ponavljaju se sa periodom [tex]1[/tex], [tex]2[/tex] ili [tex]4[/tex] (na primer, stepeni broja [tex]7[/tex] završavaju se na [tex]7[/tex], [tex]9[/tex], [tex]3[/tex], [tex]1[/tex], a zatim se to ponavlja). Pošto je [tex]13=1+3\cdot 4[/tex], brojevi [tex]p^{13}[/tex] i [tex]p[/tex] završavaju se istom cifrom. Broj [tex]A[/tex] se završava na [tex]9[/tex], pa se i [tex]p[/tex] završava na [tex]9[/tex], a zajedno sa [tex]80\lt p\lt 100[/tex] ostaje [tex]p=89[/tex] ili [tex]p=99[/tex].
Deljivost sa [tex]3[/tex]. Zbir cifara broja [tex]A[/tex] je [tex]107[/tex], što nije deljivo sa [tex]3[/tex], pa [tex]A[/tex] nije deljiv sa [tex]3[/tex]. Ako je [tex]p=99[/tex], onda bi [tex]A=99^{13}[/tex] bio deljiv sa [tex]3[/tex], što je kontradikcija. Dakle, [tex]p=89[/tex].

Rešenje:
Neka je [tex]D=53^m-37^n[/tex]. Brojevi [tex]53^m[/tex] i [tex]37^n[/tex] su stepeni različitih prostih brojeva, pa nisu jednaki i [tex]D\ne 0[/tex].
Po modulu [tex]4[/tex] važi [tex]53\equiv 37\equiv 1[/tex], pa je
[tex]D\equiv 1-1=0\pmod 4[/tex]
Po modulu [tex]9[/tex] važi [tex]53\equiv -1[/tex] i [tex]37\equiv 1[/tex], pa je
[tex]D\equiv (-1)^m-1\pmod 9[/tex]
tj. [tex]D\equiv 0\pmod 9[/tex] za parno [tex]m[/tex] i [tex]D\equiv -2\equiv 7\pmod 9[/tex] za neparno [tex]m[/tex]. Dakle, [tex]D[/tex] je sadržalac broja [tex]4[/tex] različit od nule koji pri deljenju sa [tex]9[/tex] daje ostatak [tex]0[/tex] ili [tex]7[/tex].
Sadržaoci broja [tex]4[/tex] različiti od nule čija je apsolutna vrednost manja od [tex]16[/tex] jesu [tex]\pm 4[/tex], [tex]\pm 8[/tex], [tex]\pm 12[/tex], a po modulu [tex]9[/tex] važi
[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]
Nijedan od ovih ostataka nije [tex]0[/tex] ni [tex]7[/tex], pa je [tex]|D|\ge 16[/tex]. Za [tex]m=n=1[/tex] dobija se [tex]|53-37|=16[/tex], pa je najmanja vrednost [tex]16[/tex].

Rešenje:
Izložioci brojeva [tex]5[/tex] i [tex]2[/tex] u rastavljanju broja [tex]34![/tex] na proste činioce su
[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]
Dakle, [tex]34!=10^7\cdot M[/tex], gde [tex]M[/tex] nije deljiv sa [tex]5[/tex] (pa mu poslednja cifra nije [tex]0[/tex]) i [tex]M[/tex] je deljiv sa [tex]2^{25}[/tex]. Zato se [tex]34![/tex] završava sa tačno sedam nula. U datom zapisu posle [tex]b[/tex] sledi šest nula, pa je [tex]b=0[/tex], a [tex]a[/tex] je poslednja cifra broja [tex]M[/tex].
Pošto [tex]8\mid M[/tex], broj koji čine poslednje tri cifre broja [tex]M[/tex] deljiv je sa [tex]8[/tex]:
[tex]8\mid\overline{35a}=350+a=8\cdot 43+6+a\ \Rightarrow\ 8\mid 6+a\ \Rightarrow\ a=2[/tex]
Dalje, [tex]9\mid 34![/tex], pa je zbir njegovih cifara deljiv sa [tex]9[/tex]. Zbir poznatih cifara (uz [tex]a=2[/tex], [tex]b=0[/tex]) iznosi [tex]141=9\cdot 15+6[/tex], pa je
[tex]c+d\equiv 3\pmod 9,\quad 0\le c+d\le 18\ \Rightarrow\ c+d=3\text{ ili }c+d=12[/tex]
Takođe [tex]11\mid 34![/tex], pa je razlika zbira cifara na neparnim mestima i zbira cifara na parnim mestima (brojeći zdesna, cifra jedinica je na mestu [tex]1[/tex]) deljiva sa [tex]11[/tex]. Poznate cifre daju zbir [tex]80[/tex] na neparnim mestima i [tex]61[/tex] na parnim, a [tex]d[/tex] je na mestu [tex]29[/tex] (neparnom) i [tex]c[/tex] na mestu [tex]30[/tex] (parnom). Zato je
[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{ ili }d-c=-8[/tex]
Brojevi [tex]c+d[/tex] i [tex]d-c[/tex] su iste parnosti (njihov zbir je [tex]2d[/tex]), pa su moguća samo dva slučaja:
[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]
U drugom slučaju [tex]c=10[/tex] nije cifra. Dakle, [tex]a=2[/tex], [tex]b=0[/tex], [tex]c=0[/tex], [tex]d=3[/tex].

Rešenje:
Označimo sa [tex]S(m)[/tex] zbir cifara broja [tex]m[/tex] i neka se [tex]n[/tex] završava sa tačno [tex]k\ge 0[/tex] devetki. Dodavanjem [tex]1[/tex] te devetke postaju nule, a prethodna cifra (koja nije [tex]9[/tex], možda vodeća nula) povećava se za [tex]1[/tex], pa je
[tex]S(n+1)=S(n)+1-9k[/tex]
Ako su oba zbira cifara deljiva sa [tex]7[/tex], onda
[tex]7\mid 9k-1=7k+(2k-1)\ \Rightarrow\ 7\mid 2k-1\ \Rightarrow\ k\in\{4; \,11; \,18; \,\ldots\}[/tex]
Posebno, [tex]n[/tex] se završava sa bar četiri devetke. Za [tex]k=4[/tex] je [tex]n=10000m+9999[/tex], gde se [tex]m\ge 0[/tex] ne završava cifrom [tex]9[/tex], i
[tex]S(n)=S(m)+36,\qquad 7\mid S(m)+36\ \Leftrightarrow\ S(m)\equiv 6\pmod 7[/tex]
Za [tex]0\le m\le 5[/tex] je [tex]S(m)=m\lt 6[/tex], pa je najmanja odgovarajuća vrednost [tex]m=6[/tex], odakle je [tex]n=69999[/tex]. Svaki broj [tex]n[/tex] sa [tex]k\ge 11[/tex] ima bar [tex]11[/tex] cifara i veći je. Provera:
[tex]S(69999)=42=7\cdot 6,\qquad S(70000)=7[/tex]
Dakle, traženi najmanji broj je [tex]n=69999[/tex].

Rešenje:
Neka je [tex]8n+1=a^2[/tex] i [tex]24n+1=b^2[/tex], gde su [tex]a[/tex] i [tex]b[/tex] prirodni brojevi. Tada je
[tex]3a^2-b^2=3(8n+1)-(24n+1)=2[/tex]
Zato je
[tex]8n+3=a^2+2=a^2+\left(3a^2-b^2\right)=4a^2-b^2=(2a-b)(2a+b)[/tex]
Pošto je [tex]8n+3\gt 0[/tex] i [tex]2a+b\gt 0[/tex], važi [tex]2a-b\ge 1[/tex]. Pretpostavimo da je [tex]2a-b=1[/tex], tj. [tex]b=2a-1[/tex]. Zamenom u [tex]3a^2-b^2=2[/tex] dobijamo
[tex]3a^2-(2a-1)^2=2\ \Rightarrow\ a^2-4a+3=0\ \Rightarrow\ a=1\text{ ili }a=3[/tex]
Tada je [tex]8n+1=1[/tex] ili [tex]8n+1=9[/tex], tj. [tex]n=0[/tex] ili [tex]n=1[/tex], što je u suprotnosti sa [tex]n\gt 1[/tex]. Dakle, [tex]2a-b\ge 2[/tex], a takođe i [tex]2a+b\gt 2a-b\ge 2[/tex].
Dakle, [tex]8n+3[/tex] je proizvod dva cela broja veća od [tex]1[/tex], tj. složen je. (Uslov [tex]n\gt 1[/tex] je bitan: za [tex]n=1[/tex] broj [tex]8n+3=11[/tex] je prost.)

Rešenje:
Uzastopnom primenom jednakosti [tex]\left(2^{2^k}-1\right)\left(2^{2^k}+1\right)=2^{2^{k+1}}-1[/tex], počevši od [tex]2^{2^0}-1=1[/tex], dobijamo
[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]
Zato su Fermaovi brojevi po parovima uzajamno prosti: ako je [tex]m\lt n[/tex] i [tex]d[/tex] deli i [tex]F_m[/tex] i [tex]F_n[/tex], onda [tex]d[/tex] deli [tex]F_0F_1\ldots F_{n-1}=F_n-2[/tex] (jedan od činilaca je [tex]F_m[/tex]) i [tex]F_n[/tex], pa [tex]d\mid 2[/tex]; svi [tex]F_n[/tex] su neparni, pa je [tex]d=1[/tex].
Prema tome, NZS brojeva [tex]F_2, F_3, \ldots, F_{1985}[/tex] jednak je njihovom proizvodu, koji ima [tex]1985-1=1984[/tex] činioca. Za [tex]n\ge 2[/tex]
[tex]2^{2^n}=\left(2^4\right)^{2^{n-2}}=16^{2^{n-2}}[/tex]
a svaki stepen broja koji se završava cifrom [tex]6[/tex] završava se cifrom [tex]6[/tex] (jer je [tex]6\cdot 6=36[/tex]). Dakle, [tex]2^{2^n}[/tex] se završava cifrom [tex]6[/tex], a [tex]F_n[/tex] cifrom [tex]7[/tex]; zato se proizvod završava istom cifrom kao [tex]7^{1984}[/tex].
Poslednje cifre brojeva [tex]7^1, 7^2, 7^3, 7^4, \ldots[/tex] su [tex]7; \ 9; \ 3; \ 1[/tex] i ponavljaju se sa periodom [tex]4[/tex]. Pošto je [tex]1984=4\cdot 496[/tex], broj [tex]7^{1984}[/tex] se završava cifrom [tex]1[/tex]. Dakle, cifra jedinica NZS je [tex]1[/tex].

Rešenje:
Označimo taj broj sa [tex]R[/tex]; tada je [tex]9R=10^{2^n}-1[/tex]. Uzastopnom primenom formule [tex]x^2-1=(x-1)(x+1)[/tex] dobijamo
[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]
Dakle, [tex]R=A_0A_1\ldots A_{n-1}[/tex], gde je [tex]A_k=10^{2^k}+1[/tex]. Ovi činioci su po parovima uzajamno prosti. Zaista, neka je [tex]i\lt j[/tex]. Prema istom rastavljanju (sa [tex]j[/tex] umesto [tex]n[/tex]) broj [tex]10^{2^j}-1=9A_0A_1\ldots A_{j-1}[/tex] deljiv je sa [tex]A_i[/tex], pa je
[tex]A_j=\left(10^{2^j}-1\right)+2\equiv 2\pmod{A_i}[/tex]
pa svaki zajednički delilac brojeva [tex]A_i[/tex] i [tex]A_j[/tex] deli [tex]2[/tex]; pošto je [tex]A_i[/tex] neparan, brojevi [tex]A_i[/tex] i [tex]A_j[/tex] su uzajamno prosti.
Svaki broj [tex]A_k\gt 1[/tex] ima prost delilac [tex]p_k[/tex]. Pošto su brojevi [tex]A_k[/tex] po parovima uzajamno prosti, prosti brojevi [tex]p_0, p_1, \ldots, p_{n-1}[/tex] su međusobno različiti i svi dele [tex]R[/tex].
Za svaki podskup skupa [tex]\left\{p_0, p_1, \ldots, p_{n-1}\right\}[/tex] proizvod njegovih elemenata (za prazan podskup on je [tex]1[/tex]) je delilac broja [tex]R[/tex], a zbog jedinstvenosti rastavljanja na proste činioce različiti podskupovi daju različite proizvode. Podskupova ima [tex]2^n[/tex], pa [tex]R[/tex] ima najmanje [tex]2^n[/tex] različitih delilaca.

Rešenje:
Za [tex]N=1[/tex] uzmimo [tex]M=1[/tex] (nije deljiv sa [tex]2[/tex], [tex]3[/tex], [tex]4[/tex]); za [tex]N=2[/tex] uzmimo [tex]M=2[/tex] (nije deljiv sa [tex]3[/tex], [tex]4[/tex], [tex]5[/tex]). Dakle, [tex]N=1[/tex] i [tex]N=2[/tex] su mogući.
Neka je sada [tex]N\ge 3[/tex] i neka je [tex]k[/tex] jedan od brojeva [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex]. Ako [tex]k[/tex] nije stepen prostog broja, onda je [tex]k=uv[/tex] sa uzajamno prostim [tex]u, v\gt 1[/tex] (za [tex]u[/tex] uzmemo pun stepen jednog prostog delioca broja [tex]k[/tex]). Tada je
[tex]u, v\le\frac{k}{2}\le\frac{N+3}{2}\le N[/tex]
pa [tex]u\mid M[/tex] i [tex]v\mid M[/tex], a kako su [tex]u[/tex] i [tex]v[/tex] uzajamno prosti, [tex]k=uv\mid M[/tex], što je kontradikcija. Dakle, svaki od brojeva [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex] je stepen prostog broja.
Jedan od ova tri uzastopna broja deljiv je sa [tex]3[/tex], pa je jednak [tex]3^b[/tex], [tex]b\ge 1[/tex]; bar jedan od njih je paran, pa je stepen broja [tex]2[/tex]. Kad bi [tex]N+1[/tex] i [tex]N+3[/tex] bili parni, bili bi stepeni broja [tex]2[/tex] koji se razlikuju za [tex]2[/tex], tj. [tex]2[/tex] i [tex]4[/tex], odakle je [tex]N=1\lt 3[/tex]. Dakle, [tex]N+2=2^a[/tex], gde je [tex]a\ge 3[/tex] jer je [tex]N+2\ge 5[/tex], a stepen broja [tex]3[/tex] je [tex]N+1[/tex] ili [tex]N+3[/tex]:
[tex]3^b=2^a-1\text{ ili }3^b=2^a+1[/tex]
Ako je [tex]3^b=2^a-1[/tex], onda je [tex]2^a\equiv 1\pmod 3[/tex]; kako je [tex]2\equiv -1\pmod 3[/tex], izložilac [tex]a=2c[/tex] je paran, [tex]c\ge 2[/tex], i
[tex]\left(2^c-1\right)\left(2^c+1\right)=3^b[/tex]
Oba činioca su stepeni broja [tex]3[/tex] koji se razlikuju za [tex]2[/tex], pa su to [tex]1[/tex] i [tex]3[/tex], odakle je [tex]c=1[/tex], što je kontradikcija.
Ako je [tex]3^b=2^a+1[/tex], onda je [tex]3^b\equiv 1\pmod 4[/tex] (jer je [tex]a\ge 3[/tex]); kako je [tex]3\equiv -1\pmod 4[/tex], izložilac [tex]b=2d[/tex] je paran i
[tex]\left(3^d-1\right)\left(3^d+1\right)=2^a[/tex]
Oba činioca su stepeni broja [tex]2[/tex] koji se razlikuju za [tex]2[/tex], pa su to [tex]2[/tex] i [tex]4[/tex]. Odatle je [tex]d=1[/tex], [tex]b=2[/tex], [tex]a=3[/tex] i [tex]N=2^3-2=6[/tex]. Provera: [tex]M=60[/tex] je deljiv sa [tex]1; \ 2; \ \ldots; \ 6[/tex], ali nije deljiv sa [tex]7[/tex], [tex]8[/tex], [tex]9[/tex]. Dakle,
[tex]N\in\{1; \,2; \,6\}[/tex]

Rešenje:
Neka su prosti brojevi [tex]a_k=a+kd[/tex], [tex]0\le k\le 14[/tex], gde je [tex]d\gt 0[/tex].
Ključno zapažanje: ako prost broj [tex]p[/tex] ne deli [tex]d[/tex], onda su ostaci pri deljenju sa [tex]p[/tex] bilo kojih [tex]p[/tex] uzastopnih članova [tex]a_i, a_{i+1}, \ldots, a_{i+p-1}[/tex] međusobno različiti, jer
[tex]a_j-a_k=(j-k)d,\quad 0\lt |j-k|\lt p\ \Rightarrow\ p\nmid (j-k)d[/tex]
Dakle, tih [tex]p[/tex] članova daju svih [tex]p[/tex] mogućih ostataka; jedan od njih je deljiv sa [tex]p[/tex], a pošto je prost, jednak je [tex]p[/tex].
Korak [tex]1[/tex]: [tex]p\in\{2; \,3; \,5; \,7\}[/tex]. Ako [tex]p\nmid d[/tex], primenimo zapažanje na blokove [tex]a_0, \ldots, a_{p-1}[/tex] i [tex]a_p, \ldots, a_{2p-1}[/tex] (postoje, jer je [tex]2p-1\le 13[/tex]). Svaki blok sadrži član jednak [tex]p[/tex], pa su dva člana sa različitim indeksima jednaka, što je nemoguće u strogo rastućem nizu. Dakle, [tex]2[/tex], [tex]3[/tex], [tex]5[/tex] i [tex]7[/tex] dele [tex]d[/tex], tj. [tex]210\mid d[/tex] i [tex]d\ge 210[/tex].
Korak [tex]2[/tex]: [tex]p\in\{11; \,13\}[/tex]. Ako [tex]p\nmid d[/tex], neki od članova [tex]a_0, \ldots, a_{p-1}[/tex] jednak je [tex]p[/tex]. Za [tex]k\ge 1[/tex] je [tex]a_k\ge 2+210\gt 13[/tex], pa je to [tex]a_0=p[/tex]. Ali tada je član
[tex]a_p=p+pd=p(1+d)[/tex]
(postoji, jer je [tex]p\le 13\lt 14[/tex]) deljiv sa [tex]p[/tex] i veći od [tex]p[/tex], pa nije prost, što je kontradikcija. Dakle, [tex]11\mid d[/tex] i [tex]13\mid d[/tex]. Prema tome, [tex]d[/tex] je deljiv sa
[tex]2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13=30030[/tex]
pa je [tex]d\ge 30030\gt 30000[/tex].

Rešenje:
Koristimo malu Fermaovu teoremu: [tex]5^r\equiv 5\pmod r[/tex] za svaki prost broj [tex]r[/tex]. Uslov je simetričan po [tex]p[/tex] i [tex]q[/tex].
Slučaj [tex]1[/tex]: [tex]p=5[/tex]. Ako je [tex]q=5[/tex], onda [tex]25\mid 2\cdot 5^5[/tex], pa je [tex](5; 5)[/tex] rešenje. Ako je [tex]q\ne 5[/tex], deljivost sa [tex]5[/tex] je ispunjena, a [tex]5[/tex] i [tex]q[/tex] su uzajamno prosti, pa treba da važi [tex]q\mid 5^5+5^q[/tex]. Kako je [tex]5^q\equiv 5\pmod q[/tex], to znači
[tex]q\mid 5^5+5=3130=2\cdot 5\cdot 313[/tex]
pa je [tex]q=2[/tex] ili [tex]q=313[/tex] (broj [tex]313[/tex] je prost). Obe vrednosti odgovaraju: [tex]5^5+5^2=3150=10\cdot 315[/tex], a [tex]5^5+5^{313}[/tex] je deljiv sa [tex]5[/tex] i, pošto je [tex]5^5+5^{313}\equiv 3130\equiv 0\pmod{313}[/tex], i sa [tex]313[/tex]. Dobijamo [tex](5; 2)[/tex], [tex](5; 313)[/tex] i, zbog simetrije, [tex](2; 5)[/tex], [tex](313; 5)[/tex].
Slučaj [tex]2[/tex]: [tex]p=2[/tex], [tex]q\ne 5[/tex]. Zbir [tex]5^2+5^q[/tex] je paran, a po modulu [tex]q[/tex]
[tex]5^2+5^q\equiv 25+5=30\pmod q\ \Rightarrow\ q\mid 30[/tex]
pa je [tex]q\in\{2; \,3; \,5\}[/tex], tj. [tex]q=2[/tex] ili [tex]q=3[/tex]. Za [tex]q=2[/tex]: [tex]4\nmid 50[/tex], ne odgovara. Za [tex]q=3[/tex]: [tex]5^2+5^3=150=6\cdot 25[/tex], pa su [tex](2; 3)[/tex] i, zbog simetrije, [tex](3; 2)[/tex] rešenja.
Slučaj [tex]3[/tex]: [tex]p, q\notin\{2; \,5\}[/tex]. Iz [tex]p\mid 5^p+5^q[/tex] i [tex]5^p\equiv 5\pmod p[/tex] sledi [tex]p\mid 5\left(5^{q-1}+1\right)[/tex], a pošto je [tex]p\ne 5[/tex], važi [tex]p\mid 5^{q-1}+1[/tex]. Analogno, [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]
Neka je [tex]d[/tex] najmanji prirodan broj za koji je [tex]5^d\equiv 1\pmod p[/tex]; tada je [tex]5^k\equiv 1\pmod p[/tex] tačno kada [tex]d\mid k[/tex]. Važi [tex]d\mid p-1[/tex] (po Fermaovoj teoremi), [tex]d\mid 2(q-1)[/tex] (jer je [tex]5^{2(q-1)}\equiv 1[/tex]) i [tex]d\nmid q-1[/tex] (jer je [tex]5^{q-1}\equiv -1\not\equiv 1[/tex], pošto je [tex]p\gt 2[/tex]).
Neka je [tex]2^s[/tex] najveći stepen broja [tex]2[/tex] koji deli [tex]q-1[/tex] i neka je [tex]d=2^t d'[/tex] sa neparnim [tex]d'[/tex]. Iz [tex]d\mid 2(q-1)[/tex] sledi [tex]d'\mid q-1[/tex] i [tex]t\le s+1[/tex]; ako je [tex]t\le s[/tex], onda [tex]d\mid q-1[/tex], što nije tačno. Dakle, [tex]t=s+1[/tex], a pošto [tex]d\mid p-1[/tex], važi [tex]2^{s+1}\mid p-1[/tex]: izložilac broja [tex]2[/tex] u [tex]p-1[/tex] veći je nego u [tex]q-1[/tex].
Zamenom uloga [tex]p[/tex] i [tex]q[/tex] dobijamo da je izložilac broja [tex]2[/tex] u [tex]q-1[/tex] veći nego u [tex]p-1[/tex], što je kontradikcija. Dakle, u ovom slučaju nema rešenja (uključujući i [tex]p=q[/tex]). Sva rešenja su:
[tex](2; 3),\ (3; 2),\ (2; 5),\ (5; 2),\ (5; 5),\ (5; 313),\ (313; 5)[/tex]