Communities

tag:snake search within a tag
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
created:<1w created < 1 week ago
post_type:xxxx type of post
Q&A

Show that $\forall n \in \mathbb{Z}^{+}$, $25^n \equiv 25 \bmod{100}$.

+3
−0

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.

Why does this post require moderator attention?
Why should this post be closed?

+4
−0

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.

Why does this post require moderator attention?

+4
−0

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}

Why does this post require moderator attention?