# Quadratic residue and primitive root

Let $$x^2 =a \pmod p$$ for a odd prime number $$p$$. Say $$g$$ is a primitive root for $$\bmod p$$

I've known the proposition like the below

$$(1)$$ $$a$$ is a quadratic residue $$\iff$$ $$a=g^{E}$$ (Here the $$E$$ is a even number $$s.t.$$ $$0 \leq E \leq p-1$$)

$$(2)$$ $$a$$ is a non-quadratic residue $$\iff$$ $$a=g^{O}$$ (Here the $$O$$ is a odd number $$s.t.$$ $$0 \leq O \leq p-1$$)

So my question is expanding our thought for $$mod n$$(I.e. not only the $$n$$ is a odd prime but also it is composite number having the primitive root ), I want to figure out those statements still hold.

More simply speaking, I would suggest my thought as statements $$(1)$$ and $$(2)$$

Let $$x^2 =a \pmod n$$ for a $$n$$ having primitives.(Like the $$n = 2,4,2p^k,p^k$$). Say $$g$$ is a primitive root for $$mod n$$

$$(1)$$ $$a$$ is a quadratic residue $$\iff$$ $$a=g^{E}$$ (Here the $$E$$ is a even number $$s.t.$$ $$0 \leq E \leq \phi(n)$$)

$$(2)$$ $$a$$ is a non-quadratic residue $$\iff$$ $$a=g^{O}$$ (Here the $$O$$ is a even number $$s.t.$$ $$0 \leq O \leq \phi(n)$$)

My guess is both $$(1)$$ and $$(2)$$ are right because if the $$a=g^{2k}$$, then there is a root that $$x=g^k$$. Hence $$a$$ would be quadratic residue. Vice versa, I could guess the odd power cases.

But I don't have any confidence my things are right or not. Please check my idea.

Any answers and helps are always welcome and appreciated.

• Your (1) is false as written. You are claiming that for every even number $E$, $a=g^E$; this is false, it would require, for example, $g^0 = g^2$, which would only hold for $p=3$. Same for (3), as for $p\gt 3$ it would require $g^1 = g^3$, which would also be false. Given that what “you know” is actually false, it is no wonder you are having problems. PS: A problem should not be tagged with both “number-theory” and “elementary-number-theory”. Do read the tag descriptions. Apr 21, 2020 at 3:57
• What @Arturo writes is correct. It's easy to fix; just change all to some. But there's another problem; if you're working modulo $p^3$, does $p^2$ count as a quadratic residue? It's certainly a square, but it's not any power of a primitive root. Apr 21, 2020 at 4:59
• Any thoughts on the comments, se-hyuck? Apr 22, 2020 at 13:29
• Dear @GerryMyerson, Sorry for my rude attitude. I just logged in MSE, and sawed your kind comment just now. Yes, It would be false that if "for all". So, I revised my question by deleting it. So from the 2-day ago, I've just waited other comment or answer that could give me some hints. But As your comment at Aprl 21 at 4:59, still there are other problems like you suggested. So my conclusion the statement only correct for odd pirme $p$ . And again, thanks for your comment that point out my impolite behavior. Plus I would apologize for my impoliteness. Apr 24, 2020 at 13:14
• p.s.) @GerryMyerson, So the statement should be revised as like the below I thought. "If the $n$ having primitive root,$g$ , there are some quadratic residue that can be expressed as a $g^{2k}$" (Because of the counterexample you suggested $p^2$ is a quadratic residue but not power of the primitive for $mod p^3$). Apr 24, 2020 at 13:22

Regarding your statements $$(1)$$ and $$(2)$$ for composite $$n$$ which have primitive roots, note they are true only for all $$a$$ which are coprime to $$n$$, e.g., as it states in Primitive root modulo $$n$$

... $$g$$ is a primitive root modulo $$n$$ if for every integer $$a$$ coprime to $$n$$, there is an integer $$k$$ such that $$g^{k} \equiv a \pmod{n}$$ Such a value $$k$$ is called the index or ...

Your $$(1)$$ then is, as you stated, true when the index is $$2k$$ to get $$x = g^{k}$$. For your $$(2)$$, have the odd index be $$0 \le 2k + 1 \lt \phi(n)$$ and assume there's an $$x$$ where

$$x^2 \equiv g^{2k + 1} \pmod{n} \tag{1}\label{eq1A}$$

Now, $$x$$ must be coprime to $$n$$ so there's a $$0 \le j \lt \phi(n)$$ where $$x \equiv g^j$$ so you then have

$$g^{2j} \equiv g^{2k + 1} \pmod{n} \implies g^{2j - (2k + 1)} \equiv 1 \pmod{n} \tag{2}\label{eq2A}$$

