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

on é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 mòdul , és a dir trobar a quina classe és congruent mòdul , n'hi ha prou amb veure que 7 i 10 són primers entre ells, i que . Per tant el teorema d'Euler indica que

se'n dedueix que

Per tant la xifra buscada és .

Enllaços externs