# 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 55 ^{5}.**

We first note that finding the last digit of 55^{5} can be obtained by reducing 55^{5} (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:

Hence the last digit of 55^{5} is 5.

## Example 2

**Find the last two digits of 3333 ^{4444}.**

We first note that finding the last two digits of 3333^{4444} can be obtained by reducing 3333^{4444} (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 3333^{4444} are 2 and 1.

## Example 3

**Find the remainder 29 ^{202} 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 29^{202} is divided by 13, the remainder leftover is 3.

## Example 4

**Find the remainder of 99 ^{999999} 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 99^{999999} 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.