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.

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

share|improve this question

7 Answers 7

up vote 3 down vote accepted

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.

share|improve this answer
    
@TaraB i just assume it for $n$ and prove it for $n+1$, maybe i should rephrase it –  Dominic Michaelis Mar 28 '13 at 17:16
    
OK, I think I see where I messed this up - I did the algebra wrong when I let $n=k+1$... I had set $2^{5n}$ to $2^{5n+2}$ instead of $2^{5n+5}$ –  agent154 Mar 28 '13 at 17:21
    
@agent154 I am glad i could help –  Dominic Michaelis Mar 28 '13 at 17:23

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

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

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

share|improve this answer
    
You only get odd $n$ with your induction, right? Maybe you shoudd add $(a-b)|(a^2-b^2)$ –  Simon Markett Mar 28 '13 at 17:08
    
@SimonMarkett, thanks for your observation. –  lab bhattacharjee Mar 28 '13 at 17:11

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

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

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

share|improve this answer

The other answers are file, I just want to give an answer that works from where you were.

You had: $$5^{2k}-2^{5k} = 7m$$ and were looking at $$5^{2k+2}-2^{5k+5}= 5^{2k}\cdot 5^2 - 2^{5k}\cdot 2^5$$

And trying to prove this is divisible by $7$. From the first equation, you know $5^{2k}=7m+2^{5k}$, so just replace $5^{2k} with that value in the second equation to get:

$$\begin{align}5^{2k+2}-2^{5k+5} &= (7m+2^{5k})\cdot 5^2 - 2^{5k}\cdot 2^5\end{align}$$

Then do some arithmetic with the distributive law a couple of times to show this is divisible by $7$.

You could just as well have instead replaced $2^{5k}$ with $5^{2k}-7m$ instead, but don't replace both :)

share|improve this answer

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

share|improve this answer

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.