TEOREMA DI EULERO

TEOREMA di EULERO : Se a è coprimo con n allora a elevato a Φ(n) è congruo a 1 modulo n

ESEMPIO: 
 
n=10 =2²x5² e
Φ(10)=4
infatti sono coprimi con 10  : 1 3 7 9 
 allora 3 ^ 4=1 mod10 e infatti è 81=1 mod10
E anche 7^4=1 mod10
oppure 9^4=1 mod 10

LA FUNZIONE PHI DI EULERO

La funzione di Eulero di un numero naturale n si indica con Φ(n) ed è uguale ai numeri primi con n minori di n compreso 1. 

Ad esempio n=10 i numeri minori di n sono 1 2 3 4 5 6 7 8 9 di questi sono primi con 10 il 3 7 9 insieme a 1. Allora Φ(10)=4

Φ(n)=n(1-1/p1)(1-1/p2).....(1-1/pm)

dove p1,p2,....pm sono fattori primi di n  .


Esempio: 
n=10 = 2x5
Φ(10)=10(1-1/2)(1-1/5)=10x1/2 x4/5=4
n=100
Φ(100)=100(1-1/2)(1-1/5)=40

PROPRIETA':
1. φ(p) = p - 1 se p è primo;
2.

infatti i numeri non primi con

sono quelli con fattori in comuni, ma essendo p primo sono tutti i multipli di p minori 

Quindi quelli primi sono tutti meno quelli non primi.

3. φ è una "funzione moltiplicativa", vale a dire φ(m*n)=φ(m)*φ(n) quando i fattori m e n son primi fra di loro, cioè MCD(m, n)=1;