Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 5.Teorema di Fermat-Eulero e Piccolo teorema di Fermat. Alcune proprietà dei gruppi ciclici finiti


Premesse sui gruppi ciclici

I concetti presentati in questa e nella prossima slide fanno parte dei contenuti dei corsi di Algebra del primo anno, ma vengono esplicitamente richiamati, in quanto utili nel seguito.
Si è già ricordato, nella Lezione 3, che il gruppo (Z,+) è un gruppo ciclico infinito, mentre per ogni numero intero m,  il gruppo (Zm ,+) è un gruppo ciclico finito di ordine m. Si è inoltre ricordato, sempre nella Lezione 3, che una parte non vuota H di Z è un sottogruppo di (Z,+) se e solo se esiste un intero m tale che H=<m>.
Segue infine, dalla definizione di “congruenza modulo m”, presentata sempre nella Lezione 3, che il gruppo quoziente (Z/<m> ,+) coincide con il gruppo (Zm ,+).
Teorema 5.1 
Sia C=<x> un gruppo ciclico (dato in notazione moltiplicativa). Allora:

  • se C è infinito, la funzione f di Z in C definita ponendo f(r)=xr è un isomorfismo tra (Z ,+) e C;
  • se C è finito di ordine m, la funzione g di Zm in C definita ponendo g([r]m)=xr è un isomorfismo tra (Zm ,+) e C.

Premesse sui gruppi ciclici

Dimostrazione
Se r,s sono numeri interi, allora si ha f(r+s)=xr+s =xr xs =f(r)f(s).
Dunque f è un omomorfismo e quindi un epimorfismo.
D’altra parte esiste un numero intero non-negativo n tale che ker f =<n> e quindi (Z/ker f ,+)=  (Zn ,+), sicché segue dal Teorema di Omomorfismo che C è isomorfo al gruppo quoziente (Zn ,+).

  • se C è infinito, allora Zn è infinito, per cui Ker f =<n>={0}, e f è un isomorfismo tra (Z ,+) e C.
  • sia C finito di ordine m.

Premesse sui gruppi ciclici

Segue dal Teorema di Omomorfismo che la funzione g di Zm in C definita ponendo g([r]n)=xr è un isomorfismo tra
(Zn ,+) e C.  D’altra parte, Zn ha ordine n, sicché m=n, e quindi si ha l’asserto.
Dal precedente teorema segue in modo immediato la seguente proposizione
Proposizione 5.2
Sia C=<x> un gruppo ciclico finito di ordine m. Allora:

  1. C={ x0=1 , x, … , xm-1 };
  2. se r,s sono numeri interi, allora xr=xs se e solo se r≡s (mod m);
  3. in particolare xr=1 se e solo se r è un multiplo di m;
  4. m è il minimo dell’insieme {rє N |  xr=1}.

Premesse sui gruppi ciclici

Corollario 5.3
Sia G un gruppo finito di ordine n. Allora per ogni elemento g di G,  si ha gn=1.
Dimostrazione
Per il Teorema di Lagrange, n è un multiplo di |<g>|
⇒ per la (3) della Proposizione 5.2, gn=1

Teorema di Fermat – Eulero

Teorema 5.4 (Teorema di Fermat-Eulero)
Sia n un numero intero tale che n>1. Se a è un numero intero tale che a e n siano coprimi, allora aϕ(n) ≡1 (mod n).
Dimostrazione
Per ipotesi, (a,n)=1
⇒ [a]n appartiene a Zn*
⇒ per il Corollario 5.3, [a]nϕ(n) = [1]n

Teorema di Fermat

Teorema 5.5
Siano n,r numeri naturali tali che n sia libero da quadrati e r≡1 (mod φ(n)). Allora per ogni numero intero a si ha  ar ≡a (mod n).
Dimostrazione
Sia n=p1…pt con p1 ,… , pt primi positivi due a due distinti, e sia k un numero intero tale che
r=1+kφ(n); per il Teorema 4.7, φ(n)=(p1-1)…(pt-1).
Sia i un elemento dell’insieme {1, … ,t }, e si consideri il primo pi .
Se a è multiplo di pi , allora a≡0 e quindi ar≡0 (mod pi) ⇒  pi divide ar-a.

