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.

<< Home

This page is powered by Blogger. Isn't yours?