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

Printable View

- May 20th 2010, 04:21 AMEinStoneSquare Root Modulo Composite
Show that if is composite, (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.

- May 20th 2010, 06:51 AMChris L T521
To make this easy to follow, suppose we're dealing with , the standard residue system modulo . Given any composite, we're always guaranteed two residues with this property since and .

Let be a residue modulo (where ) with and let . Then by Euler's Theorem. Keeping in mind that when , we see that . Thus, is a residue that satisfies this property. Consequently, is also another residue. This one generates a residue different from since we required and it can't generate ; if it did, then , which isn't possible given the restrictions we made on the problem.

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

Does this make sense? - May 20th 2010, 09:35 AMEinStone
Can you explain this again, esepcially how you get

Quote:

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

Does this make sense?

- May 20th 2010, 09:42 AMChris L T521
I was claiming that couldn't be generated from . To show that, suppose that they were equivalent. Then , which can not happen.

Quote:

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

- May 20th 2010, 10:42 AMroninpro
I was actually thinking that you could use the Chinese Remainder Theorem. Just look at for each prime (power) divisor . Does this yield at least four solutions modulo ?

- June 2nd 2010, 11:17 AMchiph588@
- June 2nd 2010, 02:43 PMchiph588@
In fact with a little work one can show when is not of the form , where is a prime.

So unfortunately I believe your proof (for most ) only finds such numbers, namely , where .

-------

I think the best way to approach this problem would be to show there exists such that and . - June 2nd 2010, 04:59 PMchiph588@