Teorema di Fermat

Si supponga che a sia multiplo di pi ⇒  per il Teorema di Fermat-Eulero, api-1 ≡1 (mod pi)
⇒ akφ(n) ≡1 (mod pi) ⇒  ar=a∙akφ(n) ≡a (mod pi) ⇒  anche in questo caso pi divide ar-a.
Dunque ciascun primo pi divide ar-a  ⇒  n divide ar-a ar ≡a (mod n).
Teorema 5.6 (Piccolo Teorema di Fermat)
Sia p un numero primo positivo. Allora per ogni numero intero a si ha  ap ≡a (mod p).
Dimostrazione
Poiché φ(p)=p-1 e p≡1 (mod p-1), l’asserto segue dal Teorema 5.5.

Generatori di un gruppo ciclico finito

Proposizione 5.7
Sia C=<x> un gruppo ciclico finito di ordine m. Allora xs è un generatore di C se e solo se m e s sono coprimi.
Dimostrazione
Si supponga in primo luogo che C=<xs>
⇒ esiste un umero intero t tale che x=xst
⇒ 1≡st (mod m)
⇒ esiste un numero intero k tale che 1=st+km
⇒ (m,s)=1.
Viceversa, si supponga che (m,s)=1
⇒ esistono numeri interi u,v tali che 1=mu+sv, sicché x=xsv
⇒ x appartiene a <xs>
⇒ C=<xs>.

Inversione forte del Teorema di Lagrange

La seguente proposizione assicura che per i gruppi ciclici finiti vale una “inversione forte del Teorema di Lagrange”.
Teorema 5.8
Sia C=<x> un gruppo ciclico finito di ordine m; sia d un divisore positivo di m.
Allora il sottogruppo \cyc{x^{\frac{m}{d}}} è l’unico sottogruppo di C di ordine d.
Dimostrazione
Poiché m è il minimo intero positivo tale che xm=1, si verifica immediatamente che d è il minimo intero positivo tale che (x^{\frac{m}{d}})^d=1
⇒ \vert \cyc<{x^{\frac{m}{d}}} >\vert =d.
Sia K un sottogruppo di C tale che |K|=d.

Inversione forte del Teorema di Lagrange

Poiché C =<x> e i sottogruppi di un gruppo ciclico sono ciclici (cfr. Lezione 3), esiste un numero intero k tale che K=<xk>
⇒ xkd=1
⇒ kd è un multiplo di m
⇒ k è un multiplo di \frac{m}{d}
⇒ xk appartiene \vert \cyc<{x^{\frac{m}{d}}} >\vert =d
⇒ K è un sottogruppo di \vert \cyc<{x^{\frac{m}{d}}} >\vert =d
⇒ K=\cyc<{x^{\frac{m}{d}}} >=d.
Corollario 5.9
Sia C=<x> un gruppo ciclico finito di ordine m pari. Allora x^{\frac{m}{2}} è l’unico elemento di C di periodo 2.

Alcune conseguenze dell’inversione del teorema di Lagrange

Proposizione 5.10
Sia C=<x> un gruppo ciclico finito di ordine m.
Allora per ogni numero naturale n, l’insieme {gє C | gn=1} coincide con l’unico sottogruppo di C di ordine (m,n).
Dimostrazione
Sia n un numero naturale e si indichi con H l’unico sottogruppo di C di ordine (m,n).
Sia h un qualunque elemento di H⇒ (m,n) è un multiplo di <h>⇒ n è un multiplo di dell’ordine di <h>
⇒ hn=1.
Viceversa sia g un elemento di C tale che gn=1, e sia s l’ordine di <g>
⇒ n è un multiplo di s ⇒ (m,n) è un multiplo di s⇒ H ha un unico sottogruppo di ordine s;
d’altra parte l’unico sottogruppo di H di ordine s è anche l’unico sottogruppo di C di ordine s⇒ g appartiene a H.

