Question

1.36. Square roots. In this problem, we'll see that it is easy to compute square roots modulo a prime pwith $\mathbf{p}\mathbf{\equiv }\mathbf{3}\left(\mathrm{mod}4\right)$.
(a) Suppose $\mathbf{p}\mathbf{\equiv }\mathbf{3}\left(\mathrm{mod}4\right)$. Show that$\left(p+1\right)\mathbf{/}\mathbf{4}$ is an integer.
(b) We say x is a square root of a modulo p if $\mathbf{a}\mathbf{=}{\mathbf{x}}^{\mathbf{2}}\left(\mathrm{mod}p\right)$. Show that if $\mathbf{p}\mathbf{\equiv }\mathbf{3}\left(\mathrm{mod}4\right)$and if a has a square root modulo p, then${\mathbf{a}}^{\left(p+1\right)}\mathbf{/}\mathbf{4}$ is such a square root.

Short answer

1. $\frac{\mathrm{p}+1}{4}$is showed as integer.
2. It is proved that, if $\mathrm{p}\equiv 3\left(\mathrm{mod}4\right)$and if a has a square root modulo p, then ${\mathrm{a}}^{\frac{\mathrm{p}+1}{4}}$is such a square root is depicted.

Step-by-step solution

Step 1: Introduction to the Concept

After one number is divided by another, the modulo operation yields the remainder or signed remainder of the division (called the modulus of the operation).

Step 2: Solution Explanation

a)

The following is a representation of the provided equation "$\mathrm{p}\equiv 3\left(\mathrm{mod}4\right)$"

$\mathrm{p}=3+4\left(\mathrm{k}\right)--------\left(1\right)$

• Because "$\mathrm{x}\equiv 1\mathrm{modN}$" is the same as "$\mathrm{x}=1+\mathrm{kN}$"
• It's worth noting that "k" is an integer.

On both sides of the equation (1), add "1".

$$\begin{gathered} \mathrm{p}+1=\left(4\left(\mathrm{k}\right)+3\right)+1 \\ \mathrm{p}+1=\left(4\left(\mathrm{k}\right)+4\right) \\ \mathrm{p}+1=4\left(\mathrm{k}+1\right) \\ \frac{\mathrm{p}+1}{4}=\mathrm{k}+1--------\left(2\right) \end{gathered}$$

"$\mathrm{k}+1$" is also an integer because "k" is an integer. (k+1) equals$\frac{\mathrm{p}+1}{4}$ according to equation (2).

As a result,$\frac{\mathrm{p}+1}{4}$ is an integer.

Step 3: Solution Explanation

b)

From Fermat's "Little Theorem",

${\mathrm{a}}^{\mathrm{p}-1}=1\mathrm{mod}\mathrm{p}------\left(3\right)$

The following equation has been derived based on equation (3):

$$\begin{gathered} {\mathrm{a}}^{\mathrm{p}-1}=1\mathrm{mod}\mathrm{p} \\ \left({\mathrm{a}}^{\mathrm{p}-1}-1\right)=0\mathrm{mod}\mathrm{p} \end{gathered}$$

Multiply "$\frac{1}{2}$" by both sides of the above expression's power values.

$$\begin{gathered} \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1^{\frac{1}{2}}\right)=0\mathrm{mod}\mathrm{p} \\ \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1\right)=0\mathrm{mod}\mathrm{p} \\ \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1\right)\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)=0\mathrm{mod}\mathrm{p} \end{gathered}$$

Moving the negative set of value$\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1\right)$ to the right side of the equation is not a valid solution.

$$\begin{gathered} \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)=\frac{0}{\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)}\mathrm{mod}\mathrm{p} \\ \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)=0\mathrm{mod}\mathrm{p} \\ {\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}=-1\mathrm{mod}\mathrm{p} \end{gathered}$$

Thus, the above equation will not satisfy the Fermat's "Little Theorem".

Moving the positive set of value $\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)$to the right side of the equation as follows,

$\begin{array}{rcl}\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1\right)& =& \frac{0}{\left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}+1\right)}\mathrm{mod}\mathrm{p}\\ \left({\mathrm{a}}^{\frac{\mathrm{p}-1}{2}}-1\right)& =& 0\mathrm{mod}\mathrm{p}\\ \left({\mathrm{a}}^{\frac{\mathrm{p}+1}{2}}-\mathrm{a}\right)& =& 0\mathrm{mod}\mathrm{p}\\ {\mathrm{a}}^{\frac{\mathrm{p}+1}{2}}& =& \mathrm{amod}\mathrm{p}\\ & & \end{array}$

The equation above demonstrates this ${\mathrm{a}}^{\frac{\mathrm{p}+1}{2}}=\mathrm{a}\mathrm{mod}\mathrm{p}$, and it may be written as follows:

${\left({\mathrm{a}}^{\frac{\mathrm{p}+1}{4}}\right)}^2=\mathrm{a}\mathrm{mod}\mathrm{p}$.

When you move the square from left to right, it is converted to square root.

${\mathrm{a}}^{\frac{\mathrm{p}+1}{4}}=\sqrt{\mathrm{a}}\mathrm{mod}\mathrm{p}$

When "a" has a square root modulo “${\mathrm{a}}^{\frac{\mathrm{p}+1}{4}}$”is a square root.