3
$\begingroup$

I have that $$5\mid 8^n - 3^n$$

The first thing I tried is vía Induction:

It is true for $n = 1$, then I have to probe that it's true for $n = n+1$

$$5 \mid 8(8^n -3^n)$$ $$5 \mid 8^{n+1} -8\cdot3^n$$ $$5 \mid 3(8^{n+1} -8\cdot3^n)$$ $$5 \mid 3\cdot8^{n+1} -8\cdot3^{n+1}$$

After this, I don't know how to continue. Then I saw an example about a property: $$(a+b)^n = am + b ^ n$$ with $m = a + 2b$ or the number it represents.

$$5 \mid 8^n -3^n$$ $$5 \mid (5+3)^n -3^n)$$ $$5 \mid 5m + 3^n - 3^n)$$ $$5 \mid 5m$$

So, $d \mid a$ only if $a = kd$. From this I get that $5 \mid 5 m$.

My questions:

1) Is the exercise correct?

2) Could it have been resolved via method 1?

Thanks a lot.

$\endgroup$
8
$\begingroup$

For induction, you have

$$\begin{align}8^{n+1} - 3^{n+1} &= 8\cdot 8^n - 3\cdot3^n\\&= 3(8^n - 3^n) + 5\cdot8^n\end{align}$$

Note that the first term must be divisible by $5$ because $8^n-3^n$ is divisie by $5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I dont get how you reach the second line $\endgroup$ – JorgeeFG May 29 '16 at 3:31
  • $\begingroup$ Expanding the second line gives the previous expression - it is really just splitting up the coefficient of $8^n$. $\endgroup$ – Yiyuan Lee May 29 '16 at 4:28
8
$\begingroup$

Hint: Use the identity $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}).$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is new for me, where can I see more? How is it named? $\endgroup$ – JorgeeFG Sep 28 '15 at 18:41
4
$\begingroup$

Note that $8\equiv 3 \pmod5$, so that $8^n \equiv 3^n \pmod5$.

Therefore, $8^n - 3^n \equiv 3^n - 3^n \equiv 0 \pmod5$ so that $5|8^n - 3^n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, I'm also seeing this, so it is very useful to know how to resolve with congruence $\endgroup$ – JorgeeFG Jun 2 '16 at 20:51
3
$\begingroup$

By the binomial theorem, $8^n=(5+3)^n=5a+3^n$.

| cite | improve this answer | |
$\endgroup$

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