Alcune conseguenze dell’inversione del teorema di Lagrange

Sia C un gruppo ciclico finito e sia H un suo sottogruppo; detto d l’ordine di H, segue da quanto visto finora che l’insieme degli elementi di C di periodo d coincide con l’insieme dei generatori di H. Si ha dunque il seguente corollario:
Corollario 5.11
Sia C=<x> un gruppo ciclico finito di ordine m e sia d un divisore positivo di m. Allora:

  1. l’insieme {gє C | gd=1} coincide con l’unico sottogruppo di C di ordine d
  2. l’insieme {gє C | g ha periodo d} ha ordine φ(d).

Una proprietà della funzione di Eulero

Proposizione 5.12
Sia n un numero naturale. Allora
n=\sum _{ _{1\leq d \vert n}} \varphi (d).
Dimostrazione
Si fissi un gruppo ciclico C di ordine n, e sia, per ogni divisore positivo d di n, Yd l’insieme {gє C | g ha periodo d}.
Allora ogni Yd ha ordine φ(d) e l’insieme {Yd  |  d è un divisore positivo di n} è una partizione di n; l’asserto segue dal Corollario 5.11.

Gruppi ciclici di ordine pari

Definizione 5.13
Sia G un gruppo e sia g un elemento di G. Si dice che g è un quadrato in G se esiste un elemento y di G tale che g=y2.
Proposizione 5.14
Sia C=<x> un gruppo ciclico finito di ordine m pari.
Allora xj è un quadrato in C se e solo se j è pari.
Dimostrazione 
Se j è pari allora esiste un numero i tale che j=2i e quindi xj=(xi)2.
Viceversa, sia gj un quadrato in C⇒ esiste un numero intero i tale che xj=(xi)2 ⇒ xj-2i=1
⇒ j-2i è un multiplo di m⇒ j è pari.

Gruppi ciclici di ordine pari

Proposizione 5.15
Sia C=<x> un gruppo ciclico finito di ordine m pari, e sia b l’unico elemento di C di periodo 2.
Si ponga m=2uv con v dispari.
Allora per ogni numero naturale n tale che n=2rt con t dispari e 0≤r<u, si ha che l’insieme {gєC | gn=b} ha ordine (m,n) (cioè 2r(v,t)).
Dimostrazione
Sia T l’insieme {gєC | g2n =1}⇒ |T|=(m,2n)=(m,2r+1 t)=(2uv,2r+1 t)=2r+1 (v,t)=2(m,n).
D’altra parte, g2n =(gn)2 , sicché T ={gєC | gn=b}U{gєC | gn=1}
⇒ 2(m,n)= |{gєC | gn=b}| + |{gєC | gn=1}| = |{gєC | gn=b}| + (m,n).
Da quest’ultima uguaglianza segue l’asserto.

Sottogruppi finiti del gruppo moltiplicativo di un campo

Teorema 5.16
Sia H un sottogruppo finito del gruppo moltiplicativo di un campo F. Allora H è ciclico.
Dimostrazione 
Sia n=|H|.
Per ogni divisore positivo d di n, si indichi con Yd l’insieme degli elementi di H di periodo d.
Sia r un qualunque divisore positivo di n tale che Yr sia non vuoto e sia K l’insieme degli elementi di H che sono radici del polinomio xr -1 appartenente a F[x] ⇒  |K|≤r.
Sia h un elemento di Yr
⇒ <h> è contenuto in K
⇒ <h> = K
⇒  Yr coincide con l’insieme dei generatori del gruppo K, che è ciclico di ordine r
⇒  |Yr|=φ(r).

Sottogruppi finiti del gruppo moltiplicativo di un campo

L’insieme Ω ={Yd  |  Yd≠Ø} è una partizione di H
n=\sum _{ _{Y_d\in \Omega}} \varphi (d)
D’altra parte,
n=\sum _{ _{1\leq d \vert n}} \varphi (d)
⇒ per ogni divisore positivo d di n, deve essere Yd≠Ø ; in particolare Yn≠Ø  , sicché H è ciclico.

