## Exercises - Euler's Theorem

1. Find the last $4$ digits of $2^{2020}$.

Finding the last four digits is equivalent to finding the remainder upon division by $1000$ (with leading zeros as needed).

With this in mind, note that $1000 = 2^3 \cdot 5^3$, so $\phi(1000) = (2^3 - 2^2)(5^3 - 5^2) = 400$.

Therefore, using Euler's Theorem: $$2^{2020} = 2^{5 \cdot 400 + 20} = (2^{400})^5 \cdot 2^{20} = 1 \cdot 2^{20} = 1048576 \equiv 8576\pmod{1000}$$

Hence, the last four digits we seek are $8576$.

2. Find the remainder when $1 + 2 + 2^2 + 2^3 + \cdots + 2^{100}$ is divided by $125$.

Recall $1 + 2 + 2^2 + 2^3 + \cdots + 2^{100} = 2^{101} - 1$.

Also note that $\phi(125) = \phi(5^3) = 5^3 - 5^2 = 100$

Consequently, by Euler's Theorem we have $2^{101} - 1 = 2 \cdot 2^{100} \equiv 2(1) - 1 = 1\pmod{125}$

So the remainder when $1 + 2 + 2^2 + 2^3 + \cdots + 2^{100}$ is divided by $125$ is $1$.

3. Prove that if $n$ is an odd integer, then $n$ divides $2^{(n-1)!} - 1$.

The case when $n = 1$ is trivial. When $n \gt 1$, Euler's Theorem applies, yielding $2^{\phi(n)} \equiv 1\pmod{n}$. As $0 \lt \phi(n) \lt n$, $\phi(n) \mid (n-1)!$. Thus, $(n-1)! = \phi(n) \cdot k$ for some integer $k$. The rest is immediate: $$2^{(n-1)!} \equiv 2^{\phi(n)\cdot k} \equiv \left(2^{\phi(n)}\right)^k \equiv 1^k \equiv 1\pmod{n}$$

4. 🔎 How many integers $a$ between 1 and 1000, inclusive, solve $a^{11764} \equiv a^4\pmod{25725}$?

Does $a$ have a multiplicative inverse$\pmod{25725}$?