Mod 2011

• Nov 15th 2011, 01:14 PM
Sorombo
Mod 2011
Hi guys, I'm new at number theory. So, Could you help with the following congruence equation.

$x^2+x+1676 \equiv 0 \mod 2011$

Regards!
• Nov 16th 2011, 01:12 PM
Opalg
Re: Mod 2011
Quote:

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

$x^2+x+1676 \equiv 0 \mod 2011$

I think that this equation has no solutions. I started by writing it as $x^2 + x - 335\equiv0\pmod{2011}$ (since $1676\equiv-335\pmod{2011}$). The usual formula for a quadratic equation gives the solutions as $x = \tfrac12(-1\pm\sqrt{1341})$, which you have to write as $x\equiv1006(-1\pm\sqrt{1341})\pmod{2011}$ 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 $3^{1005}\equiv1\pmod{2011}.$ But you can evaluate $3^{1005}\pmod{2011}$ 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 $3^{1005}\pmod{2011}$ and get the result much more painlessly.
• Nov 17th 2011, 04:58 PM
Sorombo
Re: Mod 2011
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?
• Nov 18th 2011, 12:38 AM
Opalg
Re: Mod 2011
Quote:

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 $x=y^2$ then $x^{-1} = (y^{-1})^2,$ and conversely.