Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 9 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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
1  
Then, I'm lost here! where did $16(1-10n)+10(n+1)-1$ come from? –  MinaHany Jun 8 '12 at 15:32
1  
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$.)

share|improve this answer
    
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$

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.