Il teorema di Eulero

Dato l'intero n > 1 diciamo C(n) l'insieme degli interi compresi tra 1 ed n-1 che sono coprimi con n.
In simboli: C (n) = {a : 1 Ł a Ł n-1 Ù MCD(a,n) = 1}, dove MCD(a,b) è il massimo comun divisore di a e b.

Per definizione j (n) è il numero degli elementi che stanno in C(n):

j (n) = |C(n)|
La funzione j è detta funzione di Eulero.

Esempi

C(12) = {1, 5, 7, 11}

C(5) = {1, 2, 3, 4}

C(15) = {1, 2, 4, 7, 8, 11, 13, 14}

Evidentemente se p è primo j (p) = p-1.

Inoltre se MCD(a,b)=1 allora j (ab) = j (a)j (b).

Vale l'importante Teorema di Eulero:

Se a appartiene a C(n) allora:

a^j(n) = 1 mod n

equivalentemente:

n divide ( a^j(n) - 1)

In particolare se p è primo e p non divide a allora:

p divide (a^p-1- 1)

Il caso particolare di p primo, cioè a^p-1= 1 mod n viene detto Piccolo Teorema di Fermat, perché venne scoperto da Fermat (1601-1665), che però non lo dimostrò. La dimostrazione venne data da Eulero (1707-1783).

Per esempio:

n = 15, j (n) = 8, a = 11, 11⁸ - 1 = 214358880 = 15 ´ 14290592

p = 13, j (p) = 12, a = 2, 2¹² - 1 = 4095 = 13 ´ 315

Inoltre si prova che dato qualsiasi a in C(n) esiste sempre un unico b in C(n) tale che

a b = 1 mod n

b si dice inverso di a modulo n.

Vediamo due esempi:

per n = 15 si ha:

a	1	2	4	7	8	11	13	14
inverso	1	8	4	13	2	11	7	14

per n = 13 si ha:

a	1	2	3	4	5	6	7	8	9	10	11	12
inverso	1	7	9	10	8	11	2	5	3	4	6	12