Vés al contingut

Teorema d'Euler

De Viki.cat

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

<math>a^{\varphi(n)} \equiv 1 \mod n.</math>

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

<math>7^4 \equiv 1 \mod n.</math>

se'n dedueix que

<math>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.</math>

Per tant la xifra buscada és <math>9</math>.

Enllaços externs