With $$d = 2j - (2k + 1)$$, since the multiplicative order of $$g$$ modulo $$n$$ is $$\phi(n)$$, and you have $$0 \le 2j \lt 2\phi(n)$$ so $$-\phi(n) \lt d \lt 2\phi(n)$$, this means you either have $$d = 0 \implies 2j = 2k + 1$$, which is not possible since you can't have an even equal an odd, or $$d = \phi(n) \implies 2j = \phi(n) + (2k + 1)$$. However, apart from $$n = 2$$ (where statement $$(2)$$ doesn't apply), $$\phi(n)$$ for all the other cases, i.e., $$n = 4, p^{k}$$ and $$2p^k$$, is even. Thus, once again, you have an even number on the left and an odd on the right, so it can't be true. This shows the original assumption of $$x$$ existing can't be true, so $$a$$ must be a quadratic nonresidue.

As for handling $$a$$ when it's not coprime to $$n$$, for simpler algebra & handling, first reduce $$a$$, if need be, so it's $$0 \le a \lt n$$. With $$a = 0$$, it's a quadratic residue. With $$a \gt 0$$, for $$n = 2$$, there's no other values, while for $$n = 4$$, you have $$a = 2$$ being a quadratic nonresidue. For $$p^k$$ and $$2p^k$$, where $$p$$ is an odd prime, you have

$$a = 2^i p^j(m) \tag{3}\label{3A}$$

for some $$i \ge 0$$ and $$0 \le j \le k$$, with $$ij \neq 0$$, and $$m$$ where $$\gcd(m, 2p) = 1$$. For $$j = k$$, the only possibility is $$a = p^k$$ with $$n = 2p^k$$ and $$m = 1$$, i.e.,

$$x^2 \equiv p^k \pmod{2p^k} \tag{4}\label{eq4A}$$

If $$k$$ is even, then $$x \equiv p^{\frac{k}{2}} \pmod{2p^k}$$, while if $$k$$ is odd, then $$x \equiv p^{\frac{k + 1}{2}} \pmod{2p^k}$$, so $$a$$ is a quadratic residue in either case.

Next, consider $$j \lt k$$, with the $$2$$ cases for $$n$$:

Case #$$1$$: $$n = p^k$$

There's an integer $$q$$ such that

$$x^2 \equiv 2^i p^j(m) \pmod{p^k} \iff x^2 - 2^i p^j(m) = qp^k \tag{5}\label{eq5A}$$

Let $$x$$ have $$r$$ factors of $$p$$, so $$x^2$$ has $$2r$$ factors. If $$2r \lt j$$, the left side has $$2r$$ factors of $$p$$ altogether, while if $$2r \gt j$$, then it has $$j$$ factors in total. In summary, it has $$b = \min(2r, j)$$ factors of $$p$$. However, since the right side has at least $$k \gt j \ge b$$ factors, this means it has more factors of $$p$$, which is not possible. As such, with $$j$$ being odd, $$a$$ would be a quadratic nonresidue. Otherwise, with $$j = 2r$$, if you have $$x = p^r x'$$, dividing both sides by $$p^j$$ gives

$$(x')^2 - 2^i(m) = qp^{k - j} \iff (x')^2 \equiv 2^i(m) \pmod{p^{k - j}} \tag{6}\label{eq6A}$$

Since $$p^{k - j}$$ has a generator and $$2^i(m)$$ is coprime to $$p^{k - j}$$, you can then use $$a = 2^i(m)$$ and $$n = p^{k - j}$$ with your statements $$(1)$$ and $$(2)$$ to determine whether or not this $$a$$ is a quadratic residue.

Case #$$2$$: $$n = 2p^k$$

As before, there's an integer $$q$$ such that

$$x^2 \equiv 2^i p^j(m) \pmod{2p^k} \iff x^2 - 2^i p^j(m) = q(2p^k) \tag{7}\label{eq7A}$$

As with case #$$1$$, if $$j$$ is odd then it's a quadratic nonresidue, else $$j = 2r$$ with $$x = p^r x'$$ giving, after dividing by $$p^j$$,

$$(x')^2 - 2^i(m) = q(2p^{k-j}) \tag{8}\label{eq8A}$$

If $$i = 0$$, you then have

$$(x')^2 \equiv m \pmod{2p^{k-j}} \tag{9}\label{eq9A}$$

You can use $$a = m$$ and $$n = 2p^{k-j}$$ with your statements $$(1)$$ and $$(2)$$ to find whether or not this is a quadratic residue.

For $$i \gt 0$$, $$x'$$ must be even, i.e., $$x' = 2x''$$, so \eqref{eq8A} becomes

$$4(x'')^2 - 2^i(m) = q(2p^{k-j}) \iff 2(x'')^2 - 2^{i-1}(m) = q(p^{k-j}) \tag{10}\label{eq10A}$$

The multiplicative inverse of $$2$$ modulo $$p^{k-j}$$ is $$\frac{p^{k-j} + 1}{2}$$, so multiplying both sides of \eqref{eq10A} by this value means it then becomes the equivalent of

$$(x'')^2 \equiv \left(\frac{p^{k-j} + 1}{2}\right)2^{i-1}(m) \pmod{p^{k-j}} \tag{11}\label{eq11A}$$

Similar to in case #$$1$$, you can now use $$a = \left(\frac{p^{k-j} + 1}{2}\right)2^{i-1}(m)$$ and $$n = p^{k - j}$$ with your statements $$(1)$$ and $$(2)$$ to determine whether or not this $$a$$ is a quadratic residue.