mod 169

[Apocalyp5e]

Докажете, че ако [tex]a^7 \not\equiv a (mod 13),[/tex] то [tex]a^{78} +1\equiv 0(mod 169).[/tex]

[martin123456]

Aко [tex]a \equiv 0 (mod 13)[/tex]=>[tex]a^7 \equiv 0 \equiv a (mod 13)[/tex]=>[tex]\empty[/tex].
от ойлер: [tex]a^{12} \equiv 1 (mod 13) \Leftrightarrow a^6 \equiv \pm a(mod 13)[/tex]. От условието [tex]a(a^6-1) \not \equiv 0 (mod 13)[/tex]=>[tex]a^6 \not \equiv 1(mod 13)[/tex]=>[tex]a^6 \equiv -1 (mod 13)[/tex].
[tex]\varphi(169)=13.12[/tex]=>[tex]a^{13.12} \equiv 1(mod 169)[/tex]=>[tex]a^{78}=a^{13.6} \equiv \pm 1 (mod 13)[/tex].
Ако допуснем, че [tex]a^{13.6} \equiv 1 (mod 169)[/tex]=>[tex](a^6)^{13} \equiv 1 (mod 13) \Leftrightarrow -1 \equiv 1 (mod 13)[/tex]=>[tex]\empty[/tex].

[Apocalyp5e]

Браво!

[Apocalyp5e]

от ойлер: [tex]a^{12} \equiv 1 (mod 13) \Leftrightarrow a^6 \equiv \pm 1(mod 13)[/tex].

и все пак в общия случай това не винаги е вярно в едната посока.

[martin123456]

не е вярно само ако [tex]a \equiv 0 (mod 13)[/tex]

[Apocalyp5e]

и ако [tex]a^6<13.[/tex] В случая е ясно, че няма такова естествено а, чиято 6-та степен да е под 13 (освен а=1), но ако вместо 13 стоеше нещо друго, хубаво е да се уточни.