Lagrange's theorem
The residue classes modulo that are coprime to form a group under multiplication (see the article Multiplicative group of integers modulo "n" for details). The order of that group is . Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case . If is any number coprime to then is in one of these residue classes, and its powers modulo form a subgroup of the group of residue classes, with . Lagrange's theorem says must divide , i.e. there is an integer such that . This then implies,