# 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 Walters 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

$\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$

-

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