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
|
{ 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 reuslta 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 <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
- Eric W. Weisstein, Teorema d'Euler a MathWorld.