Il gruppo delle classi invertibili modulo la potenza di un primo dispari

Teorema 5.17 

Sia p un numero primo dispari.
Allora per ogni numero naturale n, \mathbf{Z} _{p^n}^* è ciclico.
Dimostrazione
Si procede per induzione su n.
Segue dai Teoremi 3.3 e 5.16 che esiste  un numero a appartenente all’insieme {1, … , p-1} tale che \mathbf{Z}_p^* = \cyc<{[a]_p}>.
Sia r il periodo di [a]_{p^2} in \mathbf{Z}_{p^2}^* e sia s il periodo di [a+p]_{p^2} in \mathbf{Z}_{p^2}^*
⇒ ar ≡1 (mod p2)
⇒ ar ≡1 (mod p), cioè ([a]p)r =[1]p
⇒ r è un multiplo di p-1.
D’altra parte r è un divisore dell’ordine di \mathbf{Z}_{p^2}^*, che è p(p-1)
⇒ r=(p-1) oppure r=p(p-1).

Il gruppo delle classi invertibili modulo la potenza di un primo dispari

Analogamente  si prova che s=(p-1) oppure s=p(p-1).

Si supponga per assurdo che r=p-1=s.
Sviluppando con la formula del binomio di Newton, si ha:
1≡(a+p)p-1≡ap-1+(p-1)pap-2≡1+(p-1)pap-2 (mod p2)
⇒ (p-1)pap-2≡0 (mod p2)
⇒ p divide (p-1)ap-2, una contraddizione che prova che r=p(p-1) oppure s=p(p-1).
Si è dunque provato che una tra le due classi [a]_{p^2} oppure [a+p]_{p^2} è un generatore sia di \mathbf{Z}_p^* che di \mathbf{Z}_{p^2}^*.
Sia ora n≥3, e si supponga che b sia un numero tale che [b]_{p^i} sia un generatore di \mathbf{Z}_{p^i}^* per ogni i<n.

Il gruppo delle classi invertibili modulo la potenza di un primo dispari

Dal fatto che \mathbf{Z}_{p^{n-2}} ha ordine φ(pn-2), si ha che [b]_{p^{n-2}}^{\varphi (p^{n-2})}=[1]_{p^{n-2}}

⇒ esiste un numero intero k tale che b^{\varphi (p^{n-2})} =1+kp^{n-2}.
Sia r il periodo di [b]_{p^n} in \mathbf{Z}_{p^n}^*
⇒ br≡1 (mod pn)
⇒ br≡1 (mod pn-1), cioè [b]_{p^n-1}=[1]_{p^n-1}
⇒ r è un multiplo di φ(pn-1).
D’altra parte r è un divisore dell’ordine di \mathbf{Z}_{p^n}^*, che è φ(pn)=pφ(pn-1)
⇒ r=φ(pn-1) oppure r=φ(pn).
Si supponga per assurdo che r=φ(pn-1)
⇒ b^{\varphi (p^{n-1})} \equiv 1 \; (mod \; p^n).

Il gruppo delle classi invertibili modulo la potenza di un primo dispari

Sviluppando con la formula del binomio di Newton, si ha
1 \equiv b^{\varphi (p^{n-1})} =b^{p\varphi (p^{n-2})}=(1+kp^{n-2})^p \equiv 1+ p kp^{n-2} =1+ kp^{n-1} \; (mod \; p^n)
⇒ kpn-1≡0 (mod pn)
⇒ p divide k
⇒ b^{\varphi (p^{n-2})} =1+kp^{n-2} \equiv 1 \; (mod \; p^{n-1}), il che è assurdo perché il periodo di [b]_{p^{n-1}} in \mathbf{Z}_{p^{n-1}}^* è φ(pn-1).
Questa contraddizione prova che r=φ(pn), sicché <\cyc{[b]_{p^n}} >= \mathbf{Z}_{p^n}^*.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion