If $i = \sqrt{(-1)} \bmod p$, $p$ prime, does not exist, then we can form numbers of the form $a+b i \bmod p$ with multiplicative order $p^2 - 1$. How often do these numbers occur modulo $p$? In other words, how many complex values of the form $a+b i \bmod p$, where $a$ and $b$ are taken from $\mathbb{Z} /p \mathbb{Z}$ have multiplicative order $p^2-1$?


As Joanpemo points out, I'm looking for the number of elements of multiplicative order $p^2 - 1$ in the field $\mathbb{F}_{p^2}$ with $p \equiv 3 \bmod 4$, and $p$ prime.

  • $\begingroup$ I find the wording a little confusing. Your first words mean "If $\;-1\;$ is not a quadratic residue modulo some prime $\;p\;$ , then we..."? $\endgroup$ – DonAntonio May 26 '16 at 20:06
  • $\begingroup$ And where are we looking for multiplicative order equal to $\;p^2-1\;$ ? In what ring, field,...? $\endgroup$ – DonAntonio May 26 '16 at 20:08
  • $\begingroup$ @Joanpemo: Both components $a$ and $b$ are modulo $p$. I look for a prime $p$ where the imaginary essentially does not exist. For example, $2^2 \equiv -1 \bmod 5$, so the imaginary unit essentially exists in this ring. I look for rings where the imaginary does not exist. This is I believe a two-valued ring. In other words, we have the complexes modulo a prime $p$. I'm not sure exactly how to describe it. It may be $\mathbb{C} /p \mathbb{C}$. It's the complexes, where both components are taken modulo a prime $p$. $\endgroup$ – Matt Groff May 26 '16 at 20:44
  • $\begingroup$ The reason I'm looking for complex "rings", as I guess they'd be called, are because I can get a ring of large size, where the components (real and imaginary) are small. $\endgroup$ – Matt Groff May 26 '16 at 20:45
  • $\begingroup$ Well, we can say the following: $\;-1\;$ is a quadratic residue modulo some prime $\;p\;$ iff $\;p=1\pmod 4\;$ , so you're looking forward to work with some prime $\;p=3\pmod 4\;$ , like $\;p=7,11,23\;$ , etc. Now, in the prime field $\;\Bbb F_p\cong\Bbb Z/p\Bbb Z\;$ , the polynomial $\;x^2+1\in\Bbb F_p[x]\;$ is irreducible, so you can talk of the field extension $\;\Bbb F_p[\sqrt{-1}]\;$ of degree two of $\;\Bbb F_p\;$ , which itself is the field $\;\Bbb F_{p^2}\;$ with $\;p^2\;$ elements. I'm not sure though if you can handle this algebraic mumbling so far... $\endgroup$ – DonAntonio May 26 '16 at 21:07

If we're talking of the field $\;\Bbb F_{p^2}\;$ , then the multiplicative group of this, $\;\left(\Bbb F_{p^2}\right)^*:=\Bbb F_{p^2}\setminus\{0\}\;$ is a cyclic group (as is any finite subgroup of the multiplicative group of any field), and in this case it is a group of order $\;p^2-1\;$ , so you're looking for the number of generators this group has, and this number is exactly $\;\phi(p^2-1)\;,\;\;\phi=$ Euler's Totient Function..

Thus, you can search in the net for asymptotics of Euler's Function, or perhaps only take this function as it is.

  • 1
    $\begingroup$ I just wanted to say thank you for taking the time to understand my question and explain a little abstract algebra to me, as my algebra's more than a bit shaky. This question is in regards to an algorithm, like I said, so you have helped me with it, too. $\endgroup$ – Matt Groff May 26 '16 at 22:13

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.