NB: ci sono esattamente n interi modulo n (e cioè 0, 1, . . . , n-1)

Fatto importante: se a e q sono interi primi fra loro (in particolare se q è primo e a non è divisibile per q, cioè non è uguale a 0 modulo q, allora ci sono altri interi b e c tali che

Dimostrazione

Conseguenze importanti:
1) Se p è primo e a non è uguale a 0 mod p allora c'è un altro intero b tale che

Inoltre se c è un altro intero c'è un quarto intero d tale che da = c mod p (basta prendere d = bc). In altre parole, si può dividere per a modulo p.

2) Se p e a sono come in 1) e a₁, a₂, . . . , a_h sono interi distinti modulo p, allora anche aa₁, aa₂, . . . , aa_h sono distinti modulo p (se aa_i e aa_j fossero uguali mod p, moltiplicandoli per b si concluderebbe che a_i e a_j sono uguali mod p, contro le ipotesi).

3) Se p e a sono come in 1), ogni intero è uguale modulo p a uno e uno solo tra 0a, a, 2a, 3a, . . . , (p-1)a; infatti questi interi sono distinti modulo p (per la conseguenza 2) e sono esattamente p. Dato che 0a = 0, ne segue che ogni intero non nullo modulo p è uguale, modulo p, a uno e uno solo tra a, 2a, 3a, . . . , (p-1)a.

4) Una dimostrazione del piccolo teorema di Fermat