Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

Question

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any secret trick that I'm unaware of?

Answer 1

For the sake of familiarity I will use $p$ instead of $a$.

Suppose to the contrary that $p$ does not divide $b$. Then $p$ and $b$ are relatively prime. Thus by the Bezout Identity there exist integers $s$ and $t$ such that $ps+bt=1$. Then $b^nt^n=(1-ps)^n$. Expand using the binomial theorem. Since $p$ divides $b^n$, and also divides every term in the expansion of $(1-ps)^n$ except $1$, we conclude that $p$ divides $1$, which is impossible.

Answer 2

Let $b = k + ma$. ($0 \le k < a; m \in \mathbb Z$). $b^n = (k + ma)^n = k^n + \sum_{i = 1}^n{n \choose k}k^i(ma)^{n - i}$

$a | \sum_{i = 1}^n{n \choose k}k^i(ma)^{n - i}$ and $a|b^n$ so $a|k^n$. But $k < a$ and $a$ is prime so $a$ and $k$ have no factors in common if $k > 0$ so $a$ and $k^n$ will have no factors in common if $k > 0$ so $k = 0$.

So $b = ma$ and $a|b$.