Теория чисел, a^{20} = 1 (mod 100)

[Trotil]

Можно как-то доказать, что если $(100,a)=1$, то $a^{20} \equiv 1 \mod 100$ ?

$\phi(100)=40$, этого недостаточно для доказательства.

[Xaositect]

Перебором точно можно.

Prelude> map (\x -> x^20 `mod` 100) $ filter (\x -> gcd x 100 == 1) $ [0..99]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

[Trotil]

Ну так я перебором это и обнаружил, мне интересно, есть ли другой способ

[Xaositect]

Если я нигде не напутал, можно так:
$a\equiv a_1\ (\mathrm{mod} 4)$
$a\equiv a_2\ (\mathrm{mod} 25)$
$a_1^{20}\equiv 1\ (\mathrm{mod} 4)$
$a_2^{20}\equiv 1\ (\mathrm{mod} 25)$ ($\varphi(25) = 20$)
и китайская теорема.

[maxal]

см. http://en.wikipedia.org/wiki/Carmichael_function