Dato , (oppure a % M) denota il resto della divisione di a per M.
Il modulo dunque gode della proprietà secondo cui il risultato di una operazione di modulo non supera mai il modulo utilizzato. Vale inoltre la seguente proprietà: per , .
Esempio: e

Il prodotto di due valori in modulo per un valore è uguale al prodotto dei resti dei due valori e per in modulo .

Dimostrazione:
siano e , con , allora esistono e tali che e .
Pertanto


Abbiamo quattro addendi nell'espressione sopra.
Per calcolare il modulo di ciascun addendo, dobbiamo fare il modulo di ogni elemento del prodotto di quell'addendo. Per esempio per calcolare dobbiamo fare per poi moltiplicarlo con , ecc.
, il motivo è che è multiplo di dunque il resto di per è 0, tale 0 viene moltiplicato per il modulo di , qualunque sia il loro risultato viene annullato quando moltiplicato per zero. Lo stesso ragionamento vale per gli altri addendi che contengono la .

Abbiamo dimostrato che: dove e sono i resti di e , il che equivale a dire che:

La potenza di per in modulo è uguale alla potenza del resto di per elevato a in modulo .

Dimostrazione:
sia con
allora esiste tale che .
Pertanto


ma non è altro che , dunque come volevasi dimostrare

divide
Ovvero tale che
Ovvero

Per ogni (infatti )
Per ogni (infatti )
Per ogni (infatti )

Se e allora infatti:
sia e allora .
Vediamolo con un esempio: se , il che vuol dire che e , il che vuol dire che , allora e in particolare

Se e allora per ogni intero i, j.
Infatti, se e , allora , ovvero equivale ad moltiplicare per una costante più alta.

Se e , allora .
Per mostrare un esempio, troviamo prima due numeri e , il cui MCD sia 1.
Supponiamo che , i divisori di sono:
Scegliamo invece , i divisori di sono:

Adesso vogliamo che divida , scegliamo , in tal modo divide poiché il resto della divisione tra e restituisce come resto. La proprietà dice che se è vero che divide e che il massimo divisore comune tra e è , allora divide .

"X congruente a Y modulo M".
Esempio:

Significa che X diviso M dà resto 1 (quindi per qualche )
Tale equivalenza ci dice che e sono tra di loro coprimi.
Esempio: , infatti con

La funzione di Eulero è una funzione aritmetica che restituisce il numero di interi positivi inferiori a n che sono coprimi con n, ovvero il numero di interi positivi tra 1 e n - 1 che non hanno fattori primi in comune con n, eccetto l'1. In parole semplici, la conta quanti numeri coprimi con , ci sono fino a .

Esempio: , i numeri minori di , che non hanno fattori in comune con se non l', sono: , dunque .

Diciamo che un numero è una radice primitiva modulo n se e solo se l'ordine di modulo n è .

In altre parole, se è una radice primitiva modulo n, allora elevando a tutti i possibili esponenti da a , otterremo un insieme completo di resti diversi modulo n, ovvero per ogni numero che va da a usato come esponente di , e applicatagli l'operazione , si ottengono numeri primi diversi.
, dunque, genera tutti i numeri coprimi con n quando elevato a potenze successive.

Esempio: consideriamo

Numeri primi minori di

Dobbiamo adesso trovare un numero tale che elevandolo a ogni risulta che

Proviamo con .
OK
OK
Tuttavia, ci rendiamo conto che, qualsiasi usato come potenza per , ci darà sempre in , il che vuol dire che il numero di valori primi generati da non sarà dell'ordine di . Infatti ha numeri primi. Usando , avremo solo come valore generato.

Proviamo con .
OK
OK
OK
Abbiamo di nuovo il 2
I numeri generati da sono e sono che non sono dell'ordine di .

Proviamo con .
OK
OK
OK
OK
OK
OK
Abbiamo nuovamente il 3
I numero generati da sono , dunque sono dell'ordine di .