# Math induction problem with large numbers

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.

• You are absolutely required to use induction to solve for one specific case? – Brevan Ellefsen Dec 7 '15 at 23:34
• i have to use induction. Its a problem in the mathematical induction chapter. I cant just punch it in a calculator and solve it – al exx Dec 7 '15 at 23:36
• 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$. – Thomas Andrews Dec 7 '15 at 23:37
• Thank you for the comment. Where is 17 ^ 4n coming from? – al exx Dec 7 '15 at 23:40
• 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? – al exx Dec 7 '15 at 23:42

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.

• 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. – al exx Dec 7 '15 at 23:58
• @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. – Bamboo Dec 7 '15 at 23:59
• You can simplify the argument by noting that $17^2= 289 = 10a-1$ implies $17^4= 10b+1$. – lhf Dec 8 '15 at 0:05
• Surely you mean $4m+4$ or $4(m+1)$ in your exponents. – Eckhard Dec 8 '15 at 9:47
• Not that it matters to recover the special case in the actual question, but you only proved one direction of your $\iff$. – Steve Jessop Dec 8 '15 at 10:09

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.

• 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. – David Z Dec 8 '15 at 13:53
• 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. – J.Gudal Dec 8 '15 at 16:42
• @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." – Benjamin Dickman Dec 9 '15 at 2:58

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

• Induction is in the binomial theorem, which is used twice. – lhf Dec 8 '15 at 0:00
• 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 – al exx Dec 8 '15 at 0:03
• $a,b,c$ are some integers whose exact values are immaterial to the argument. – lhf Dec 8 '15 at 0:04

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.

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

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