Teorema d'Euler

En matemàtiques, i en particular en aritmètica modular, el teorema d'Euler és un teorema, anomenat així en honor del matemàtic suís Leonhard Euler, que estableix que

Teorema d'Euler - Sigui n un nombre natural i a un enter coprimer amb n, llavors

$a^{\varphi (n)}\equiv 1\mod n.$

on $\varphi$ és la funció fi d'Euler i mod designa la congruència sobre els enters.

Demostració

Si a és coprimer amb n, llavors la multiplicació per a permuta el residu de les classes mòdul n que siguin coprimeres amb n; en altres paraules (escrivint R per indicar el conjunt que consisteix en els φ(n) d'aquestes classes diferents) els conjunts

{ x : x de R } i

{ ax : x de R }

són iguals; per tant, els seus productes són iguals. Així,

P ≡ a^φ(n)P (mod n) on P és el primer d'aquests productes.

Com que P és coprimer amb n, en resulta que

a^φ(n) ≡ 1 (mod n).

Aquest teorema és una generalització del petit teorema de Fermat (que no tracta més que el cas on n és un nombre primer), i al seu torn és una cas particular del teorema de Carmichaël.

Aquest teorema permet simplificar el càlcul de les potències mòdul n. Per exemple, si es vol trobar el valor de $7^{222}$ mòdul $10$ , és a dir trobar a quina classe és congruent $7^{222}$ mòdul $10$ , n'hi ha prou amb veure que 7 i 10 són primers entre ells, i que $\varphi (10)=4$ . Per tant el teorema d'Euler indica que