5

I'm stuck on my inductive step, and can't figure out how to manipulate this algebraically to get the form that I want...

$5^{2k}-2^{5k}=7m,m\in\mathbb{Z}$

\begin{align*} 5^{2k+2}-2^{5k+2}=5^{2k}\cdot 5^{2}-2^{5k}\cdot 2^{2} \end{align*}

So i'm not sure what to do now...

Yimin
  • 3,311
  • 17
  • 32
Mirrana
  • 9,009

6 Answers6

5

I wouldn't do this by induction. Modular arithmetic is your friend!

$$5^{2n} - 2^{5n} = 25^n - 32^n\equiv 4^n - 4^n \equiv 0 \pmod{7}.$$

(You could turn this into a proof by induction: show that for all $n\in \mathbb{N}$ the remainders upon division by $7$ of $5^{2n}$ and $2^{5n}$ are the same. But it really wouldn't be that nice.)

Tara B
  • 5,341
  • mh i am missing the induction ... – Dominic Michaelis Mar 28 '13 at 17:11
  • Ah yes, I was just about to check whether it was required to be proved by induction. Oops! – Tara B Mar 28 '13 at 17:12
  • @TaraB I have to do it by induction though; It's an assignment question that says as much. – Mirrana Mar 28 '13 at 17:14
  • 1
    @agent154: Yes, sorry, I didn't check that before posting my answer. I'll modify my answer to hint at how you can dress this up into a proof by induction. – Tara B Mar 28 '13 at 17:16
  • Umm, hmm, this approach is not the most amenable to pretending to be induction, because it's just obvious right off. (I have made non-induction proofs successfully look like induction before, e.g. here, but this one really doesn't want to be.) – Tara B Mar 28 '13 at 17:20
  • Thanks for your detailed answer for my question. +1 – Mikasa Mar 29 '13 at 09:23
  • I accidentally gave essentially the same proof before I saw your answer. (+1) – robjohn Apr 05 '13 at 00:16
4

Maybe another solution for $n=1$ we have $25-32=-7$ this one has the divisor $7$.
Now we assume that $7||5^{2n}-2^{5n}$ for a $n$ and we will show that this implies $7|5^{2(n+1)}-2^{5(n+1)}$.

The main idea is that $32=25+7$, so we will be able to manipulate it in a multiple of our assumption and add a multiple of $7$.

$$5^{2n+2}-2^{5n+5}=25 \cdot 5^{2n} - 32 \cdot 2^{5n}=25\cdot 5^{2n}- (25+7)\cdot 2^{5n}= 25\cdot (5^{2n}-2^{5n}) -7 \cdot 2^{5n}$$ The first part is divisble through $7$ by our assumption, and the second is a multiple of $7$. Hence it is true.

Dominic Michaelis
  • 19,935
2

$5^{2n}=(5^2)^n=25^n$ Similarly, $2^{5n}=32^n$

$$\text{So, }5^{2n}-2^{5n}=25^n-32^n$$

Now,

(1)$(a^n-b^n)(a+b)=a^{n+1}-b^{n+1}+ab(a^{n-1}-b^{n-1})$

$\implies a^{n+1}-b^{n+1}=(a^n-b^n)(a+b)-ab(a^{n-1}-b^{n-1})$

If $(a-b)$ divides $(a^{n-1}-b^{n-1}),(a^n-b^n)$

it will divide $ (a^{n+1}-b^{n+1})$

Now, $(a-b)\mid (a-b)$ and $(a-b)\mid (a^2-b^2)$

(2)$(a-b)(a^n+b^n)=a^{n+1}-b^{n+1}-ab(a^{n-1}-b^{n-1})$

$\implies a^{n+1}-b^{n+1}=(a-b)(a^n+b^n)+ab(a^{n-1}-b^{n-1})$

So, $(a-b)\mid (a^{n+1}-b^{n+1})\iff $ it divides $(a^{n-1}-b^{n-1})$

Now, $(a-b)\mid (a-b)$ and $(a-b)\mid (a^2-b^2)$

Here $a=25,b=32$

lab bhattacharjee
  • 274,582
2

$$\forall\;a,b\in\Bbb R\;,\;\;a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1})\implies$$

$$5^{2n}-2^{5n}=25^n-32^n=(25-32)(25^{n-1}+25^{n-2}\cdot32+\ldots+25\cdot32^{n-2}+32^{n-1})$$

and since $\,25-32=-7\,$ we're done and without induction as long as we can assume the first equation above.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • It's very easy without induction (see my answer, for example). But unfortunately the OP was asked to provide a proof by induction, so neither my answer nor your answer is really an answer to the question. – Tara B Mar 29 '13 at 18:47
  • 1
    Oh, don't care about that, @TaraB . The answer stays for whoever may be interested in it...and still a little induction is needed indeed, though it may be a little hidden: the fact that $,a^n-b^n=(a-b)(a^{n-1}+\ldots+b^{n-1}),$ is true for any natural $,n,$ requires it...:) – DonAntonio Mar 29 '13 at 19:02
  • True. =] I thought about trying to sneak induction into my approach, but it just really didn't belong there at all. – Tara B Mar 29 '13 at 19:42
1

Set $a=5^2=25$ and $b=2^5=32$. Then $$ (a^{n+1}-b^{n+1})-(a^{n}-b^{n}) = (a-1)a^n-(b-1)b^n = 24a^n - 31b^n = 24(a^n-b^n) - 7b^n $$ and so $$ a^{n+1}-b^{n+1} = 25(a^{n}-b^{n}) - 7b^n $$ Thus, if $7$ divides $a^{n}-b^{n}$ then $7$ divides $a^{n+1}-b^{n+1}$.

lhf
  • 216,483
1

$\begin{eqnarray}{\bf Hint}&&\rm n\mid\ \ \color{#C00}{a^k\!-\!b^k}\:\ and\:\ n\mid \color{#0A0}{a-b} \\ \Rightarrow\: &&\rm n\mid (\color{#C00}{a^k\!-b^k})\,a\,+\,b^k(\color{#0A0}{a-b})\, =\, a^{k+1}\!-b^{k+1}\end{eqnarray}$

Note $\ $ The above proof is essentially a special case of that for the Congruence Product Rule. Below are proofs of this product rule proof expressed in both divisibility and congruence form, $ $ using the standard notation: $\rm\ \ a\mid b \ :=\ a\,$ divides $\rm\, b,\ $ and $\rm\ \, a\equiv b\ \ (mod\ n) \iff n\mid a-b$

$\begin{eqnarray} \rm {\bf Lemma}\ \ &\rm n\ \ |&\rm\ \, X-x\quad\ and &&\rm n\ |\: Y-y \ \Rightarrow\ n\:|\!\!&&\rm XY - \: xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &\rm n\ \ |&\rm (X-\color{brown}x)\:\color{brown}Y\ \ \ + &&\rm\, \color{brown}x\ (\color{brown}Y-y)\ \ \ = &&\rm XY - \: xy \\ \\ \rm {\bf Lemma}\ \ & &\rm\ \, X\equiv x\quad\ \ and &&\rm\quad\ \ Y\equiv y \ \ \ \ \Rightarrow\ &&\rm XY\equiv xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &0\equiv& \rm (X-\color{brown}x)\:\color{brown}Y\ \ \ + &&\rm\, \color{#C00}x\ (\color{brown}Y-y)\ \ \ \equiv &&\rm XY - \: xy \\ \end{eqnarray}$

Math Gems
  • 19,574