Wednesday, June 8, 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...