Math induction problem with large numbers

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.