Teorema d'Euler

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 primer amb n, llavors

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

on \varphi és la funció Funció Fi d'Euler i mod designa la Congruència sobre els enters.


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

7^4 \equiv 1 \mod n.

se'n dedueix que

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.

Enllaços externs[modifica | modifica el codi]