$x^4 = -1$ (mod $p$) implies p = 1 mod 8

1,423

Solution 1

$x^4\equiv -1\pmod{p}\iff \text{ord}_p(x)=8$ (why?).

$x^k\equiv 1\pmod{p}\iff \text{ord}_p(x)\mid k$ (why? hint: for contradiction, let $k=\text{ord}_p(x)h+r$ with $0<r<\text{ord}_p(x)$ and get that $x^r\equiv 1\pmod{p}$, contradiction).

And remember Fermat's Little theorem. This is all you need to know.

Solution 2

By FLT,$$x^{p-1}\equiv1\pmod{p}$$

$$x^8\equiv 1\pmod{p}\implies 8\mid p-1\implies p\equiv1\pmod{8}$$

The case where $p-1 \mid 8$ is impossible because $p\neq 9$ so we need to check only $p=2,3,5$ where,

$$x^4\equiv 1\pmod{2,3,5}$$

so not possible.

(The $x\mid p$ and $p\mid x$ case is easily eliminated so not considered)

Share:
1,423

Related videos on Youtube

Ludwwwig
Author by

Ludwwwig

Updated on August 01, 2022

Comments

  • Ludwwwig
    Ludwwwig over 1 year

    Let $p$ be an odd prime. Show that

    $x^4 = -1$ (mod $p$)

    has a solution if and only if $\Leftrightarrow p = 1$ (mod $8$)

    • caffeinemachine
      caffeinemachine almost 8 years
      For some $x$ or for all $x$?
    • Ludwwwig
      Ludwwwig almost 8 years
      I have now changed my question; for some x.
  • Mathmo123
    Mathmo123 almost 8 years
    You must be missing some conditions from your argument. $(-1)^8 \equiv 1 \pmod 3$ for example, but $3\not\equiv 1\pmod 8$.
  • cr001
    cr001 almost 8 years
    You are right, actually it can be $p-1\mid 8$ as well, I will add that case in the proof.
  • lhf
    lhf almost 8 years
    This is one direction only.
  • Mathmo123
    Mathmo123 almost 8 years
    @cr001 in which case, take $1^8 \equiv 1 \pmod 3$. But $(p-1)\nmid 1$ and $p\not\equiv 1 \pmod 8$. For your argument to work, you need to know that $x$ has order $8$, which it does in this case. But as written this is wrong.
  • Ludwwwig
    Ludwwwig almost 8 years
    For the other direction, let $-1 = r^k$, r is a primitive root. Since $r^(k(p-1)/4) = 1$ mod 8, we get that (p-1) | k/4 (p-1). Hence k = 4j. If we let x = r^j we have that x^4 = -1.
  • user236182
    user236182 almost 8 years
    You must know $\text{ord}_p(x)=8$ in order to conclude $8\mid p-1$. And it's not true that $x^k\equiv 1\pmod{p}$ implies either $k\mid p-1$ or $p-1\mid k$.