How to prove the equivalence of these two equations in modular arithmetics?

Question

We have to prove that $$ x^4 \equiv -1 \pmod p $$ iff $$ p \equiv 1 \pmod 8 $$where $p$ is an odd prime.

I am stuck at proving that $$ \gcd(4, p - 1) \mid (p-1)/2 $$ is equivalent to $$ 8 \mid (p - 1). $$

Answer 1

It's fairly obvious, to me, the question is not intended for you to prove it for all $x \neq 0 \pmod p$ since, for $x = 1$, you have $x^4 = 1$. This means $x^4 \equiv -1 \pmod{p}$ can only be true for the prime $p = 2$.

Instead, I believe a more appropriate wording of what the question intended is that for odd prime $p$, there exists an integer $x$ where $x^4 \equiv -1 \pmod{p} \iff p \equiv 1 \pmod{8}$.

For the $\implies$ direction, you have the right idea, as also indicated in the question comments. Squaring gives

$$x^8 \equiv 1 \pmod{p} \tag{1}\label{eq1A}$$

This means the multiplicative order of $x$ modulo $p$ must divide $8$. Since the only smaller factors of $8$ are $1$, $2$ and $4$, where $x$ to any of those powers can't be congruent to $1$, you get $8$ must be the multiplicative order of $x$ modulo $p$.

Since the multiplicative order must divide the Euler's totient function value, which is $p - 1$ for primes, means you have

$$8 \mid p - 1 \implies p \equiv 1 \pmod{8} \tag{2}\label{eq2A}$$

For the $\impliedby$ direction, since $p$ is a prime, there is an element $g$ which is a primitive root and, thus, also generator of the multiplicative group of non-zero remainders. This means there exists an integer $1 \lt j \lt p - 1$ where

$$g^{j} \equiv -1 \pmod{p} \implies g^{2j} \equiv 1 \pmod{p} \tag{3}\label{eq3A}$$

As $g$ is a primitive root, this means its multiplicative order is $p - 1$ so $p - 1 \mid 2j$. However, $j \lt p - 1 \implies 2j \le 2(p - 1)$, means

$$2j = p - 1 \tag{4}\label{eq4A}$$

Since $p \equiv 1 \pmod{8}$, there exists a positive integer $k$ such that $p = 8k + 1$. Using this in \eqref{eq4A} gives

$$2j = 8k \implies j = 4k \tag{5}\label{eq5A}$$

Thus, \eqref{eq3A} gives

$$g^{4k} \equiv -1 \pmod{p} \implies (g^k)^4 \equiv -1 \pmod{p} \tag{6}\label{eq6A}$$

You therefore have $x \equiv g^k \pmod{p}$ satisfying $x^4 \equiv -1 \pmod{p}$.