Eulers sætning

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 7²²², dvs. 7²²² (mod 10). Bemærk at 7 og 10 er indbyrdes primiske, og φ(10) = 4. Af Eulers sætning fås altså at 7⁴ ≡ 1 (mod 10), og det fås at

7²²² ≡ 7^{4·55 + 2} ≡ (7⁴)⁵⁵·7² ≡ 1⁵⁵·7² ≡ 49 ≡ 9 (mod 10).

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