Question

Show that if $\mathit{x}$is a nontrivial square root of 1 modulo N , that is if ${\mathbf{x}}^{\mathbf{2}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{}\mathbf{N}$but $\mathbf{}\mathbf{x}\mathbf{\ne }\mathbf{\pm }\mathbf{1}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{N}$, then$\mathit{N}$ must be composite. (For instance,${\mathbf{4}}^{\mathbf{2}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{}\mathbf{15}\mathbf{}\mathbf{but}\mathbf{}\mathbf{4}\mathbf{\not\equiv }\mathbf{\pm }\mathbf{1}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{15}$; thus 4 is a nontrivial square root of 1 modulo 15.)

Short answer

It can be proved by the proof by contradiction method.

Step-by-step solution

Explain composite numbers

The multiple of two small positive integers that has atleast one divisor other than one.

Prove the given problem

By proof by contradiction method, Consider If${\mathrm{x}}^2\equiv 1\mathrm{mod}\mathrm{p},\mathrm{x}\ne \pm 1\mathrm{mod}\mathrm{p}$ and is a prime number. Then,

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

Since,$x\ne \pm 1modp$ , it is known that$1\le xmodp-1<xmodp+1<p,$ ,and P is a prime number. Knowing that$xmodp\pm 1$ is relatively prime to p . Then by$(\mathrm{x}\mathrm{mod}\mathrm{p}+1)(\mathrm{x}\mathrm{mod}\mathrm{p}-1)\equiv 0\mathrm{mod}\mathrm{p}$, according to the division theorems,

$\mathrm{x}\mathrm{mod}\mathrm{p}\pm 1\equiv 0\mathrm{mod}\mathrm{p}$, This is a contradiction.

So, p is a composite.

Therefore, it has been proved.