Thread: Mod 2011

Hi guys, I'm new at number theory. So, Could you help with the following congruence equation.





Regards!

Originally Posted by Sorombo

Hi guys, I'm new at number theory. So, Could you help with the following congruence equation.

I think that this equation has no solutions. I started by writing it as (since ). The usual formula for a quadratic equation gives the solutions as , which you have to write as because 1006 is the inverse of 2 (mod 2011).

So we need to know whether 1341 has a square root (mod 2011). In the technical jargon, is 1341 a quadratic residue (mod 2011)? The easiest way to investigate that is to notice that 1341 is the inverse of 3 (mod 2011). So 1341 will be a quadratic residue if and only if 3 is. By Euler's criterion (which we can apply because 3 and 2011 are both prime), that will be the case if and only if But you can evaluate by writing 1005 = 512+256+128+64+32+8+4+1 and calculating those powers of 3 (mod 2011) by successive squaring and reducing mod 2011. The answer comes out as –1, not 1.

Thus 3 is not a quadratic residue (mod 2011) and therefore that congruence has no solutions.

Edit. If you know about quadratic reciprocity, then you can avoid the calculation of and get the result much more painlessly.

I have a point I'd like to check, how could I prove that x is a quadratic residue modulo p if and only if its inverse is?

Originally Posted by Sorombo

I have a point I'd like to check, how could I prove that x is a quadratic residue modulo p if and only if its inverse is?

If then and conversely.