Modulär aritmetik med höga tal, eulers sats och kinesiska restsatsen.

Ja men precis.

12^639 är ingen vidare förenkling. 

Så dela upp 3960=8*9*5*11.

Så t.ex. för 5, phi(5) = 4:

$x\equiv {12}^{639}\equiv {12}^{140·4-1}\equiv {12}^{-1}\equiv 2^{-1}\equiv 3 (mod 5)$

Och sedan samma procedur för 8,9 och 11?

ghc235 skrev:

Så t.ex. för 5, phi(5) = 4:

$x\equiv {12}^{639}\equiv {12}^{140·4-1}\equiv {12}^{-1}\equiv 2^{-1}\equiv 3 (mod 5)$

Och sedan samma procedur för 8,9 och 11?

Jo men precis, och sen använda kinesiska restsatsen för att få resten modulo 3960.

Hur gavs att 12^639 är kongruent med 12^(140*4-1) och att det sedan är kongruent med 12^(-1)

hoppsan, 160 * 4 - 1 ska det vara, då är det dessutom en likheter och inte bara en kongruens. 

a ^ phi(n) är kongruent med 1 (mod n) enligt eulers sats. Jag faktoriserar alltså 12^639 som 12^phi(5)^140 * 12^(-1), där den första faktorn är kongruent med 1^140 som är 1.

ghc235 skrev:

hoppsan, 160 * 4 - 1 ska det vara, då är det dessutom en likheter och inte bara en kongruens. 

a ^ phi(n) är kongruent med 1 (mod n) enligt eulers sats. Jag faktoriserar alltså 12^639 som 12^phi(5)^140 * 12^(-1), där den första faktorn är kongruent med 1^140 som är 1.

det makear sense! Tack