# modulo version of the quadratic formula and Euler's criterion

Use the modulo version of the quadratic formula and Euler's criterion to decide if the following has a solution or not.

$2x^2+5x+8 \equiv 0\pmod{37}$

I'm not sure how I would use what was being asked of me to decide if this has a solution or not, but I have came to the conclusion that it does not, because I plugged in every possible answer $0-36$, and none of them were congruent to zero.

The way people have answered the question, isn't exactly the way I need. I have made some progress, but I'm not exactly sure how to finish:

$2x^2+5x+8 \equiv 0\pmod{37}$

$x^2+21x+4\equiv0\pmod{37}$

$x^2+58x+841\equiv837\pmod{37}$

$(x+29)^2\equiv23\pmod{37}$

I know that if $p$ is an odd prime and $p$ doesn't divide $a$, then $x^2\equiv a\pmod{p}$ has a solution or no solution depending on whether $a^\frac{p-1}{2}\equiv 1 \space\space \text{or}\space -1\pmod{p}$.

This is where I get stuck. Can someone help me from here? I have a feeling this problem has no solutions, so could someone also explain to me what to do if a problem like this did have solutions.

-

Consider the quadratic congruence $ax^2+bx+c\equiv 0\pmod{p}$, where $p$ is an odd prime. Multiplying through by $4a$, we obtain the equivalent congruence $$4a^2x^2+4abx+4ac\equiv 0\pmod{p},$$ which, by completing the square, can be rewritten as $$(2ax+b)^2\equiv b^2-4ac\pmod{p}.\tag{1}$$ So in order for the original congruence to be solvable, $b^2-4ac$ must be a square modulo $p$. Conversely, but we will not need this, if $b^2-4ac$ is congruent to a square modulo $p$, then we can use $(1)$ to solve the original congruence, in a manner which is essentially the Quadratic Formula.

In our case, $4b^2-4ac=25-64=-39\equiv -2\pmod{37}$. So we want $-2$ to be a quadratic residue of $37$. By Euler's Criterion, which you have been asked to use, this is the case precisely if $$(-2)^{\frac{37-1}{2}}\equiv 1\pmod{37}.$$ Since we are calculating an even power, we don't need to worry about the minus sign. Note that $2^5\equiv -5\pmod{37}$, so $2^{10}\equiv 25\pmod{37}$, and therefore $2^{13}\equiv 200\equiv 15\pmod{37}$. It follows that $2^{18}\equiv -75\equiv -1\pmod{37}$, and therefore by Euler's Criterion $-2$ is not a quadratic residue of $37$. We could also have used the calculator, by computing $2^{18}$, and dividing by $37$: the remainder is not $1$.

You can get this in a simpler way. Since $-1$ is a QR of $37$, we find that $-2$ is a QR iff $2$ is. But $37$ has the shape $8k+5$, and $2$ is a QR of primes of the shape $8k\pm 1$, and a NR of primes of shape $8k\pm 3$.

-
bx+c i guess , and i guess QR is quadratic residue and NR - not quadratic residue???? – talmudist Jan 19 at 21:19
Yes, fairly standard abbreviation, – André Nicolas Jan 19 at 21:21
first line should be bx+c , thank you very much Andre , good answer – talmudist Jan 19 at 21:35
: @talmudist: Thank you, I very much appreciate the opportunity to correct old typos/answers. Like the name, am envious of the choice. – André Nicolas Jan 20 at 3:13

The modular version of the quadratic formula is, for all practical purposes, just the quadratic formula (provided twice the coefficient of $x^2$ is relatively prime to the modulus). As usual, you wind up looking at $b^2-4ac$, which here is $5^2-(4)(2)(8)=25-64=-39$. Since we're working modulo $37$, we can replace that $-39$ by $-2$ or by $35$, if we find it convenient. If $-39$ is a quadratic residue (a "square") modulo $37$, the congruence has solutions; if not, not. So, presumably you have some way to work out whether $-39$ is a quadratic residue modulo $37$ --- that should be where Euler's criterion comes in.

-

Hint $\rm\,\ mod\ 37\:$ it has discriminant $\,-39\equiv -2\:$ which is not a square since, by Euler's criterion

$$\rm \ \ mod\ 37\!:\,\ (-2)^{18}\!=\, 4\cdot (\color{#C00}{2^8})^2 \equiv 4\cdot 9\equiv -1,\ \ \ by\ \ \ \color{#C00}{2^8}\! = 16^2\! = 256\equiv -3,\ \ \ by\ \ \ 7\cdot 37 = 259$$

Now recall: if a quadratic $\rm\:f(x)\in R[x]\:$ has a root in a ring R, then its discriminant is a square in R. Said contrapositively, if the discriminant is not a square in R, then the quadratic has no root in R. The proof, by completing the square, works in any ring $\rm\,R\,$ (so in $\mathbb Z/37 =$ integers mod $37$), viz. $$\rm\: \ \ 4a\:(a\:x^2\! + b\:x + c\, =\, 0)\ \Rightarrow\ (2a\:x+b)^2 =\: b^2\! - 4ac$$

Remark $\$ When learning (modular) arithmetic in new rings it is essential to keep in mind that, like above, any proofs from familiar concrete rings (e.g. $\mathbb Q,\mathbb R,\mathbb C)$ will generalize to every ring if they are purely ring theoretic, i.e. if the proof uses only universal ring properties, i.e. laws that hold true in every ring, e.g. commutative, associative, distributive laws. Thus many familar identities (e.g. Binomial Theorem, difference of squares factorization) are universal, i.e. hold true in every ring.

This is one of the great benefits provided by axiomatization: abstracting the common properties of familiar number systems into the abstract notion of a ring allows one to give universal proofs of ring theorems. It is not necessary to reprove these common ring properties every time one studies a new ring (such reproofs occurred frequently before rings was axiomatized).

-
So if the discriminate has a square, for a quadratic congruence, it has a solution? – maroon.elephants Nov 5 '12 at 15:21
Here we need the converse: $\rm\,f(x)\,$ has discriminant D nonsquare in $\Bbb Z/37\,$ $\Rightarrow$ $\rm\,f(x)\,$ has no root $\in \Bbb Z/37.\:$ Conversely, if if D is a square, then you can apply the quadratic forumula to obtain a root presuming that twice the leading coefficient is invertible. Howver, the quadratic formula needn't give all roots when the ring is not a domain, e.g. mod $8$ note $\rm\: x^2 = 1\:$ has four roots $\rm\: x = \pm 1,\ \pm 3.\ \$ – Bill Dubuque Nov 5 '12 at 15:42