consider, that for any natural number n > 0, the set of integers modulo n co-prime to n form a group, often called the group of units modulo n, or U(n).

this group has order φ(n): |U(n)| = φ(n). it may not be clear that if gcd(a,n) = 1 and gcd(b,n) = 1, that gcd(ab,n) = 1 as well.

but if gcd(a,n) = 1, then there are integers r,s with ar + sn = 1, and if gcd(b,n) = 1, then there are integers t,u with bt + un = 1.

hence (ar + sn)(bt + un) = 1*1 = 1, so:

ab(rt) + (aru + bst + sun)n = 1, so there are integers x,y (namely x = rt, and y = aru+bst+sun) with (ab)x + yn = 1, gcd(ab,n) = 1.

if we denote a modulo n by [a], this shows that if [a],[b] are in U(n), so is [a][b] = [ab]. since U(n) is finite, it is a group, since it is closed

under multiplication modulo n. thus Lagrange's theorem applies.

to obtain Fermat's Little Theorem, one considers the group U(p), where p is a prime.