$p\equiv1\pmod 8$. Solve $x^4\equiv-1\pmod p$

Question

Here is a very elegant result proven using Wilson's theorem:

Theorem. $p\equiv1\pmod4\iff x^2\equiv-1\pmod p$ is solvable. In particular, $$x\equiv\Big(\frac{p-1}{2}\Big)!$$is a solution. $-(*)$

Proof.
'$\Rightarrow$': $\bigg(\Big(\frac{p-1}{2}\Big)!\bigg)^2\equiv 1*2*\dots*\frac{p-1}{2}*\frac{p-1}{2}*\dots*2*1\equiv(-1)^{(p-1)/2}*1*2*\dots*\frac{p-1}{2}*(-\frac{p-1}{2})*\dots*(-2)*(-1)\equiv(-1)^{(p-1)/2}*1*2*\dots*\frac{p-1}{2}*\frac{p+1}{2}*\dots*(p-2)*(p-1)\equiv (p-1)!\equiv-1\pmod p$

'$\Leftarrow$': If so, then $x$ is of order $4$ in $\Bbb Z^*_p$. By Lagrange's theorem, $4$ divides $p-1$ the order of $\Bbb Z^*_p$. Thus $p\equiv1\pmod 4$

Afterall, $\Big(\frac{p-1}{2}\Big)!$ and $\bigg(\Big(\frac{p-1}{2}\Big)!\bigg)^3$ are the elements of order $4$ in $\Bbb Z^*_p$

Out of curiosity, I want to investigate the semi-direct product $\Bbb Z_p\rtimes\Bbb Z_8$. Assume $p\equiv1\pmod 8$. $x^4\equiv-1\pmod p$ has the following solutions for different $p$:

p = 17, x ≡ 2, 8, 9, 15
p = 41, x ≡ 3, 14, 27, 38
p = 73, x ≡ 10, 22, 51, 63
p = 89, x ≡ 12, 37, 52, 77
p = 97, x ≡ 33, 47, 50, 64
p = 113, x ≡ 18, 44, 69, 95
p = 137, x ≡ 10, 41, 96, 127
p = 193, x ≡ 9, 43, 150, 184
p = 233, x ≡ 12, 97, 136, 221
p = 241, x ≡ 8, 30, 211, 233
p = 257, x ≡ 4, 64, 193, 253
p = 281, x ≡ 60, 89, 192, 221
p = 313, x ≡ 5, 125, 188, 308
p = 337, x ≡ 85, 111, 226, 252
p = 353, x ≡ 70, 116, 237, 283

I have no clue how to express one of the solutions of $x^4\equiv-1\pmod p$ in terms of $p$. Note that if $a$ is one of them, then so is $a^3$, $a^5$ and $a^7\mod p$ because $\Bbb Z^*_p$ is cyclic. I've tried out something like $\frac{p-1}{4}!+1$, and even $\frac{p-1}{8}!$. Obviously, those were just plain guess. The result $(*)$ is elegant. I wonder if the result for $x^4\equiv-1\pmod p$ if $p\equiv1\pmod 8$ would be equally elegant. Can somebody derive the general solution to this just like in $(*)$?

P.S. As I'd expect, this question would be favourited in just a few minutes. I am however surprised that it has NEVER been asked before.

Answer 1

I cooked up the following (most certainly known) generalization of the method you used to find a solution of $x^2\equiv-1\pmod p$. It is largely useless for calculations, but I will share it with you anyway.

Theorem. Assume that a prime $p\equiv1\pmod {2n}$, where $n$ is an even number. Let $G\le \Bbb{Z}_p^*$ be a subgroup of order $n$. Let $D$ be a set of representatives of cosets of $G$ in $\Bbb{Z}_p^*$. Let $S$ be the product of elements of $D$. Then $$S^n\equiv-1\pmod p.$$

Proof. Because $G$ has an even number of elements we easily see that $$p(G)=\prod_{g\in G}g\equiv-1\pmod p.$$ This is because $-1$ is the only element of order two (see e.g. here). Therefore the product of the elements of the coset $dG, d\in D,$ is $p(dG)=d^np(G)=-d^n$.

