9
$\begingroup$

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.

7 Answers 7

12

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

  • 0
    You're welcome, I figured this was more what you were looking for.2012-06-08
8

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.

  • 1
    Phira's point is that $4^{2(n+1)}$ is congruent to $16(1-10n)$ mod $25$ if the induction hypothesis is assumed.2012-06-08
3

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

  • 0
    $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 :-)2017-04-18
3

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

2

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

  • 0
    (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$)2017-04-18
0

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

  • 0
    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$.2012-06-08