Examples Using Euler's Theorem
Recall that Euler's theorem states that if $(a, m) = 1$, then $a^{\phi (m)} \equiv 1 \pmod {m}$. We will now apply this property to some common questions.
Example 1
Find the last digit of 555.
We first note that finding the last digit of 555 can be obtained by reducing 555 (mod 10), that is evaluating $55^{5} \pmod {10}$. We note that (10, 55) = 5, and hence this pair is not relatively prime, however, we know that 55 has a prime power decomposition of 55 = 5 x 11. (11, 10) = 1, hence it follows that $11^{\phi (10)} \equiv 1 \pmod {10}$. We note that $\phi (10) = 4$. Hence $11^4 \equiv 1 \pmod {10}$, and more appropriately:
(1)Hence the last digit of 555 is 5.
Example 2
Find the last two digits of 33334444.
We first note that finding the last two digits of 33334444 can be obtained by reducing 33334444 (mod 100). Since (3333, 100) = 1, we can apply this theorem.
We first calculate that $\phi (100) = \phi (2^2) \phi(5^2) = (2)(5)(4) = 40$. Hence it follows from Euler's theorem that $3333^{40} \equiv 1 \pmod {100}$. Now let's apply the division algorithm on 4444 and 40 as follows:
(2)Hence it follows that:
(3)Hence the last two digits of 33334444 are 2 and 1.
Example 3
Find the remainder 29202 when divided by 13.
We first note that $(29, 13) = 1$. Hence we can apply Euler's Theorem to get that $29^{\phi (13)} \equiv 1 \pmod {13}$. Since 13 is prime, it follows that $\phi (13) = 12$, hence $29^{12} \equiv 1 \pmod {13}$. We can now apply the division algorithm between 202 and 12 as follows:
(4)Hence it follows that $29^{202} = (29^{12})^{26} \cdot 29^{10} \equiv (1)^{26} \cdot 29^{10} \equiv 29^{10} \pmod{13}$.
Also we note that 29 can be reduced to 3 (mod 13), and hence:
(5)Hence when 29202 is divided by 13, the remainder leftover is 3.
Example 4
Find the remainder of 99999999 when divided by 23.
Once again we note that $(99, 23) = 1$, hence it follows that $99^{\phi (23)} \equiv 1 \pmod {23}$. Once again, since 23 is prime, it goes that $\phi (23) = 22$, and more appropriately $99^{22} \equiv 1 \pmod {23}$. We will now use the division algorithm between 999999 and 22 to get that:
(6)Hence it follows that $99^{999999} = (99^{22})^{45454} \cdot 99^{11} \equiv 1^{45454} \cdot 99^{11} \equiv 7^{11} = 1977326743 \equiv 22 \pmod {23}$.
Hence the remainder of 99999999 when divided by 23 is 22.
Note that we can solve the final congruence a little differently as: $99^11 \equiv 7^{11} = (7^2)^5 \cdot 7 = (49)^5 \cdot 7 \equiv 3^5 \cdot 7 = 1701 \equiv 22 \pmod {23}$. There are many ways to evaluate these sort of congruences, some easier than others.