Question

Quadratic residues. Fix a positive integer N. We say that a is a quadratic residue modulo N ifthere exists a such that $\mathbf{a}\mathbf{\equiv }{\mathbf{x}}^{\mathbf{2}}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{N}$.
(a) Let N be an odd prime and be a non-zero quadratic residue modulo N. Show that there are exactly two values in$\left\{0,1,....,N-1\right\}$ satisfying ${\mathbf{x}}^{\mathbf{2}}\mathbf{\equiv }\mathbf{a}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{N}$.
(b) Show that if N is an odd prime, there are exactly$\frac{\left(N+1\right)}{\mathbf{2}}$ quadratic residues in $\left\{0,1,...,N-1\right\}$.
(c) Give an example of positive integers a and N such that${\mathbf{x}}^{\mathbf{2}}\mathbf{\equiv }\mathbf{a}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{N}$has more than two solutions in $\left\{0,1,...,N-1\right\}$.

Short answer

(a) it is proved that there are only two possible values, which are x and N-x.

(b) It is proved that, if N is an odd prime, we have exactly$\frac{\mathrm{N}+1}{2}$ quadratic residues.

(c) The example is, “ ${\mathrm{x}}^2\equiv 1\mathrm{mod}8$has more than solution$\left\{1,3,5,7\right\}$ for the set of values $\left\{0,1,2,3,4,5,6,7\right\}$.”

Step-by-step solution

Explanation of (a)

The two values satisfying ${\mathrm{x}}^2\equiv \mathrm{a}\mathrm{mod}\mathrm{N}$.

Since is the non-zero quadratic residue mod N, the two values can be identifies using the following steps.

Then,

$\mathrm{x},\mathrm{y}\in \left\{0,1,...,\mathrm{N}-1\right\}$

The equation is,

${\mathrm{x}}^2\equiv {\mathrm{y}}^2\mathrm{mod}\mathrm{N}$

Thus,

${\mathrm{x}}^2-{\mathrm{y}}^2=\left(\mathrm{x}+\mathrm{y}\right)\left(\mathrm{x}-\mathrm{y}\right)$

From the case 1, N divides $\left(\mathrm{x}-\mathrm{y}\right)$.

If we divide$\left(\mathrm{x}-\mathrm{y}\right)$ by N, then$\mathrm{x}\equiv \mathrm{y}\mathrm{mod}\mathrm{N}$ that can be written as$\mathrm{x}=\mathrm{y}$ because the value x and y are inside the set of $\left\{1,2,...,\mathrm{N}-1\right\}$.

From the case 2, N divides $\left(\mathrm{x}+\mathrm{y}\right)$.

If $\left(\mathrm{x}+\mathrm{y}\right)$is inside of the limit, then N can divide$\left(\mathrm{x}+\mathrm{y}\right)$ with the condition $\left(\mathrm{x}+\mathrm{y}\right)=\mathrm{N}$, which can be written as $\mathrm{y}=\mathrm{N}-\mathrm{x}$.

Thus, the only two possible values are x and N-x.

Explanation of (b)

To show that there are exactly$\frac{\left(\mathrm{N}+1\right)}{2}$ quadratic residues.

In the range of $\left\{0,1,...,\mathrm{N}-1\right\}$, clearly 0 is a quadratic residue since $0^2=0\mathrm{mod}\mathrm{N}$.

Then, we take the range of quadratic residue as$\left\{1,2,...,\frac{\mathrm{N}-1}{2}\right\}$ .

For the odd prime value N, the equation is,

${\mathrm{x}}^2\ne {\mathrm{y}}^{2}0\mathrm{mod}\mathrm{N}$

Assuming towards contradiction,

${\mathrm{x}}^2\equiv {\mathrm{y}}^2\mathrm{mod}\mathrm{N}\to \left(\mathrm{x}-\mathrm{y}\right)\left(\mathrm{x}+\mathrm{y}\right)\equiv 0\mathrm{mod}\mathrm{N}$

Since N is a prime value, the Equation$\mathrm{x}\ne \mathrm{y}$

Then, $\mathrm{x}+\mathrm{y}\equiv \mathrm{N}$.

The two distinct elements $\mathrm{x}$and y is of size$\frac{\mathrm{N}-1}{2}$ quadratic residues, since the elements x and y are non-zero quadratic residues.

Explanation of (c)

Showing that${\mathrm{x}}^2\equiv \mathrm{a}\mathrm{mod}\mathrm{N}$has more than two solutions

In the range of $\left\{0,1,...,\mathrm{N}-1\right\}$, clearly we cannot take $\mathrm{N}=0,2$or any odd prime.

Therefore, we take the value of N as 8 and the value .

The equation can be written like ${\mathrm{x}}^2\equiv 1\mathrm{mod}8$.

Use value of x as$\left\{0,1,2,3,4,5,6,7\right\}$

Substituting the value of x as 0 in the equation,

localid="1657540092086" $$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {0}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

localid="1657540469266" $\begin{array}{rcl}0& \equiv & 1\mathrm{mod}8\\ 0\mathrm{mod}8& =& 1\\ 0& \ne & 1\end{array}$

Thus, $0^2\ne 1\mathrm{mod}8$.

Similarly,

Substitute the value of x as 1 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {1}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}1& \equiv & 1\mathrm{mod}8\\ 1\mathrm{mod}8& =& 1\\ 1& =& 1\end{array}$

Thus $1^2=1\mathrm{mod}8$, $1=1\mathrm{mod}8$.

Substitute the value of x as 2 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {2}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}4& \equiv & 1\mathrm{mod}8\\ 4\mathrm{mod}8& =& 1\\ 4& \ne & 1\end{array}$$\begin{array}{rcl}4& \equiv & 1\mathrm{mod}8\\ 4\mathrm{mod}8& =& 1\\ 4& \ne & 1\end{array}$

Thus, $2^2\ne 1\mathrm{mod}8$.

Substitute the value of x as 3 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {3}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}9& \equiv & 1\mathrm{mod}8\\ 9\mathrm{mod}8& =& 1\\ 1& =& 1\end{array}$

Thus, $3^2=1\mathrm{mod}8$.

Substitute the value of x as 4 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {4}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}16& \equiv & 1\mathrm{mod}8\\ 16\mathrm{mod}8& =& 1\\ 16& \ne & 1\end{array}$

Thus, $4^2\ne 1\mathrm{mod}8$.

Substitute the value of x as 5 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {5}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}25& \equiv & 1\mathrm{mod}8\\ 25\mathrm{mod}8& =& 1\\ 1& =& 1\end{array}$

Thus, $5^2=1\mathrm{mod}8$.

Substitute the value of x as 6 in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {6}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}36& \equiv & 1\mathrm{mod}8\\ 36\mathrm{mod}8& =& 1\\ 36& \ne & 1\end{array}$

Thus, $6^2\ne 1\mathrm{mod}8$.

Substitute the value x as 7 of in the equation,

$$\begin{gathered} {\mathrm{x}}^2\equiv 1\mathrm{mod}8 \\ {7}^2\equiv 1\mathrm{mod}8 \end{gathered}$$

It can be written as,

$\begin{array}{rcl}49& \equiv & 1\mathrm{mod}8\\ 49\mathrm{mod}8& =& 1\\ 1& =& 1\end{array}$

Thus, $7^2=1\mathrm{mod}8$.

Therefore,${\mathrm{x}}^2\equiv 1\mathrm{mod}8$ has more than one solution$\left\{1,3,5,7\right\}$ for the set of values from $\left\{0,1,2,3,4,5,6,7\right\}$.