# Prove, for every nonnegative integer $n$, that $5^{2n} + 2^{2n} ≡ 2^{2n+1}\pmod{21}$.

Is my proof correct? Thanks in advance.

Base step: n = 0
$$5^{2 \times 0} + 2^{2 \times 0} ≡ 2^{2 \times 0+1} \pmod{21}$$ $$= 1 + 1 ≡ 2 \pmod{21} \checkmark$$
Inductive hypothesis: assume $$5^{2n} + 2^{2n} ≡ 2^{2n+1} \pmod{21}$$ is true when $$n=k$$: $$5^{2k} + 2^{2k} ≡ 2^{2k+1} \pmod{21}$$
Since the statement above is true we can write the following: $$5^{2k} + 2^{2k} - 2^{2k+1} = 21x$$
Simplify and rewrite: $$2^{2k} = 5^{2k}-21x$$
Now we proceed with the inductive step: $$n = k + 1$$:
$$5^{2(k+1)} + 2^{2(k+1)} ≡ 2^{2(k+1)+1} \pmod{21}$$ $$5^{2k+2} + 2^{2k+2} ≡ 2^{2k+3} \pmod{21}$$
Rephrase the statement above:

$$21 \mid (5^{2k+2} + 2^{2k+2} - 2^{2k+3})$$

$$21 \mid (5^{2k+2} - 4 \times 2^{2k})$$
Replace $$2^{2k}$$ with $$5^{2k}-21x$$:
$$21 \mid (5^{2k+2} - 4 \times (5^{2k}-21x))$$
Multiply out: $$21 \mid (5^{2k+2} - 4\times 5^{2k} + 4\times 21x))$$ $$= 21 \mid (25 \times 5^{2k} - 4\times 5^{2k} + 4\times 21x))$$ $$= 21 \mid (21 \times 5^{2k} + 4\times 21x))$$ $$= 21 \mid 21(5^{2k} + 4x))\checkmark$$
Hence $$5^{2(k+1)} + 2^{2(k+1)} ≡ 2^{2(k+1)+1} \pmod{21}$$
$$\blacksquare$$

• Alt. hint (without induction): $\;5^{2n}+2^{2n}-2^{2n+1}=5^{2n}-2^{2n}=\dots\,$
– dxiv
Commented Nov 14, 2021 at 22:19
• @dxiv sorry, I don't understand how I can use that in my proof.
– a a
Commented Nov 14, 2021 at 22:22
• Your proof looks ok, but it is needlessly complex. Life gets much simpler if you just look $\pmod 3$ and $\pmod 7$.
– lulu
Commented Nov 14, 2021 at 22:27
• @aa Remember the difference of powers identity, and use it for $\,5^{2n}-2^{2n}=25^n-4^n\,$.
– dxiv
Commented Nov 14, 2021 at 22:32

However, it can actually be done with a lot less work and without induction: $$5^{2n}=\left(5^2\right)^n=25^n\equiv 4^n=2^{2n} (\mathrm{mod}\ 21)$$ Hence $$5^{2n}+2^{2n}\equiv 2\cdot 2^{2n}=2^{2n+1} (\mathrm{mod}\ 21)$$.