# When does $p^2$ divide $an^k + bp$?

In the ongoing effort of dealing with abstract duplicates. This question is about the lemma:

Lemma Let $$k \ge 2$$, $$p$$ prime and $$a$$ coprime to $$p$$. Then $$p^2\!\mid a n^k+ bp\iff p\mid n,b.$$

This lemma answers the following kinds of questions:

• The second claim in blue can be seen easily. $x$ must be divisible by $7$, but then, $7^n-x^2$ is divisible by $49$, if $n>1$ holds. – Peter Dec 5 '19 at 21:21
• The lemma is not difficult either. Since $a$ is not divisble by $p$, $n$ must be dividible by $p$. This forces $n^k$ to be divisble by $p^2$ , hence $bp$ must be divisible by $p^2$, forcing that $b$ is divisible by $p$. – Peter Dec 5 '19 at 21:26
• Is the question about proving the lemma? – rtybase Dec 5 '19 at 21:42
• @TrevorGunn I see. Well, Peter, technically, proved it. – rtybase Dec 5 '19 at 21:47
• @rtybase To clarify, a proof of the Lemma was already posted last month in one of the other linked questions, but some users objected to using that more specific question as an (abstract) dupe target. – Bill Dubuque Dec 6 '19 at 0:55

## 1 Answer

Lemma $$\, \ p^2\!\mid a n^k+ bp\iff p\mid n,b,\$$ if $$\ \color{#0a0}{k\ge 2}\,\$$ & $$\ a\,$$ is $$\rm\color{#90f}{coprime}$$ to $${\rm\color{#c00}{prime}}\ p$$ (or $${\rm\color{#c70}{squarefree}}\ p$$)

Proof $$\ \ (\Leftarrow)\ \$$ Clear by $$\,p\mid b,n\,\overset{\times\, p}\Rightarrow\,p^2\mid bp, n^{\color{#0a0}k}_{\phantom{|_{|_.}}}$$ and basic divisibility laws.
$$\ (\Rightarrow)\$$ $$\,p\mid an^k\! + bp\overset{\color{#90f}{(a,p)=1}}\Longrightarrow\! p\mid n^k\color{#c00}{\overset{\rm EL}\Rightarrow}\, p\mid n\,$$ $$\overset{\color{#0a0}{k\,\ge\, 2}}\Longrightarrow\,p^2\mid n^k\Rightarrow p^2\mid pb\,\Rightarrow\,p\mid b$$

using basic divisibility laws, and $$\,\color{#c00}{\rm EL}$$ = Euclid's Lemma.

Remark  It also holds true for $${\rm\color{#c70}{squarefree}}\:p\,$$ because they are precisely those integers satisfying the key middle inference, i.e. $$\ p\mid n^k\color{#c00}\Rightarrow\,p\mid n,\,$$ for all integers $$\,n$$.