Home

Federica EU

1/21

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 (Z_m ,+) è 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 (Z_m ,+).
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)=x^r è un isomorfismo tra (Z ,+) e C;
se C è finito di ordine m, la funzione g di Z_m in C definita ponendo g([r]_m)=x^r è un isomorfismo tra (Z_m ,+) e C.

Premesse sui gruppi ciclici

Dimostrazione
Se r,s sono numeri interi, allora si ha f(r+s)=x^r+s =x^r x^s =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 ,+)= (Z_n ,+), sicché segue dal Teorema di Omomorfismo che C è isomorfo al gruppo quoziente (Z_n ,+).

se C è infinito, allora Z_n è 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 Z_m in C definita ponendo g([r]_n)=x^rè un isomorfismo tra
(Z_n ,+) e C. D’altra parte, Z_n 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:

C={ x⁰=1 , x, … , x^m-1 };
se r,s sono numeri interi, allora x^r=x^s se e solo se r≡s (mod m);
in particolare x^r=1 se e solo se r è un multiplo di m;
m è il minimo dell’insieme {rє N | x^r=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 gⁿ=1.
Dimostrazione
Per il Teorema di Lagrange, n è un multiplo di |<g>|
⇒ per la (3) della Proposizione 5.2, gⁿ=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^ϕ⁽ⁿ⁾≡1 (mod n).
Dimostrazione
Per ipotesi, (a,n)=1
⇒ [a]_n appartiene a Z_n*
⇒ per il Corollario 5.3, [a]_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 a^r ≡a (mod n).
Dimostrazione
Sia n=p₁…p_t con p₁ ,… , p_t primi positivi due a due distinti, e sia k un numero intero tale che
r=1+kφ(n); per il Teorema 4.7, φ(n)=(p₁-1)…(p_t-1).
Sia i un elemento dell’insieme {1, … ,t }, e si consideri il primo p_i.
Se a è multiplo di p_i , allora a≡0 e quindi a^r≡0 (mod p_i) ⇒ p_i divide a^r-a.

Teorema di Fermat

Si supponga che a sia multiplo di p_i ⇒  per il Teorema di Fermat-Eulero, a^pⁱ^-1 ≡1 (mod p_i)
⇒ a^kφ(n) ≡1 (mod p_i) ⇒  a^r=a∙a^kφ(n) ≡a (mod p_i) ⇒  anche in questo caso p_i divide a^r-a.
Dunque ciascun primo p_i divide a^r-a ⇒  n divide a^r-a a^r ≡a (mod n).
Teorema 5.6 (Piccolo Teorema di Fermat)
Sia p un numero primo positivo. Allora per ogni numero intero a si ha a^p ≡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 x^s è un generatore di C se e solo se m e s sono coprimi.
Dimostrazione
Si supponga in primo luogo che C=<x^s>
⇒ esiste un umero intero t tale che x=x^st
⇒ 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=x^sv
⇒ x appartiene a <x^s>
⇒ C=<x^s>.

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 x^m=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=<x^k>
⇒ x^kd=1
⇒ kd è un multiplo di m
⇒ k è un multiplo di $\frac{m}{d}$
⇒ x^k 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 | gⁿ=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>
⇒ hⁿ=1.
Viceversa sia g un elemento di C tale che gⁿ=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:

l’insieme {gє C | g^d=1} coincide con l’unico sottogruppo di C di ordine d
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, Y_d l’insieme {gє C | g ha periodo d}.
Allora ogni Y_d ha ordine φ(d) e l’insieme {Y_d | 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=y².
Proposizione 5.14
Sia C=<x> un gruppo ciclico finito di ordine m pari.
Allora x^j è 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 x^j=(xⁱ)².
Viceversa, sia g^j un quadrato in C⇒ esiste un numero intero i tale che x^j=(xⁱ)² ⇒ x^j-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=2^uv con v dispari.
Allora per ogni numero naturale n tale che n=2^rt con t dispari e 0≤r<u, si ha che l’insieme {gєC | gⁿ=b} ha ordine (m,n) (cioè 2^r(v,t)).
Dimostrazione
Sia T l’insieme {gєC | g²ⁿ=1}⇒ |T|=(m,2n)=(m,2^r+1t)=(2^uv,2^r+1t)=2^r+1(v,t)=2(m,n).
D’altra parte, g²ⁿ=(gⁿ)² , sicché T ={gєC | gⁿ=b}U{gєC | gⁿ=1}
⇒ 2(m,n)= |{gєC | gⁿ=b}| + |{gєC | gⁿ=1}| = |{gєC | gⁿ=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 Y_d l’insieme degli elementi di H di periodo d.
Sia r un qualunque divisore positivo di n tale che Y_r sia non vuoto e sia K l’insieme degli elementi di H che sono radici del polinomio x^r-1 appartenente a F[x] ⇒  |K|≤r.
Sia h un elemento di Y_r
⇒ <h> è contenuto in K
⇒ <h> = K
⇒  Y_r coincide con l’insieme dei generatori del gruppo K, che è ciclico di ordine r
⇒  |Y_r|=φ(r).

Sottogruppi finiti del gruppo moltiplicativo di un campo

L’insieme Ω ={Y_d | Y_d≠Ø} è 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 Y_d≠Ø ; in particolare Y_n≠Ø , 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}^*$
⇒ a^r ≡1 (mod p²)
⇒ a^r ≡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≡a^p-1+(p-1)pa^p-2≡1+(p-1)pa^p-2 (mod p²)
⇒ (p-1)pa^p-2≡0 (mod p²)
⇒ p divide (p-1)a^p-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 φ(p^n-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}^*$
⇒ b^r≡1 (mod pⁿ)
⇒ b^r≡1 (mod p^n-1), cioè $[b]_{p^n-1}=[1]_{p^n-1}$
⇒ r è un multiplo di φ(p^n-1).
D’altra parte r è un divisore dell’ordine di $\mathbf{Z}_{p^n}^*$ , che è φ(pⁿ)=pφ(p^n-1)
⇒ r=φ(p^n-1) oppure r=φ(pⁿ).
Si supponga per assurdo che r=φ(p^n-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)$
⇒ kp^n-1≡0 (mod pⁿ)
⇒ 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}}^*$ è φ(p^n-1).
Questa contraddizione prova che r=φ(pⁿ), sicché $<\cyc{[b]_{p^n}} >= \mathbf{Z}_{p^n}^*$ .