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:

  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Dec 5 '19 at 21:21
  • 3
    $\begingroup$ 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$. $\endgroup$ – Peter Dec 5 '19 at 21:26
  • $\begingroup$ Is the question about proving the lemma? $\endgroup$ – rtybase Dec 5 '19 at 21:42
  • 2
    $\begingroup$ @TrevorGunn I see. Well, Peter, technically, proved it. $\endgroup$ – rtybase Dec 5 '19 at 21:47
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Dec 6 '19 at 0:55

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.