Square Root Modulo Composite

**EinStone** · May 20th 2010, 03:21 AM

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

**Chris L T521** · May 20th 2010, 05:51 AM

Originally Posted by EinStone

Show that if $n$ is composite, $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 $\{0,1,\ldots,n-1\}$ , the standard residue system modulo $n$ . Given any $n$ composite, we're always guaranteed two residues with this property since $1^2\equiv 1\pmod{n}$ and $(n-1)^2\equiv n^2-2n+1\equiv 1\pmod{n}$ .

Let $a$ be a residue modulo $n$ (where $n\neq 2p$ ) with $1<a<n-1$ and let $(a,n)=1$ . Then $a^{\varphi(n)}\equiv 1\pmod{n}$ by Euler's Theorem. Keeping in mind that $2\mid \varphi(n)$ when $n>2$ , we see that $a^{\varphi(n)}\equiv \left(a^{\varphi(n)/2}\right)^2\equiv 1\pmod{n}$ . Thus, $a^{\varphi(n)/2}$ is a residue that satisfies this property. Consequently, $-a^{\varphi(n)/2}\equiv n-a^{\varphi(n)/2}\pmod{n}$ is also another residue. This one generates a residue different from $1$ since we required $n\neq 2p$ and it can't generate $n-1$ ; if it did, then $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 $n$ with this property. We then allow for the possibility of more residues as we allow $n$ to increase.

Does this make sense?

**EinStone** · May 20th 2010, 08:35 AM

Originally Posted by Chris L T521

This one generates a residue different from $1$ since we required $n\neq 2p$ and it can't generate $n-1$ ; if it did, then $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 $n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$

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

Does this make sense?

What do you mean increase n, I mean n is fixed??

**Chris L T521** · May 20th 2010, 08:42 AM

Originally Posted by EinStone

Can you explain this again, esepcially how you get $n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$

I was claiming that $n-1$ couldn't be generated from $n-a^{\varphi(n)/2}$ . To show that, suppose that they were equivalent. Then $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 $n$ , the number of residues that satisfy the property of interest will be more than 4.

**roninpro** · May 20th 2010, 09:42 AM

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

**chiph588@** · June 2nd 2010, 10:17 AM

Originally Posted by Chris L T521

$\implies 1\equiv a^{\varphi(n)/2}\pmod{n}$ , which can not happen.

$(2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}$

**chiph588@** · June 2nd 2010, 01:43 PM

Originally Posted by chiph588@

$(2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}$

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

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

-------

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

**chiph588@** · June 2nd 2010, 03:59 PM

Originally Posted by EinStone

Show that if $n$ is composite, $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 $18=2\cdot3^2\neq2p$ for a prime $p$

$\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 $(\pm1)^2\equiv1\bmod{18}$ , thus a counterexample.

Originally Posted by roninpro

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

Using this argument in a slightly altered way for my defense, my guess is this theorem is true when $n\neq2p^a$ where $p$ is an odd prime.

Thread: Square Root Modulo Composite

LinkBack

Thread Tools

Display

Square Root Modulo Composite

Similar Math Help Forum Discussions

Square root inside square root equation

primitive root modulo p

prove that of sum square root of 2 and square root of 3 is not rational

Square root modulo a prime

Primitive root modulo 121

Search Tags