Friday, May 05, 2006
JSH: Remarkable quadratic residue result
Given a quadratic residue r modulo n, where all are, of course, natural numbers it must be true that 4r is a quadratic residue modulo n.
I have a remarkable little proof.
That is a HUGE result. It is just such a HUGE result.
To check if a number is a quadratic residue then you can just multiply by 4. If it is, then 4 times it will be as well. e.g. 2*4 mod 7 = 1, and 2 is a square modulo 7.
Now notice that if you are not sure of the result, you can just keep multiplying by 4.
For instance, checking 2 modulo 17, I have 2(4) = 8, if you are not sure, multiply by 4 again, and you have 4(8) mod 17 = 15. If you are not sure, 4(15) mod 17 = 9, and as 9 is a square, it is definite that 2 is as well.
What a neat result. If r is a square modulo n, then 4r is a square modulo n.
All quadratic residues are connected then by 4, as they are all products of 4 times some other quadratic residue.
The proof is nifty, and not obvious.
I have a remarkable little proof.
That is a HUGE result. It is just such a HUGE result.
To check if a number is a quadratic residue then you can just multiply by 4. If it is, then 4 times it will be as well. e.g. 2*4 mod 7 = 1, and 2 is a square modulo 7.
Now notice that if you are not sure of the result, you can just keep multiplying by 4.
For instance, checking 2 modulo 17, I have 2(4) = 8, if you are not sure, multiply by 4 again, and you have 4(8) mod 17 = 15. If you are not sure, 4(15) mod 17 = 9, and as 9 is a square, it is definite that 2 is as well.
What a neat result. If r is a square modulo n, then 4r is a square modulo n.
All quadratic residues are connected then by 4, as they are all products of 4 times some other quadratic residue.
The proof is nifty, and not obvious.
# posted by James Harris @ 20:45 