But, by Wilson's theorem $p(\Bbb{Z}_p^*)=-1$. Because $\Bbb{Z}_p^*$ is the disjoint union of the cosets $dG, d\in D$, we thus arrive at $$ -1=p(\Bbb{Z}_p^*)=\prod_{d\in D}p(dG)=\prod_{d\in D}(-d^n)=(-1)^{|D|}S^n. $$ Because we assumed that $|D|=(p-1)/|G|$ is an even number, we see that $S^n\equiv-1$. QED.

Example 1. Let $G=\{+1,-1\}$. Assume that $p\equiv1\pmod4$. In this case the coset $dG=\{d,-d\}=\{d,p-d\}$, so we can use $1,2,\ldots,(p-1)/2$ as the set of representatives of cosets. Therefore $S=((p-1)/2)!$, and we rediscover your solution, as the Theorem tells us that $S^2\equiv-1\pmod4$.

How to apply this to your problem? Assume that $p\equiv1\pmod 8$. We can take advantage of the solution $g=((p-1)/2)!$. Let us use the group of powers of $g$: $$ G=\{1,g,g^2,g^3\}=\{1,g,-1,-g\}. $$ It has $n=4$ elements and $8\mid (p-1)$, so our Theorem kicks in, and says that the product $S$ of elements of $D$ is a solution of the congruence $$ S^n=S^4\equiv-1\pmod p. $$ The catch is, unfortunately, that with this harder to control group $G$ it is more difficult to describe a set of coset representatives. One way of doing that is to pick the smallest element from each coset, but this doesn't play out very nicely - see below.

Example 2. Let $p=41$, so $8\mid (p-1)$. Because $20!\equiv9\pmod{41}$ we set $g=9$. Therefore $$ G=\{1,9,81=-1,729=-9\}=\{1,9,40,32\}. $$ The cosets are $$ \begin{array}{r|c} d&dG\\ \hline 1&\{1,9,32,40\}\\ 2&\{2,18,23,39\}\\ 3&\{3,14,27,38\}\\ 4&\{4,5,36,37\}\\ 6&\{6,13,28,35\}\\ 7&\{7,19,22,34\}\\ 8&\{8,10,31,33\}\\ 11&\{11,17,24,30\}\\ 12&\{12,15,26,29\}\\ 16&\{16,20,21,25\} \end{array} $$ So we skipped $d=5$ because $5\in 4G$, and similarly skipped $9,10,13,14,15$ because those numbers had also already appeared in the earlier cosets. Anyway, all the numbers $1,2,\ldots,p-1=40$ appear in these ten cosets. Our Theorem tells us to look at $$ S=1\cdot2\cdot3\cdot4\cdot6\cdot7\cdot8\cdot11\cdot12\cdot16=17031168\equiv14\pmod{41}. $$ As a final check we can then verify that $$ S^2=196\equiv32\pmod{41} $$ and $$ S^4\equiv32^2\equiv(-9)^2=81\equiv-1\pmod{41}. $$

Remarks.

• The Theorem works just as well, when $|G|$ is odd. Then $p(G)=1$, and there are no problems with signs. Only when $2\mid |G|$ do we need to make sure that the number of cosets is also even.
• The existence of primitive roots implies that $G$ is necessarily cyclic. However, the proof works without that piece of information. It suffices that $-1$ is the only element of order two. And this follows from the observation that $x^2\equiv1\pmod p$ implies $p\mid (x^2-1)=(x-1)(x+1)$, so $x\equiv\pm1$.

Answer 2

There is no general solution expressible in terms of $p$, because the result depends on the value of primitive roots, which are not generally predictable (except that the smallest such is a prime). You are effectively looking for the four elements of order $8$, which are those with some primitive root $g$ raised to the powers $\{k,3k,5k,7k\}$ where $k=(p-1)/8$.

For example, $3$ is a primitive root $\bmod 281$ and thus $3^{35}\equiv 60,$ $3^{105}\equiv 192,$ $3^{175}\equiv 221$ and $3^{245}\equiv 89$ are the required values.

Answer 3

The fact that there is a solution to $$ x^4 + 1 \equiv 0 \pmod p$$ when $p \equiv 1 \pmod 8$ is due to Gauss.

I will check, but I don't particularly expect any closed form for one of the roots. Admittedly, I have paid little attention to the use of factorials in this sort of problem. One may find the squarerrot of one of the square roots of $-1$ by the method of Tonelli-Shanks, or the one that starts with C.

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

https://en.wikipedia.org/wiki/Cipolla's_algorithm

https://en.wikipedia.org/wiki/Pocklington's_algorithm