Teoremi ausiliari sugli interi

Teorema (388)

Esistono infiniti numeri primi.

 

Dimostrazione

Supponiamo che tutti e soli i primi siano $p_{1},p_{2},\dots ,p_{r}$$p_{1},p_{2},\dots ,p_{r}$. Costruisco allora il numero

$$p_{1}*p_{2}*\dots *p_{r}+1$$

$$p_{1}*p_{2}*\dots *p_{r}+1$$

Questo è un numero intero, che si potrà fattorizzare come prodotto di numeri primi. Questo numero non è divisibile per nessuno dei $p_{i}$$p_{i}$, perché nella divisione per i $p_{i}$$p_{i}$ si ha resto 1. Questo contraddice il teorema fondamentale dell'aritmetica, e affinché il numero si possa fattorizzare, devono esistere altri numeri primi, e così via.

 

Teorema (389 Teorema di Eulero-Fermat)

Siano $a,n$$a,n$ interi positivi, con $M.C.D.(a,n)=1$$M.C.D.(a,n)=1$. Allora $a^{\phi (n)}\equiv 1\mod n$$a^{\phi (n)}\equiv 1\mod n$.

 

Dimostrazione

Definisco l'insieme

$$I=\{[a_{1}],[a_{2}],\dots ,[a_{l}]\}$$

$$I=\{[a_{1}],[a_{2}],\dots ,[a_{l}]\}$$

dove gli $a_{i}$$a_{i}$ sono tutti e soli gli elementi invertibili di $\mathbb {Z} _{n}$$\mathbb {Z} _{n}$. Sappiamo che $l=\phi (n)$$l=\phi (n)$.

Considero poi l'insieme

$$I_{a}=\{[aa_{1}],[aa_{2}],\dots ,[aa_{l}]\}$$

$$I_{a}=\{[aa_{1}],[aa_{2}],\dots ,[aa_{l}]\}$$

ottenuto moltiplicando per $a$$a$ gli elementi di $I$$I$. Allora $[aa_{i}]$$[aa_{i}]$ è ancora invertibile, infatti $M.C.D.(n,aa_{1})=1$$M.C.D.(n,aa_{1})=1$ perché $M.C.D.(a,n)=1$$M.C.D.(a,n)=1$ per ipotesi e anche $a,a_{1}$$a,a_{1}$ sono coprimi.

$I$$I$ però contiene tutti gli elementi invertibili in $\mathbb {Z} _{n}$$\mathbb {Z} _{n}$, allora l'insieme costruito $I_{a}$$I_{a}$ è contenuto in $I$$I$. Se $[aa_{i}]=[aa_{j}]$$[aa_{i}]=[aa_{j}]$, allora $n\mid aa_{i}-aa_{j}=a(a_{i}-a_{j})$$n\mid aa_{i}-aa_{j}=a(a_{i}-a_{j})$, e siccome $n$$n$ è coprimo con $a$$a$, allora $n\mid a_{i}-a_{j}$$n\mid a_{i}-a_{j}$, cioè $[a_{i}]=[a_{j}]$$[a_{i}]=[a_{j}]$, quindi due elementi di $I_{a}$$I_{a}$ sono esattamente $l$$l$, cioè $I_{a}=I$$I_{a}=I$.

Moltiplico tra loro gli elementi di $I$$I$:

$$p_{1}=[a_{1}]*[a_{2}]*\dots *[a_{l}]=[a_{1}a_{2}\dots a_{l}]$$

$$p_{1}=[a_{1}]*[a_{2}]*\dots *[a_{l}]=[a_{1}a_{2}\dots a_{l}]$$

e moltiplicando tra loro gli elementi di $I_{a}$$I_{a}$, dovrei ottenere lo stesso risultato perché i due insiemi sono uguali:

$$p_{2}=[aa_{1}][aa_{2}]\dots [aa_{l}]=[a^{l}a_{1}a_{2}\dots a_{l}].$$

$$p_{2}=[aa_{1}][aa_{2}]\dots [aa_{l}]=[a^{l}a_{1}a_{2}\dots a_{l}].$$

Eguagliando $p_{1}$$p_{1}$ e $p_{2}$$p_{2}$ si deve avere

$$[a^{l}][a_{1}a_{2}\dots a_{l}]=[a_{1}a_{2}\dots a_{l}]$$

$$[a^{l}][a_{1}a_{2}\dots a_{l}]=[a_{1}a_{2}\dots a_{l}]$$

Pongo $x=[a_{1}a_{2}\dots a_{l}]$$x=[a_{1}a_{2}\dots a_{l}]$.

$$[a^{l}][x]=[x]$$

$$[a^{l}][x]=[x]$$

$[x]$$[x]$ è invertibile, perché $M.C.D.(n,a^{l})=1$$M.C.D.(n,a^{l})=1$, allora semplificando per $[x]$$[x]$:

$$[a^{l}]=[1]$$

$$[a^{l}]=[1]$$

cioè $a^{l}\equiv 1\mod n$$a^{l}\equiv 1\mod n$, e quindi $a^{\phi (n)}\equiv 1\mod n$$a^{\phi (n)}\equiv 1\mod n$.

 

Osservazione (390)

L'ipotesi $a,n$$a,n$ coprimi è essenziale, infatti, se $M.C.D.(a,n)=d\neq 1$$M.C.D.(a,n)=d\neq 1$, allora $a^{k}$$a^{k}$ non è mai congruo a 1 modulo $n$$n$ quando $k\geq 1$$k\geq 1$, infatti se $d\mid a^{k}$$d\mid a^{k}$, allora $d\nmid a^{k}-1$$d\nmid a^{k}-1$. In generale, l'equazione $a^{k}\equiv 1\mod n$$a^{k}\equiv 1\mod n$ con $n,a$$n,a$ non coprimi non ha mai soluzione.

 

Esempio (391)

Per $n=12$$n=12$ e $a=7$$a=7$, il teorema dice che siccome $7,12$$7,12$ sono coprimi, allora $7^{\phi (12)}\equiv 1\mod 12$$7^{\phi (12)}\equiv 1\mod 12$. $\phi (12)=n*(1-1/2)*(1-1/3)=12*1/2*2/3=4$$\phi (12)=n*(1-1/2)*(1-1/3)=12*1/2*2/3=4$, quindi $7^{4}\equiv 1\mod 12$$7^{4}\equiv 1\mod 12$. Questo si può verificare, infatti

$$7^{4}-1=(7^{2}-1)(7^{2}+1)=48*50$$

$$7^{4}-1=(7^{2}-1)(7^{2}+1)=48*50$$

e $n=12\mid 48*50$$n=12\mid 48*50$ perché $6\mid 48$$6\mid 48$ e $2\mid 50$$2\mid 50$.