Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
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