Ingegneria Energetica - Analisi e Geometria 1

Fermat e Eulero

Divided by topic

P I C C OLO T E ORE M A DI F E RM AT T E ORE M A DI E U LE RO Osservazione 1.Sianoa; b2Z. Si osservi che, seab(modn), allora, tenendo presente chebb(modn) e usando (2) del Lemma 1, si haab0 (modn). Proposizione 1.Sianox; y2Z,p2N,pprimo. Al lora (x+y)p xp +yp (modp): (1) Dimostrazione.Per la formula del binomio di Newton si ha: (x+y)p =p X k=0 p k
xk yp k : Se 1kp1, allorapj p k
;in quanto p k =( p) kk != p
(p1)




(pk+ 1)k
(k1)




2
1 e certamente nessuno tra i numeri interi al denominatore:k; k1; : : : ;2 puo essere un divisore dipche e un numero primo maggiore di essi. Allora, per ognik2N, con 1kp1, risulta  p k 0(modp) per cui (1) e vericata. Teorema 1.(Piccolo teorema di Fermat) Sianoa2Z,p2Nun numero primo. Al lora (2)ap a(modp): Dimostrazione.Si suppone in un primo momento che siaa0 e si procede per induzione completa sua. Pera= 0,ap = 0 e (2) diviene 00 (modp), ovviamente vera. Si suppone che (2) sia vera e si prova (a+ 1)p a+ 1 (modp):Per la Proposizione 1, la proprieta transitiva della congruenza modulone l'ipotesi di induzione risulta: (a+ 1)p ap + 1p a+ 1 (modp): quindi (2) e vericata quandoa0. Sea 0 e quindi (a)p  (a) (modp). Usando nuovamente la Proposizione 1, la proprieta transitiva della congruenza modulone l'ipotesi di induzione, si ha: 0 = (a+ (a))p ap + (a)p ap + (a) (modp): Pertantoap + (a)0 (modp) da cui, per l'Osservazione 1,ap a(modp). Corollario 1.Sianoa2Z,p2Nun numero primo. SeM :C:D:(a; p) = 1al lora ap 1 1(modp): Dimostrazione.Poichepjap a, ovveropja(ap 1 1), certamentepjap 1 1, essendopprimo e non divisore dia, per ipotesi. Esercizio 1.Determinare il resto della divisione di 89741527 per 3. Si osserva che897412(mod3) e quindi, per il Lemma 1 del capitolo sulla fattorizzazione, 89741527 2527 (mod3): Per il Corollario 1, poicheM :C:D:(2;3) = 1, si ha 23 1 1(mod3) (in questo caso e banale) e pertanto 89741527 2527 = (22 )263
21263
2 = 2(mod3) per cui il resto e 2.1 2 Esercizio 2.Determinare il resto della divisione di 190597 per 17. Bisogna esprimere 190597 (mod17). Si osserva prima che 1903(mod17): Inoltre, e noto cheap 1 1(modp), seM :C:D:(a; p) = 1. Quindi nel caso in esame 316 1(mod17): Allora3597 = (316 )37
35 137
35 = 35 (mod17): Si vede facilmente che 35 = 2385(mod17), e quindi il resto e 5. Esercizio 3.Determinare il resto della divisione di 574321142 per 9. Si osserva che574323(mod9) e quindi574321142 31142 (32 )571 0571 0(mod9): Denizione 1.Si dicefunzione di Eulerol'applicazione ':N f0;1g !N tale che8n2N f0;1g,'(n)=numero dei numeri minori dine primi conn. Osservazione 2. E ovvio che per ogni numero primop '(p) =p1 La dimostrazione dei risultati che seguono viene omessa. Proposizione 2.La funzione di Eulero e moltiplicativa, cioe 8n; m2N f0;1g; n >1; m >1 tali cheM :C:D:(n; m) = 1; '(n
m) ='(n)
'(m): Proposizione 3.Siapun numero primo. Al lora '(ph ) =ph ph 1 : Proposizione 4.Sian2N f0;1g, e sian=ph 1 1
: : :
ph s sla sua fattorizzazione in numeri primi. Al lora '(n) ='(ph 1 1)
: : :
'(ph s s) : Teorema 2.(teorema di Eulero) Sianoa2Z ,n2N f0;1g, conM :C:D:(a; n) = 1. Al lora a' (n) 1(modn): Esercizio 4.Determinare le ultime due cifre del numero 523321 . Si deve ridurre 523321 (mod100). Si osserva che 52323(mod100) e quindi523321 23321 (mod100): PoicheM :C:D:(23;100) = 1, si puo usare il teorema di Eulero, secondo il quale (3) 23' (100) 1(mod100): Per le proprieta della funzione di Eulero si ha '(100) ='(52 )'(22 ) = (52 5)
(22 2) = 20
2 = 40 3 pertanto (3) diventa2340 1(mod100): D'altra parte 321 = 40
8 + 1 e quindi 23321 = (2340 )8
2318
23 = 23(mod100) In conclusione 523321 23(mod100). Esercizio 5.Determinare le ultime 3 cifre del numero 17331 . Per determinare le ultime 3 cifre del numero 17331 , bisogna ridurlo (mod 1000). Si puo osservare che'(1000) = 400 e che l'esponente e 31