Teorema de Euler

Leonhard Euler, retratat en 1753 per Jakob Emanuel Handmann. Kunstmuseum Basel.

En teoria de números la teorema de Euler, també conegut com a teorema de Euler-Fermat, és una generalisació del menuda teorema de Fermat, i com tal afirma una proposició sobre la divisibilidad dels número entero. La teorema establix que:

Si a i n són sancers cosins relatius, llavors n dividix al sancer aφ(n)- 1 Leonhard Euler (1736)

no obstant, és més comú trobar-ho en notació moderna en la següent forma:

Si a i n són sancers cosins relatius, llavors aφ(n) ≡ 1 (mod n). Leonhard Euler (1736)

a on φ(n) és la funció φ de Euler.

Funció φ de Euler

Artícul principal → Funció φ de Euler.

Si n és un número entero, la cantitat de sancers entre 1 i n que són cosins relatius en n es denota com φ(n):

Valor de n Coprimos en n entre 1 i n Funció φ(n) 1 1 1 2 1 1 3 1,2 2 4 1,3 2 5 1,2,3,4 4 6 1,5 2 7 1,2,3,4,5,6 6 8 1,3,5,7 4 9 1,2,4,5,7,8 6 10 1,3,7,9 4

φ(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 0+   1 1 2 2 4 2 6 4 6 10+ 4 10 4 12 6 8 8 16 6 18 20+ 8 12 10 22 8 20 12 18 12 28 30+ 8 30 16 20 16 24 12 36 18 24 40+ 16 40 12 42 20 24 22 46 16 42 50+ 20 32 24 52 18 40 24 36 28 58 60+ 16 60 30 36 32 48 20 66 32 44 70+ 24 70 24 72 36 40 36 60 24 78 80+ 32 54 40 82 24 64 42 56 40 88 90+ 24 72 44 60 46 72 32 96 42 60

A la funció φ se li coneix com a funció φ de Euler. Tal funció és multiplicativa: si m i n són primers relatius, llavors

φ(mn)=φ(m)φ(n).

Demostracion: Sabem que:

$\phi (n)=n\prod _{p_i|n}(1-\frac{1}{p_i})\text{ con }{p}_i\text{ primo},$

de manera que:

$\phi (n)\phi (m)=mn\prod _{p_i|n}(1-\frac{1}{p_i})\prod _{q_i|m}(1-\frac{1}{q_i})$

Com $\mathrm{mcd}(m,n)=1$, cap dels cosins $p_i$ i $q_i$ són iguals, després la descomposició en cosins de $mn$ no es veu alterada, és dir, si $m=q_1^{{\beta }_1}{q}_2^{{\beta }_2}\mathrm{...}{q}_k^{{\beta }_1}$ i $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\mathrm{...}{p}_j^{{\alpha }_j}$ la descomposició en cosins de $mn$ serà $mn=q_1^{{\beta }_1}{q}_2^{{\beta }_2}\mathrm{...}{q}_k^{{\beta }_1}{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\mathrm{...}{p}_j^{{\alpha }_j}$, la qual cosa implica

$\phi (mn)=mn\prod _{p_i|n}(1-\frac{1}{p_i})\prod _{q_i|m}(1-\frac{1}{q_i})$

per lo tant

$\phi (mn)=\phi (m)\phi (n)$

si $m$ i $n$ són primers relatius.

Congruència

Artícul principal → Congruència.

L'atre concepte involucrat en la teorema de Euler és el de congruència. En teoria de números, es diu que dos números a, b són congruents respecte a un mòdul n, quan n dividix al sancer a-b. La congruència de a, b respecte al mòdul n se simbolisa com a ≡ b (mod n).

La congruència de números es comporta de manera similar a una igualtat (formalment, és una relació d'equivalència):

• Si a≡b (mod n) llavors: a+c≡b+c (mod n) i ac ≡ bc (mod n) per a qualsevol sancer c. És dir, es pot sumar o multiplicar una mateixa cantitat a abdós costats d'una congruència i es preserva la relació.
• Si a≡b (mod n) i b≡c (mod n) llavors a≡c (mod n). És atres paraules, la relació és transitiva.

Un eixemple senzill per a entendre l'aritmètica en congruència ho proporciona un rellonge de manetes, ya que les hores en un rellonge es comporten com a congruència mòdul 12. Per eixemple, les 15 i les 3 hores són indicades per la mateixa posició en el rellonge; esta equivalència s'escriuria com

• 15 ≡ 3 (mod 12)

i s'obté de que 12 dividix a 15-3.

Si ara el rellonge marca les 5, dins de 30 hores marcarà les 11, perque 12 dividix a 35-11 =24 i aixina:

• 5+30 = 35 ≡ 11 (mod 12).

Una particularitat de les congruència, que la diferència de l'igualtat comuna és que, encara que podem sumar o multiplicar una mateixa cantitat a abdós costats d'una congruència preservant-la, no podem fer lo mateix en una divisió:

• 6· 4 ≡ 3·4 (mod 6), puix 6 dividix a 24-12; no obstant no és cert que 6 ≡ 3 (mod 6).

No obstant, hi ha un cas especial en el que sí és possible efectuar tal cancelació: quan el factor i el mòdul són primers relatius:

• Ya que 5·4 ≡ 5·10 (mod 6) i el màxim comú divisor de 5 i 6 és 1 (és dir, són primers relatius), llavors podem cancelar el 5 i obtindre 4 ≡ 10 (mod 6).