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 φ ( n ) ≡ 1 mod n . {\displaystyle a^{\varphi (n)}\equiv 1\mod n.}

on φ {\displaystyle \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 {\displaystyle 7^{222}} mòdul 10 {\displaystyle 10} , és a dir trobar a quina classe és congruent 7 222 {\displaystyle 7^{222}} mòdul 10 {\displaystyle 10} , n'hi ha prou amb veure que 7 i 10 són primers entre ells, i que φ ( 10 ) = 4 {\displaystyle \varphi (10)=4} . Per tant el teorema d'Euler indica que

7 4 ≡ 1 mod n . {\displaystyle 7^{4}\equiv 1\mod n.}

se'n dedueix que

7 222 ≡ 7 4 × 55 + 2 ≡ ( 7 4 ) 55 × 7 2 ≡ 1 55 × 7 2 ≡ 49 ≡ 9 mod 10. {\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9\mod 10.}

Per tant la xifra buscada és 9 {\displaystyle 9} .

Enllaços externs

  • Eric W. Weisstein, Teorema d'Euler a MathWorld.