# Number Theory - Eulers Criterion and Gauss' Lemma

• Aug 10th 2007, 05:50 AM
freed0m
Number Theory - Eulers Criterion and Gauss' Lemma
Hi all

any help with the attached question would be wonderful
• Aug 10th 2007, 06:12 AM
ThePerfectHacker
The discrimant is,
$\displaystyle 121-103 = 18$

Consider,
$\displaystyle \left\{ 18\cdot 1,18\cdot 2 , ... , 18\cdot 9 \right\}$
There are $\displaystyle 9$ such numbers so that the remainders exceede $\displaystyle 19/2$. Thus the Legendre symbol is $\displaystyle (-1)^9=-1$.
• Aug 10th 2007, 07:50 AM
topsquark
$\displaystyle 9x^2 - 11x + 3 = 0$ (mod 19)

I can't figure out how to use Euler's criterion on this (and I'm not even going to try Gauss' Lemma) but I can show that it has no solutions.

Complete the square:
$\displaystyle 9 \left ( x^2 - \frac{11}{9}x \right ) = -3$

$\displaystyle 9 \left ( x^2 - \frac{11}{9}x + \left ( \frac{11}{18} \right )^2 \right ) = -3 + 9 \left ( \frac{11}{18} \right )^2$

$\displaystyle 9 \left ( x - \frac{11}{18} \right ) ^2 = \frac{13}{36}$

$\displaystyle (18x - 11)^2 = 13$

Remember this is all mod 19. But 13 doesn't have a square root in mod 19. So this equation has no solution.

Edit: Okay, I guess you could simply use the quadratic formula and come up with the same result, which would be a bit faster.

-Dan
• Aug 10th 2007, 07:54 AM
topsquark
Quote:

Originally Posted by ThePerfectHacker
The discrimant is,
$\displaystyle 121-103 = 18$

Consider,
$\displaystyle \left\{ 18\cdot 1,18\cdot 2 , ... , 18\cdot 9 \right\}$
There are $\displaystyle 9$ such numbers so that the remainders exceede $\displaystyle 19/2$. Thus the Legendre symbol is $\displaystyle (-1)^9=-1$.

Ahhhhhhhhh! Now I understand what this answer is referring to. :) Well, at least we agree!

-Dan
• Aug 10th 2007, 12:12 PM
ThePerfectHacker
This is a problem with your approach via completing squares. These are integers, you cannot start treating them as rational numbers.
• Aug 10th 2007, 02:52 PM
topsquark
Quote:

Originally Posted by ThePerfectHacker
This is a problem with your approach via completing squares. These are integers, you cannot start treating them as rational numbers.

I understand that. I was being lazy with my notation. Obviously when I multiply a number by $\displaystyle \frac{1}{9}$ I am multiplying it by 17, the multiplicative inverse of 9 in modulo 19. (I can get away with this only because 19 is prime, thus $\displaystyle \mathbb{Z}_{19}$ is a field.)

However it doesn't matter much since my method didn't answer any of his questions. I just posted it because I didn't realize your post addressed the question (I didn't realize that until later, I thought it was in reference to his last question), and wanted to tell him the answer is that there is no solution to the equation so that he would know what to expect as an answer when he used the methods he was required to use.

-Dan
• Aug 11th 2007, 05:03 PM
ThePerfectHacker
Another approach is to multiply by $\displaystyle 36$ to get,

$\displaystyle 36(9x^2 - 11 x + 3) \equiv 0$

$\displaystyle (18x-11)^2 \equiv 18 (\bmod 19)$