Examples Using Euler's Theorem

# 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)
\begin{align} 55^{5} = 5^5 \cdot 11^5 = 5^{5} \cdot 11^4 \cdot 11 \equiv 5^{12} \cdot (1)^4 \cdot 11 \equiv 34375 \equiv 5 \pmod {10} \end{align}

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)
$$4444 = 40(111) + 4$$

Hence it follows that:

(3)
\begin{align} 3333^{4444} \equiv (3333^{40})^{111} \cdot 3333^{4} \equiv (1)^{111} \cdot 3333^4 \pmod {100} \equiv 33^4 = 1185921 \equiv 21 \pmod {100} \\ \end{align}

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)
$$202 = 12(16) + 10$$

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)
\begin{align} 29^{10} \equiv 3^{10} = 59049 \equiv 3 \pmod {13}^2 \end{align}

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)
$$999999 = 22(45454) + 11$$

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.