# How many complexes modulo a prime $p$ are of multiplicative order $p^2 - 1$?

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$?

PROBLEM RESTATEMENT

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.

• I find the wording a little confusing. Your first words mean "If $\;-1\;$ is not a quadratic residue modulo some prime $\;p\;$ , then we..."? – DonAntonio May 26 '16 at 20:06
• And where are we looking for multiplicative order equal to $\;p^2-1\;$ ? In what ring, field,...? – DonAntonio May 26 '16 at 20:08
• @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$. – Matt Groff May 26 '16 at 20:44
• 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. – Matt Groff May 26 '16 at 20:45
• 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... – 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..