Show that $\forall n \in \mathbb{Z}^{+}$, $25^n \equiv 25 \bmod{100}$.
Show that $\forall n \in \mathbb{Z}^{+}$, $25^n \equiv 25 \bmod{100}$.
This was a simple observation I made when playing around and I came up with the following proof:
It follows from $(10a + 25)^2 = 100a^2 + 500a + 625 = 100(a^2 + 5a) + 625$ that any number ending in $25$ raised to a power of $2$ will also end in $25$. As each number has a unique binary representation, every number can be written as a sum of powers of two. By the rule $a^{b + c} = a^b \cdot a^c$ and $ab \bmod {c} = (a \bmod {c}) \cdot (b \bmod {c}) \bmod {c}$, $25^n \mod {100}$ will eventually cascade down to $25 \bmod {100}$. For example, \begin{align}25^{19} \equiv 25^{16 + 2 + 1} \equiv 25^{16} \cdot 25^{2} \cdot 25^{1} \equiv 25 \cdot 25 \cdot 25 \\ \equiv 25^{3} \equiv 25^{2 + 1} \equiv 25^2 \cdot 25^1 \equiv 25 \cdot 25 \equiv 25^2 \equiv 25\bmod{100}\end{align}
I am wondering if there are alternate, potentially simpler proofs.
2 answers
You can prove it using the binomial theorem.
Assume that $1\leq n∈\mathbb{N}$, then:
$$ \begin{align} 25^n & =(20+5)^n=\sum_{k=0}^n\binom{n}{k}20^k\cdot 5^{n-k}=5+\sum_{k=1}^{n-1}\binom{n}{k}20^k\cdot 5^{n-k}+20\\ & =25+5\cdot 20\cdot\sum_{k=1}^{n-1}\binom{n}{k}20^{k-1}\cdot 5^{n-k-1}\equiv 25\mod 100 \end{align} $$
0 comment threads
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| Carefree Explorer | (no comment) | Sep 26, 2022 at 07:01 |
There is a fairly simple proof by induction.
Base case: $n = 1$
$$25^1\equiv 25 \mod 100$$
Inductive case: Assuming $25^n\equiv 25 \mod 100$,
$$ \begin{align} 25^{n+1}&\equiv 25\cdot 25^n \mod 100\\ &\equiv 25 \cdot 25 \\ &\equiv 625 \\ &\equiv 25 \end{align} $$
Actually, this proof can easily be extended to show the stronger statement that $5^n\equiv 25\mod 100$ for all natural numbers $n\ge2$
Base case: $n=2$
$$5^2\equiv25\mod100$$
Inductive case: Assuming $5^n\equiv 25 \mod 100$,
$$ \begin{align} 5^{n+1}&\equiv 5\cdot 5^n \mod 100\\ &\equiv 5 \cdot 25 \\ &\equiv 125 \\ &\equiv 25 \end{align} $$
The case with powers of $25$ then simply comes from the case when $n$ is even.
0 comment threads
0 comment threads