7
$\begingroup$

I am trying to figure out how to prove $17^{200} - 1$ is a multiple of $10$. I am talking simple algebra stuff once everything is set in place.

I have to use mathematical induction.

I figure I need to split $17^{200}$ into something like $(17^{40})^5 - 1$ and have it as $n = 17^{40}$ and $n^5 - 1$.

I just don't know if that's a good way to start.

$\endgroup$
6
  • 3
    $\begingroup$ You are absolutely required to use induction to solve for one specific case? $\endgroup$ – Brevan Ellefsen Dec 7 '15 at 23:34
  • $\begingroup$ i have to use induction. Its a problem in the mathematical induction chapter. I cant just punch it in a calculator and solve it $\endgroup$ – al exx Dec 7 '15 at 23:36
  • 3
    $\begingroup$ Prove in general that $17^{4n}-1$ is divisible by $10$. Or prove that $n(n^4-1)$ is always divisible by $5$, and thus when $n$ is not divisible by $5$, $n^4-1$ is divisible by $5$. $\endgroup$ – Thomas Andrews Dec 7 '15 at 23:37
  • 2
    $\begingroup$ Thank you for the comment. Where is 17 ^ 4n coming from? $\endgroup$ – al exx Dec 7 '15 at 23:40
  • $\begingroup$ What i tried to do is what i said about and by n=k, then k becomes (k+1) i change 17 ^ 200 to 17^(20)^(10) and n = 17^20 so n^10 = 1. Then (k+1)^10 - 1 and then i foiled it out so it gives me k^10 + ..... + 10(k^2 +2k)^3 which is a multiple of 10. is that right? $\endgroup$ – al exx Dec 7 '15 at 23:42
8
$\begingroup$

Since it seems a bit strange to use induction to solve for particular case ($17^{200} - 1$), and it seems from your question that you want to see this solved via an inductive proof, let's use induction to solve a somewhat more general problem, and recover this particular example as a special case.

So, let's make the conjecture that $$4 \mid n \implies 10 \mid (17^n - 1).$$ This means we want to show 10 divides $17^{4k} - 1$ for all integers $k$. Now, the base case is $k = 1$ and we have $$ 17^{4k} - 1 = 17^4 - 1 = 83520 = 10 * 8352.$$ Indeed, the hypothesis holds in the base case.

Now, assume the statement is true for some integer $m$. We then have \begin{align*} &&17^{4m} - 1 &= 10 \cdot a &\text{for some } a \in \mathbb{Z} \\ \implies && 17^4 (17^{4m} - 1) &= 10 \cdot a \\ \implies && 17^{4m+1} - 83521 &= 10 \cdot a \\ \implies && 17^{4m+1} - 1 &= 10\cdot a + 83520 \\ \implies && 17^{4m+1} - 1 &= 10\cdot (a + 8352) \end{align*} Thus, 10 divides $17^{4m+1}$ if it divides $17^{4m}$; hence, we have shown that 10 divides $17^{4k}$ for every integer $k$.

Since 200 is a multiple of 4, the problem at hand is then solved as a special case of this theorem.

$\endgroup$
6
  • $\begingroup$ Ok that makes sense. I just didnt know if this way was the right approach but your example is the same as I was shown. Thank you for taking the time to write this up. $\endgroup$ – al exx Dec 7 '15 at 23:58
  • 1
    $\begingroup$ @alexx No problem. I hope a detailed example is helpful. Although, as you can see from the other answer, there are faster ways to prove this without using induction. $\endgroup$ – Bamboo Dec 7 '15 at 23:59
  • $\begingroup$ You can simplify the argument by noting that $17^2= 289 = 10a-1$ implies $17^4= 10b+1$. $\endgroup$ – lhf Dec 8 '15 at 0:05
  • $\begingroup$ Surely you mean $4m+4$ or $4(m+1)$ in your exponents. $\endgroup$ – Eckhard Dec 8 '15 at 9:47
  • 1
    $\begingroup$ Not that it matters to recover the special case in the actual question, but you only proved one direction of your $\iff$. $\endgroup$ – Steve Jessop Dec 8 '15 at 10:09
8
$\begingroup$

Consider a number with a $7$ in its units place. As we take powers of it, the units digit proceeds:

$$7, 9, 3, 1, 7, 9, 3, 1, \ldots$$

Notice that when raised to a power that is a multiple of $4$, such a number ends up with a $1$ in its units place. Since $17$ has a $7$ in its units place, and since $200$ is a multiple of $4$, we reason that the number $17^{200}$ must have a $1$ in its units place. Thus, $17^{200} - 1$ has a $0$ in its units place, i.e., is a multiple of $10$ as desired. QED.

