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.

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).

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.

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.