Eulers sætning

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

I talteorien siger Eulers sætning, at, hvis n er et naturligt tal, og a og n er indbyrdes primiske, gælder kongruensen

aφ(n) ≡ 1 (mod n),

hvor φ(n) er Eulers totientfunktion, og "mod" betegner modulus for kongruensen.

Sætningen er en generalisering af Fermats lille sætning og er yderligere generaliseret af Carmichaels sætning.

Sætningen kan benyttes til let at reducere store eksponenter modulo n. Betragt for eksempel problemet med at finde det sidste decimale ciffer af tallet 7222, dvs. 7222 (mod 10). Bemærk at 7 og 10 er indbyrdes primiske, og φ(10) = 4. Af Eulers sætning fås altså at 74 ≡ 1 (mod 10), og det fås at

7222 ≡ 74·55 + 2 ≡ (74)55·7² ≡ 155·7² ≡ 49 ≡ 9 (mod 10).

Sætningen er opkaldt efter den schweiziske matematiker Leonhard Euler.