| | |
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$.
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$.
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}$$
🔎 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}$?