Fermat e Eulero

Page 1

P ICCOLO T EOREM A DI F ERM AT − T EOREM A DI EU LERO Osservazione 1. Siano a, b∈ Z. Si osservi che, se a≡ b (mod n), allora, tenendo presente che b≡ b (mod n) e usando (2) del Lemma 1, si ha a− b≡ 0 (mod n). Proposizione 1. Siano x, y∈ Z, p∈ N, p primo. Allora (x + y)p≡ xp + yp(mod p).(1) Dimostrazione. Per la formula del binomio di Newton si ha: (x + y)p = p∑ k=0 (p k ) xkyp−k. Se 1≤ k≤ p− 1, allora p| (p k ) , in quanto ( p k ) = (p)k k! = p· (p− 1)····· (p− k + 1) k· (k− 1)····· 2· 1 e certamente nessuno tra i numeri interi al denominatore: k, k− 1, . . . ,2 pu` o essere un divisore di p che ` e un numero primo maggiore di essi. Allora, per ogni k ∈ N, con 1≤ k≤ p− 1, risulta ( p k ) ≡ 0(mod p) per cui (1) ` e verificata. Teorema 1. (Piccolo teorema di Fermat) Siano a∈ Z, p∈ N un numero primo. Allora (2) ap ≡ a (mod p). Dimostrazione. Si suppone in un primo momento che sia a ≥ 0 e si procede per induzione completa su a. Per a = 0, ap = 0 e (2) diviene 0 ≡ 0 (mod p), ovviamente vera. Si suppone che (2) sia vera e si prova (a+1) p ≡ a+1 ( mod p). Per la Proposizione 1, la propriet` a transitiva della congruenza modulo n e l’ipotesi di induzione risulta: (a + 1)p ≡ ap + 1p ≡ a + 1 (mod p). quindi (2) ` e verificata quando a≥ 0. Se a < 0, allora −a > 0 e quindi ( −a)p ≡ (−a) ( mod p). Usando nuovamente la Proposizione 1, la propriet` a transitiva della congruenza modulo n e l’ipotesi di induzione, si ha: 0 = (a + (−a))p ≡ ap + (−a)p ≡ ap + (−a) (mod p). Pertanto ap + (−a) ≡ 0 (mod p) da cui, per l’Osservazione 1, ap ≡ a (mod p). Corollario 1. Siano a∈ Z, p∈ N un numero primo. Se M.C.D.(a, p) = 1 allora ap−1≡ 1(mod p). Dimostrazione. Poich´ ep| ap− a, ovvero p| a(ap−1− 1), certamente p| ap−1− 1, essendo p primo e non divisore di a, per ipotesi. Esercizio 1. Determinare il…