Да се докаже

[Гост]

Да се докаже, че
[tex]2^{341} \equiv[/tex]2(mod 341)


[tex]2^{561 } \equiv[/tex]2(mod561)

[ptj]

От малката теорема на Ферма:


[tex]2^{11.31}=31.x+2^{11}=11.y+2^{31}[/tex], където [tex]x,y \in N[/tex].

[tex]31x-11y=2^{31}-2^{11}=2^{11}(2^{10}+1)(2^5+1)(2^5-1)=2^{11}.1025.33.31=2^{11}.5^2.41. 3.11.31[/tex]

Горното равенство е възможно само при [tex]11/x[/tex] и [tex]31/y[/tex].

Тогава [tex]2^{341}=2^{31.11} \equiv 2^{11} \pmod{341} \equiv 2.(1023+1) \pmod{341} \equiv 2 \pmod{341}[/tex]