1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Apr 21, 2020 at 3:57
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 21, 2020 at 4:59
  • $\begingroup$ Any thoughts on the comments, se-hyuck? $\endgroup$ Apr 22, 2020 at 13:29
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 24, 2020 at 13:14
  • 1
    $\begingroup$ 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$). $\endgroup$ Apr 24, 2020 at 13:22

1 Answer 1

1
$\begingroup$

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.


$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .