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.
Best Answer
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$
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.