$\endgroup$
3
  • 1
    $\begingroup$ A good proof (or demonstration, if one wants to be picky), but not an inductive one as the question required. However I do think this is good motivation for the step that is missing in several of the other answers, which is why one should try to prove $10 \vert (17^{4n} - 1)$ in the first place. $\endgroup$ – David Z Dec 8 '15 at 13:53
  • $\begingroup$ By the way, for those that aren't aware, the general method for proving divisibility in this way is called modular arithmetic. This solution considered the given number in modulo 10. $\endgroup$ – J.Gudal Dec 8 '15 at 16:42
  • 1
    $\begingroup$ @DavidZ Right: The OP indicated a lack of surety around "a good way to start." And so I hope this demonstration responds in that direction! Perhaps my QED is a bit heavy-handed; to turn this from a demonstration into a formal proof (in a course broaching induction) involves justification around where I simply wrote, "notice that..." One can use induction to do precisely this, which is what the OP's selected answer chose to do with its "conjecture." $\endgroup$ – Benjamin Dickman Dec 9 '15 at 2:58
6
$\begingroup$

$17^{200} - 1$ is clearly even and so it remains to prove that it is a multiple of $5$.

Now, $17^{200}= (15+2)^{200}=15a+2^{200}$. So it suffices to prove that $2^{200}-1$ is a multiple of $5$.

Indeed, $2^{200}=(2^{4})^{50}=16^{50}=(5b+1)^{50}=5c+1$.

$\endgroup$
3
  • $\begingroup$ Induction is in the binomial theorem, which is used twice. $\endgroup$ – lhf Dec 8 '15 at 0:00
  • $\begingroup$ this might be a stupid question but what does the a a, b and c stand for? Constants? I was thought with k and k+1 sorry for asking $\endgroup$ – al exx Dec 8 '15 at 0:03
  • 1
    $\begingroup$ $a,b,c$ are some integers whose exact values are immaterial to the argument. $\endgroup$ – lhf Dec 8 '15 at 0:04
6
$\begingroup$

We need to prove that for all $n$, $17^{4n} -1$ is divisible by 10.

Consider when n=1:

$17^{4} - 1 = (17^{2} - 1)(17^{2} +1)=(288)(290)$

this is obviously divisible by 10.

Assume for some integer k that $17^{4k} -1$ is divisible by 10.

Then $17^{4(k+1)} -1 =17^{4k+4} -1=(17^{4})(17^{4k}) -1 = (17^{4k} -1) + (17^{4} -1)(17^{4k}) = (17^{4k} -1) + (288)(290)(17^{4k}) $

And both parts of the last sum are divisible by 10 as required.

$\endgroup$
4
  • 1
    $\begingroup$ Or simply, $17^{4k}-1=(17^4-1)(\cdots)$ from $x^k-1=(x-1)(x^{k-1}+\cdots+x+1)$. $\endgroup$ – lhf Dec 8 '15 at 0:10
  • $\begingroup$ But that wouldn't require induction. The question specifically asked for induction. $\endgroup$ – J.Gudal Dec 8 '15 at 0:11
  • 1
    $\begingroup$ It does require induction to prove that $x^k-1=(x-1)(x^{k-1}+\cdots+x+1)$. $\endgroup$ – lhf Dec 8 '15 at 0:12
  • $\begingroup$ I assume they meant to prove the proposition directly with induction, rather than proving another theorem that would simplify the problem. $\endgroup$ – J.Gudal Dec 8 '15 at 0:14
4
$\begingroup$

Here is another proof that $k(k^4-1)$ is divisible by $10$, using some "fun" observations ;)

The base case is $2(2^4-1) = 30$, which is easily seen to be $3\cdot10$
Assume $k^5-k = 10 a$ for some $a \in \mathbb{Z}$ $$(k+1)^5-(k+1)$$ $$=\left(k^5+5k^4+10k^3+10k^2+5k+1\right)-(k+1)$$ $$=k^5+5k^4+10k^3+10k^2+5k-k$$ $$=(k^5-k)+5k^4+10k^3+10k^2+5k$$ $$10a+5(k^4+2k^3+2k^2+k)$$ Since an odd times and odd is odd and an even times and even is even, so $k^4+k$ is either $(2k+1)+(2r+1) = 2(r+k+1)$ or $2n+2r=2(n+r)$ and thus must be even, so we rewrite the above as $$10a+5(2(k^3+k^2+p)) = 10(a+k^3+k^2+p)$$ Examining $17^{200}-1$, we realize that $17^{200}-1$ must be divisible by $10$ if $17^{50}$ is not. $17^{50}$ has no factors of $10$ though (as it is prime), so $17^{200}-1$ must be divisible by $10$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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