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

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?

• Do you know the theorem that if $p$ is prime, and $p\mid ab$, then $p\mid a$ or $p\mid b$? If you do, you can use it to prove your result by induction on $n$. Feb 2, 2016 at 6:10
• Hello, thanks that's a great idea. However, this question is for an assignment and we were specifically told to use the binomial theorem.
– lsy
Feb 2, 2016 at 6:13

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.

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

• Hello did you mean $a\mid b^n$ instead of $a\mid b^2$? Also, thanks! This looks right and it's concise.
– lsy
Feb 2, 2016 at 7:28
• Did you mean did I mean "$a |k^n$ instead of $a|k^2$" instead of "$a |b^n$ instead of $a|b^2$"? :) Yes, yes I did. Feb 2, 2016 at 14:38