Square Root Modulo Composite

Nov 2009
169
2
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
May 2008
2,844
2,046
Chicago, IL
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:
  • Like
Reactions: EinStone
Nov 2009
169
2
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
May 2008
2,844
2,046
Chicago, IL
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.
 
Nov 2009
485
184
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
Sep 2008
1,163
429
Champaign, Illinois
\(\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
Sep 2008
1,163
429
Champaign, Illinois
\(\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
Sep 2008
1,163
429
Champaign, Illinois
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: