Inverse elementer og eulers sætning

Jeg er ikke helt klar over hvad du spørger om. Det fremgår af Euler, som du selv siger. Hvis du bare vil regne det ud kan jeg fortælle dig at phi(25)=20

Skidt, jeg omgik problemet på en anden måde. :)

Det jeg ikke kan finde ud af er vist, hvad a^phi(n)-1(mod n) egentlig betyder - altså hvordan det udregnes. Hvis det er, vil jeg da stadig gerne vide det, men da jeg alligevel ikke skal bruge det, er det kun hvis du sidder og keder dig helt vildt ;)

Jeg er iIgen lidt usikker på hvad du sørger om. Hvis det er phi(n) så er phi(pi)=p^i-1(p-1), når p er et primtal. Er det sammensat af flere primtal skal de bare ganges sammen for eks. for 2 forskellige primtal p og q vil du få phi(pⁱ*q^j)=phi(pⁱ) phi(q^j).

Hvis det er et udtryk som a^s mod(n) kan du i princippet bare udregne a^s og derefter finde resten ved division med n. I praksis vil a^s normalt blive så stor, at det ikke kan beregnes. Så må man bare tage det i bidder. Her skal man bruge at a*b mod n= (a mod n )*(b mod n). Helt primitivt kan du så først  finde a*a mod n, dernæst a³ mod n = (a² mod n)* (a mod n) o.s.v. For meget store værdier af n vil det dog gå for langsomt. Så kan man bruge et andet trick ´f. eks. a³⁵⁷ mod n  = a^300+50+7 mod n = a³⁰⁰ *a⁵⁰*a⁷ mod n = (a³⁰⁰ mod n) *(a⁵⁰ mod n) *(a⁷ mod n) = ((a¹⁰⁰)^3 mod n)*((a¹⁰)^5)*(a⁷ mod n) =                          ((a¹⁰⁰ mod n)³  mod n)*((a¹⁰ mod n)⁵)*(a⁷ mod n). Her kan man finde a¹⁰⁰ mod n  som (a¹⁰ mod n)* (a¹⁰ mod n).

Jeg har her beskrevet det ud fra 10-talssystemet; men i praksis bruger man 2-tals systemet, da det er mere effektivt.