# Square Root Modulo Composite

#### EinStone

Show that if $$\displaystyle n$$ is composite, $$\displaystyle n \neq 2p$$ (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.

#### Chris L T521

MHF Hall of Fame
Show that if $$\displaystyle n$$ is composite, $$\displaystyle n \neq 2p$$ (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.
To make this easy to follow, suppose we're dealing with $$\displaystyle \{0,1,\ldots,n-1\}$$, the standard residue system modulo $$\displaystyle n$$. Given any $$\displaystyle n$$ composite, we're always guaranteed two residues with this property since $$\displaystyle 1^2\equiv 1\pmod{n}$$ and $$\displaystyle (n-1)^2\equiv n^2-2n+1\equiv 1\pmod{n}$$.

Let $$\displaystyle a$$ be a residue modulo $$\displaystyle n$$ (where $$\displaystyle n\neq 2p$$) with $$\displaystyle 1<a<n-1$$ and let $$\displaystyle (a,n)=1$$. Then $$\displaystyle a^{\varphi(n)}\equiv 1\pmod{n}$$ by Euler's Theorem. Keeping in mind that $$\displaystyle 2\mid \varphi(n)$$ when $$\displaystyle n>2$$, we see that $$\displaystyle a^{\varphi(n)}\equiv \left(a^{\varphi(n)/2}\right)^2\equiv 1\pmod{n}$$. Thus, $$\displaystyle a^{\varphi(n)/2}$$ is a residue that satisfies this property. Consequently, $$\displaystyle -a^{\varphi(n)/2}\equiv n-a^{\varphi(n)/2}\pmod{n}$$ is also another residue. This one generates a residue different from $$\displaystyle 1$$ since we required $$\displaystyle n\neq 2p$$ and it can't generate $$\displaystyle n-1$$; if it did, then $$\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies a^{\varphi(n)/2}\equiv 1\pmod{n}$$, which isn't possible given the restrictions we made on the problem.

This shows that we are guaranteed four different residues modulo $$\displaystyle n$$ with this property. We then allow for the possibility of more residues as we allow $$\displaystyle n$$ to increase.

Does this make sense?

Last edited:
• EinStone

#### EinStone

This one generates a residue different from $$\displaystyle 1$$ since we required $$\displaystyle n\neq 2p$$ and it can't generate $$\displaystyle n-1$$; if it did, then $$\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies a^{\varphi(n)/2}\equiv 1\pmod{n}$$, which isn't possible given the restrictions we made on the problem.
Can you explain this again, esepcially how you get $$\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$$

This shows that we are guaranteed four different residues modulo $$\displaystyle n$$ with this property. We then allow for the possibility of more residues as we allow $$\displaystyle n$$ to increase.

Does this make sense?
What do you mean increase n, I mean n is fixed??

#### Chris L T521

MHF Hall of Fame
Can you explain this again, esepcially how you get $$\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$$
I was claiming that $$\displaystyle n-1$$ couldn't be generated from $$\displaystyle n-a^{\varphi(n)/2}$$. To show that, suppose that they were equivalent. Then $$\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies 1\equiv a^{\varphi(n)/2}\pmod{n}$$, which can not happen.

What do you mean increase n, I mean n is fixed??
I mean as we pick larger values of $$\displaystyle n$$, the number of residues that satisfy the property of interest will be more than 4.

#### roninpro

I was actually thinking that you could use the Chinese Remainder Theorem. Just look at $$\displaystyle x^2\equiv 1\pmod{p_i}$$ for each prime (power) divisor $$\displaystyle p_i$$. Does this yield at least four solutions modulo $$\displaystyle n$$?

#### chiph588@

MHF Hall of Honor
$$\displaystyle \implies 1\equiv a^{\varphi(n)/2}\pmod{n}$$, which can not happen.
$$\displaystyle (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}$$

Last edited:

#### chiph588@

MHF Hall of Honor
$$\displaystyle (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}$$
In fact with a little work one can show $$\displaystyle a^{\phi(m)/2}\equiv1\bmod{m}$$ when $$\displaystyle m$$ is not of the form $$\displaystyle 1,2,4,p^a,2p^a$$, where $$\displaystyle p$$ is a prime.

So unfortunately I believe your proof (for most $$\displaystyle n$$) only finds $$\displaystyle 2$$ such numbers, namely $$\displaystyle \{1,n-1\}$$, where $$\displaystyle a^2\equiv1\bmod{n}$$.

-------

I think the best way to approach this problem would be to show there exists $$\displaystyle a$$ such that $$\displaystyle |a|\not\equiv1\bmod{n}$$ and $$\displaystyle a\equiv a^{-1}\bmod{n}$$.

Last edited:

#### chiph588@

MHF Hall of Honor
Show that if $$\displaystyle n$$ is composite, $$\displaystyle n \neq 2p$$ (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.
I believe this statement is false. Consider $$\displaystyle 18=2\cdot3^2\neq2p$$ for a prime $$\displaystyle p$$

$$\displaystyle \begin{tabular}{|c c | c c|}\hline a & a squared & a & a squared \\\hline 1 & 1 & 10 & 10\\ 2 & 4 & 11 & 13\\ 3 & 9 & 12 & 0\\ 4 & 16 & 13 & 7\\ 5 & 7 & 14 & 16\\ 6 & 0 & 15 & 9\\ 7 & 13 & 16 & 4\\ 8 & 10 & 17 & 1\\ 9 & 9 & & \\\hline \end{tabular}$$

Only $$\displaystyle (\pm1)^2\equiv1\bmod{18}$$, thus a counterexample.

I was actually thinking that you could use the Chinese Remainder Theorem. Just look at $$\displaystyle x^2\equiv 1\pmod{p_i}$$ for each prime (power) divisor $$\displaystyle p_i$$. Does this yield at least four solutions modulo $$\displaystyle n$$?
Using this argument in a slightly altered way for my defense, my guess is this theorem is true when $$\displaystyle n\neq2p^a$$ where $$\displaystyle p$$ is an odd prime.

Last edited: