9
$\begingroup$

I am looking for a hint on this problem:

Suppose $a,b\in\mathbb{N}$ such that $\gcd\{ab,p\}=1$ for a prime $p$. Show that if $a^p\equiv b^p \pmod p$, then we have: $$a^p \equiv b^p \pmod {p^2}.$$

I have noted that $a,b$ are necessarily coprime to $p$ already, and Fermat's little theorem ($x^p\equiv x \pmod p$), but I do not see how I should apply it in this case if at all.

Any hints are appreciated!

$\endgroup$
  • $\begingroup$ Do you mean $\gcd(ab,p)=1$? $\endgroup$ – mysatellite Dec 18 '15 at 3:44
  • 1
    $\begingroup$ Hint: prove first that $a \equiv b \mod p$. The condition $(ab,p) = 1$ is useless, and $a$ and $b$ can be any integers. $\endgroup$ – darij grinberg Dec 18 '15 at 3:44
  • $\begingroup$ Oh yes, I will edit that in a second, it is just short form that a professor had used. $\endgroup$ – anakhro Dec 18 '15 at 3:44
  • $\begingroup$ @darijgrinberg It follows from Fermat's little theorem easily that $a\equiv b$ (mod p). However, I am still stuck on where that leads me. Is there another tiny nudge you can give me in the right direction? $\endgroup$ – anakhro Dec 18 '15 at 3:47
10
$\begingroup$

Fermat's Little theorem should help you show $a\equiv b(\text{mod }p)$, at which point you have $a=b+pk$ for some $k\in\mathbb{Z}$. An application of the binomial theorem from here could give you the result you seek.

$\endgroup$
  • $\begingroup$ Would that be an application of the binomial theorem to $(a-b)^p$, by any chance? $\endgroup$ – anakhro Dec 18 '15 at 4:05
  • 3
    $\begingroup$ I think it might be easier to apply it to $a^p$, but you would get the same result using $(a-b)^p$. $\endgroup$ – Mb123 Dec 18 '15 at 4:06
  • $\begingroup$ Thank you, that is sufficient! $\endgroup$ – anakhro Dec 18 '15 at 4:08
  • 6
    $\begingroup$ Alternatively, $a^p - b^p = \left(a-b\right)\left(a^{p-1} + a^{p-2} b + \cdots + b^{p-1}\right)$. Now, you only need to check that the second parenthesized factor is divisible by $p$. $\endgroup$ – darij grinberg Dec 18 '15 at 4:22
  • $\begingroup$ @darijgrinberg I can't see any relatively straightforward way of doing so? $\endgroup$ – Steven Stadnicki Dec 18 '15 at 4:23
4
$\begingroup$

You could generalize this further. Here is one of the Lifting the Exponent Lemmas (LTE):

Define $\upsilon_p(a)$ to be the exponent of the largest prime power of $p$ that divides $a$.

If $a,b\in\mathbb Z$, $n\in\mathbb Z^+$, $a\equiv b\not\equiv 0\pmod{p}$, then $$\upsilon_p\left(a^n-b^n\right)=\upsilon_p(a-b)+\upsilon_p(n)$$

In your case, by Fermat's Little theorem $a^p\equiv b^p\not\equiv 0\pmod{p}\iff a\equiv b\not\equiv 0\pmod{p}$, therefore $$\upsilon_p\left(a^p-b^p\right)=\upsilon_p(a-b)+\upsilon_p(p)=\upsilon_p(a-b)+1$$

Therefore $p^2\mid a^p-b^p$.

$\endgroup$
  • $\begingroup$ I like this a lot! Thanks! $\endgroup$ – anakhro Dec 19 '15 at 3:24
  • $\begingroup$ The LTE Lemma I cited only holds for odd $p$. I only proved your problem for odd primes $p$. $\endgroup$ – user236182 Dec 26 '15 at 5:57

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.