Friday, July 15, 2016

divisibility - Prove that $5mid 8^n - 3^n$ for $n ge 1$


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.


Answer



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



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...