# Prove that $4^{2n} + 10n -1$ is a multiple of 25

Prove that if $n$ is a positive integer then $4^{2n} + 10n - 1$ is a multiple of $25$

I see that proof by induction would be the logical thing here so I start with trying $n=1$ and it is fine. Then assume statement is true and substitute $n$ by $n+1$ so I have the following:

$4^{2(n+1)} + 10(n+1) - 1$

And I have to prove that the above is a multiple of 25. I tried simplifying it but I can't seem to get it right. Any ideas? Thanks.

Here is a proof by induction. Suppose $4^{2n}+10n-1=25k$.

$$4^{2(n+1)}+10(n+1)-1$$ $$=16\cdot 4^{2n}+10n+9$$ $$=16\cdot 4^{2n}+160n-16-150n+25$$ $$=16(4^{2n}+10n-1)-150n+25$$ $$=16(25k)-25\cdot 6n+25$$ $$=25(16k-6n+1)$$

• Very clear. Nice and simple! Thank you :) – MinaHany Jun 8 '12 at 16:47
• You're welcome, I figured this was more what you were looking for. – Jackson Jun 8 '12 at 16:50

1) Proof by induction:

Set $4^{2n}+10n-1=25k$ and use this to replace the term $4^{2(n+1)}$ in your expression.

It remains to show that 25 divides $16(1-10n)+10(n+1)-1$ which is obviously true.

2) Shorter proof without induction: Expand $(5-1)^{2n}$ using the binomial theorem.

• hmm.. How did $4^{2n+2}$ become $16(1-10n)$ ? – MinaHany Jun 8 '12 at 15:01
• @MinaHany Phira did not say that it is. – AD. Jun 8 '12 at 15:28
• Then, I'm lost here! where did $16(1-10n)+10(n+1)-1$ come from? – MinaHany Jun 8 '12 at 15:32
• Phira's point is that $4^{2(n+1)}$ is congruent to $16(1-10n)$ mod $25$ if the induction hypothesis is assumed. – hardmath Jun 8 '12 at 15:53

Here are the details to complete the induction argument you started. There are better ways than induction.

By the induction hypothesis, $4^{2n}+10n-1$ is a multiple of $25$. So it is enough to prove that $$\left(4^{2n+2}+10(n+1)-1\right)-\left(4^{2n}+10n-1\right)\tag{1}$$ is a multiple of $25$.

Expression $(1)$ simplifies to $4^{2n+2}-4^{2n}+10$. But $4^{2n+2}=(16)4^{2n}$, so we want to prove that $(15)4^{2n}+10$ is a multiple of $25$.

It is enough to prove that $(3)4^{2n}+2$ is a multiple of $5$. We have $4\equiv -1\pmod{5}$, so $4^{2n}\equiv 1\pmod{5}$, and therefore $(3)4^{2n}+2\equiv 5\equiv 0\pmod{5}$.

(If you don't know about congruences, we can note that the decimal representation of $4^{2n}$ ends in $6$, since $4^2=16$, and conclude that the decimal representation of $(3)4^{2n}+2$ ends in $0$.)

• Yes, I do know congruences. Would you please try to simplify the last paragraph? – MinaHany Jun 8 '12 at 15:09
• $15(4^{2n}+10n-1) = (15)4^{2n}+150n-15 = (15)4^{2n}+10 +25(6n-1)$ so $25 \mid (15)4^{2n}+10$ from reusing hypothesis :-) – Joffan Apr 18 '17 at 21:47

$\rm\displaystyle 25\ |\ 10n\!-\!(1\!-\!4^{2n}) \iff 5\ |\ 2n - \frac{1-(-4)^{2n}}{5}.\$ Now via $\rm\ \dfrac{1-x^k}{1-x}\, =\, 1\!+\!x\!+\cdots+x^{k-1}\$ $\rm\displaystyle we\ easily\ calculate\ that, \ mod\ 5\!:\, \frac{1-(-4)^{2n}}{1-(-4)\ \ \,}\, =\, 1\!+\!1\!+\cdots + 1^{2n-1} \equiv\, 2n\ \$ by $\rm\: -4\equiv 1$

Another solution, via congruences mod. $25$. First note $16\bmod 25$ generates a cyclic group of order $5$: $$16^2\equiv 6,\quad16^3\equiv 6\cdot 16\equiv-4,\quad16^4\equiv6^2\equiv 11, \quad 16^5\equiv6\cdot-4\equiv1\mod25.$$ So let's examine each case:

• If $n\equiv 0\mod 5$, $\;16^n+10n-1\equiv1+0-1=0$.
• If $n\equiv 1\mod 5$, $\;16^n+10n-1\equiv16+10-1=25\equiv 0$.
• If $n\equiv 2\mod 5$, $\;16^n+10n-1\equiv 6+20-1=25\equiv 0$.
• If $n\equiv 3\mod 5$, $\;16^n+10n-1\equiv -4+30-1=25\equiv 0$.
• If $n\equiv 4\mod 5$, $\;16^n+10n-1\equiv 11+40-1=50\equiv 0$.

Thus in each case, $\;16^n+10n-1$ is divisible by $25$.

• (and we know it must generate a group of order five because $\phi(25)=20$ and so $2^{20}=16^5\equiv 1 \bmod 25$) – Joffan Apr 18 '17 at 21:19

This is an interesting property, so can we precisely describe when it is true? The answer is yes:

Theorem: In an arbitrary ring, $q^n$ is an affine function of $n$ if and only if $(q-1)^2=0$. We then have $q^n=1+n(q-1)$.

Proof: If $q^n=a+bn$, by taking $n=0$ and $n=1$ we see that $a=1$ and $b=q-1$. Taking $n=2$ results in $q^2=2q-1$, that is $(q-1)^2=0$.

Conversely, when $(q-1)^2=0$, it is easy to prove the relation by induction: $$q^0=1$$ $$q^{n+1}=q(1+n(q-1))=nq^2-q(n-1)=1+(n+1)(q-1)$$

There is also a direct proof by seeing that $q^n=(1+(q-1))^n=\sum_{i=0}^n \tbinom{n}{i} (q-1)^i=1+n(q-1)$.

Application: in $\mathbb Z/25\mathbb Z$, if $q=4^2$, $(q-1)^2=15^2=0$, so $4^{2n}=1+15n$, or equivalently $4^{2n}+10n-1=0$.

• More generally one has (implicit in my answer) $$\rm \dfrac{f(x)-f(a)}{x-a}\, \equiv\, f{\,}'(a)\pmod{x-a}$$ – Bill Dubuque Jun 8 '12 at 17:34
• It's true (and a very nice equality!), but I was especially interested in the reciprocal of the theorem, which only makes sense when $a=1$. – Generic Human Jun 8 '12 at 18:02

Let $$S$$ be the shift operator on sequences: $$Sa_n=a_{n+1}$$. Then $$\color{#C00}{(S-16)}\color{#090}{(S-1)^2}\left(\color{#C00}{16^n}\color{#090}{-1+10n}\right)=0\tag1$$ Since $$(x-16)(x-1)^2=x^3-18x^2+33x-16$$, our sequence satisfies $$a_n=18a_{n-1}-33a_{n-2}+16a_{n-3}\tag2$$ Note that $$\begin{array}{c|c} n&16^n-1+10n&\bmod{25}\\\hline 0&0&0\\ 1&25&0\\ 2&275&0 \end{array}\tag3$$ $$(2)$$ and $$(3)$$ show inductively that, for $$n\ge0$$, $$16^n-1+10n\equiv0\pmod{25}\tag4$$