Teoremi ausiliari sugli interi

Teorema

Esistono infiniti numeri primi.

 
Dimostrazione

Supponiamo che tutti e soli i primi siano . Costruisco allora il numero

Questo è un numero intero, che si potrà fattorizzare come prodotto di numeri primi. Questo numero non è divisibile per nessuno dei , perché nella divisione per 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

Siano interi positivi, con . Allora .

 
Dimostrazione

Definisco l'insieme

dove gli sono tutti e soli gli elementi invertibili di . Sappiamo che .


Considero poi l'insieme

ottenuto moltiplicando per gli elementi di . Allora è ancora invertibile, infatti perché per ipotesi e anche sono coprimi.


però contiene tutti gli elementi invertibili in , allora l'insieme costruito è contenuto in . Se , allora , e siccome è coprimo con , allora , cioè , quindi due elementi di sono esattamente , cioè .


Moltiplico tra loro gli elementi di :

e moltiplicando tra loro gli elementi di , dovrei ottenere lo stesso risultato perché i due insiemi sono uguali:
Eguagliando e si deve avere
Pongo .
è invertibile, perché , allora semplificando per :
cioè , e quindi .

 


Osservazione

L'ipotesi coprimi è essenziale, infatti, se , allora non è mai congruo a 1 modulo quando , infatti se , allora . In generale, l'equazione con non coprimi non ha mai soluzione.

 


Esempio

Per e , il teorema dice che siccome sono coprimi, allora . , quindi . Questo si può verificare, infatti

e perché e .

 
Successivo