2
$\begingroup$

How would you go about showing that (for $a \in \mathbb{Z}$) $x^{2}+a^{2}$ divides $x^{p-1}-1$, modulo a prime $p$, where $p\equiv 1 \mod 4$?

My first thought was to use the fact that there exists a $u$ such that $u^{2}\equiv -1 \mod p$ and factor to get $(x+ua)(x-ua)\equiv x^2 + a^2 \mod p$. Though, I can't seem to relate that to $x^{p-1}-1$.

$\endgroup$
  • $\begingroup$ Did you mean for $\gcd(a,p) = 1$? $\endgroup$ – Hurkyl Apr 20 '13 at 21:04
1
$\begingroup$

Hint $\ $ By little Fermat, $\rm\,\pm ua \:$ are roots of $\rm\:f(x) = x^{p-1}\!-1\:$ hence, by the Factor Theorem, $\rm\:f(x),\:$ is divisible by $\rm\:x\!-\!ua,\:$ and $\rm\:x\!+\!ua,\:$ so also by their product $\rm\:x^2\!+a^2,\:$ since the roots are distinct (why?)

Remark $\ $ Note that the last inference depends crucially on $\rm\:p\:$ being prime. It may fail otherwise, e.g. $\rm\: mod\ 8\!:\ f(x) = x^2\!-1\:$ has roots $\rm\:x = 1,3\:$ hence $\rm\:f(x)\:$ is divisible by both $\rm\:x-1\:$ and $\rm\:x-3,\:$ but it is not divisible by their product.

$\endgroup$
  • 1
    $\begingroup$ This is less of a hint, and more of a complete solution with a minor point omitted to leave some busy work for the OP. $\endgroup$ – Hurkyl Apr 20 '13 at 21:03
  • $\begingroup$ @Hurkyl The omitted point is far from "minor" or "busy work", see the Remark. $\endgroup$ – Math Gems Apr 20 '13 at 21:36
  • $\begingroup$ What if a and p are not coprime? $\endgroup$ – user70363 Apr 21 '13 at 22:42
  • $\begingroup$ @user70363 If $\rm\,p\mid a\,$ then $\rm\:mod\ p\!:\ x^2\!+a^2\equiv x^2,\:$ which does not divide $\rm\,f(x) = x^{p-1}\!-1\:$ since $\rm\:f(0) = -1\not\equiv 0.\ \ $ $\endgroup$ – Math Gems Apr 21 '13 at 23:11
1
$\begingroup$

Hint: by Fermat's little theorem, we have $x^{p-1}\equiv 1\pmod{p}$.

$\endgroup$
  • $\begingroup$ One needs more than that to give a complete proof - see my answer. E.g does your proposed proof work in non-domains? If not, where did you use that hypothesis? $\endgroup$ – Math Gems Apr 20 '13 at 20:52
  • 1
    $\begingroup$ @MathGems: That's why it's called a "hint", rather than called "a complete proof".... $\endgroup$ – Hurkyl Apr 20 '13 at 20:59
  • $\begingroup$ @Hurkyl Imo hints should not omit mention of points that are critical to the success of the proof. Hence my comment. $\endgroup$ – Math Gems Apr 20 '13 at 21:29
0
$\begingroup$

If prime $p>2, p$ is odd,

$x^{p-1}=(x^2)^{\frac{p-1}2}=(-a^2)^{\frac{p-1}2}$ (Putting $x^2=-a^2$)

$x^{p-1}=(-1)^{\frac{p-1}2}\cdot a^{p-1}\equiv (-1)^{\frac{p-1}2}\pmod p$ using Fermat's little theorem, $a^{p-1}\equiv1\pmod p$

But $x^{p-1}\equiv1\pmod p$

$\implies (-1)^{\frac{p-1}2}\equiv1\pmod p$

If $\frac{p-1}2$ is odd, if $\frac{p-1}2=2k+1,p=4k+3\equiv3\pmod 4$ for some integer $k,$

$(-1)^{\frac{p-1}2}\equiv-1\pmod p\implies -1\equiv1\pmod p\implies 2$ divides $p$, but $p$ is odd

Similarly, test when $\frac{p-1}2$ is even

$\endgroup$

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.