4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ To find an element of order $8$ in $\Bbb{Z}_p^*$ all you need is $i=\sqrt{-1}$ (which you have already) and $\sqrt2$. By the recipe familiar to all of us from complex roots of unity $$u=\frac{1+i}{\sqrt2}$$ has order eight. Run one of the algorithms suggested by Will Jagy to find $\sqrt2$, and you are done. $\endgroup$ – Jyrki Lahtonen Aug 19 '17 at 5:31
  • $\begingroup$ @JyrkiLahtonen What do you mean by 'dividing' numbers in modular arithmetic $\endgroup$ – user441558 Aug 19 '17 at 5:44
  • $\begingroup$ I dare not guess whether the non-deterministic algorithm of calculating powers $a^{(p-1)/8}$ for random $a$ (succeeds with probability one half per round) might be faster than calculating $\sqrt2$ by one of those methods. $\endgroup$ – Jyrki Lahtonen Aug 19 '17 at 5:45
  • $\begingroup$ $\Bbb{Z}_p$ is a field so you can divide the usual way of multiplying with the inverse. So if you have $c=\sqrt2$, then run the generalized Euclid's algorithm to find $d$ such that $cd\equiv1\pmod p$. Then dividing by $c$ means the same thing as multipliying by $d$. $\endgroup$ – Jyrki Lahtonen Aug 19 '17 at 5:47
  • 2
    $\begingroup$ @WillJagy I don't remember any such methods either. Only when $p\equiv7\pmod8$, when $2$ is a quadratic residue, and we can use $2^{(p-1)/2}\equiv1$ implying that $a=2^{(p+1)/4}$ satisfies $$a^2=(2^{(p+1)/4})^2=2^{(p+1)/2}=2\pmod p.$$ Basically $2$ has odd order, so squaring is an automorphism of $\langle 2\rangle$. $\endgroup$ – Jyrki Lahtonen Aug 19 '17 at 16:23
0
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ For $d=3$, $dG=\{3,14,27,38\}$ though. $\endgroup$ – user441558 Aug 21 '17 at 1:24
  • $\begingroup$ And this is a nice generalisation of the $x^2\equiv-1$ thing! $\endgroup$ – user441558 Aug 21 '17 at 1:27
  • $\begingroup$ Thanks for catching that typo. Fixing. $\endgroup$ – Jyrki Lahtonen Aug 21 '17 at 5:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not familiar with the concept of primitive roots. However can you explain why is there a general solution expressible in terms of $p$ for $x^2\equiv-1\pmod p$, if not for $x^4\equiv-1\pmod p$? $\endgroup$ – user441558 Aug 19 '17 at 3:22
  • 1
    $\begingroup$ Hah, apparently Gauss had an answer but I'm not ashamed of not being as clever as Gauss. I will say though that the use of Wilson's Theorem generally doesn't scale well, due to multiplying lots of different numbers (as opposed to high powers of a single number which can be efficiently calculated.. Primitive roots are worth learning about, I added a link. $\endgroup$ – Joffan Aug 19 '17 at 4:22
  • $\begingroup$ Yea, now that I know the primitive roots are the generators of the multiplicative group of intergers modulo something. And I agree that Wilson's theorem doesn't scale well. But maybe if we're lucky, we may find a general sol. with or without using factorials? $\endgroup$ – user441558 Aug 19 '17 at 4:47
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yeah of course if $p\equiv1\pmod 8$, $x^4\equiv-1\pmod p$ is solvable simply because $\Bbb Z^*_p$is cyclic, so it must contain an element of order $8$. In fact there are $4$ of them. $\endgroup$ – user441558 Aug 19 '17 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy