Euler's theorem is a generalization of Fermat's little theorem dealing with powers of integers modulo positive integers. It arises in applications of elementary number theory, including the theoretical underpinning for the RSA cryptosystem.
Let be a positive integer, and let be an integer that is relatively prime to Then
where is Euler's totient function, which counts the number of positive integers which are relatively prime to
Suppose is relatively prime to Since Euler's theorem says that i.e. the units digit of is always See the wiki on finding the last digit of a power for similar problems.
Here are two proofs: one uses a direct argument involving multiplying all the elements together, and the other uses group theory.
Proof using residue classes:
Consider the elements of the congruence classes of integers that are relatively prime to For the claim is that multiplication by is a permutation of this set; that is, the set equals The claim is true because multiplication by is a function from the finite set to itself that has an inverse, namely multiplication by
For example, let and Then Multiplication by turns this set into So it permutes the elements of the set.
Multiplication by is the inverse of this permutation.
Now, given the claim, consider the product of all the elements of On one hand, it is On the other hand, it is So these products are congruent mod :
where cancellation of the is allowed because they all have multiplicative inverses
Proof using Lagrange's theorem:
The elements in with multiplicative inverses form a group under multiplication, denoted . This group has elements. The subgroup consisting of the powers of has elements, where is the multiplicative order of because the elements of the subgroup are
By Lagrange's theorem, say for some integer Since
Show that if is an odd integer, then divides .
The statement is clear for so assume By Euler's theorem, . Since , we have for some integer . So
An army of worker ants was carrying sugar cubes back into their colony. In there, the ants put 1 sugar cube into the first room, 2 into the second, 4 into the third, and doubling the amount so on until the room.
Then the queen ant decided to build bigger cubic blocks of sugar cubes from all they had previously collected. How many sugar cubes would remain after all these build-ups?
Let and for Find the last two digits of
Note that mod for all Now the goal is to compute Since it suffices to compute mod Similarly, we want mod mod and mod But all the are odd, so Working our way back up,
So and so by the Chinese remainder theorem it is congruent to a unique element mod which is by inspection.