Show that if is composite, (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 , 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?
Can you explain this again, esepcially how you get
What do you mean increase n, I mean n is fixed??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?
I was claiming that couldn't be generated from . To show that, suppose that they were equivalent. Then , which can not happen.
I mean as we pick larger values of , the number of residues that satisfy the property of interest will be more than 4.What do you mean increase n, I mean n is fixed??
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 .