Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to figure out whether the following quadratic congruence is solvable: $3x^2+6x+5 \equiv 0\pmod{89}$.

It's impossible to divide $3x^2+6x+5$ to a form of $f(x) \cdot g(x)=3x^2+6x+5$ and then to check whether $f(x)\equiv 0 \pmod{89}$ or $g(x)\equiv 0(89)$, but $3x^2+6x+5 \equiv 0\pmod{89}$ is equal to $3(x+1)^2+2 \equiv 0\pmod{89}$ or $3(x+1)^2 \equiv -2\pmod{89}$ or $3(x+1)^2 \equiv 87\pmod{89}$ or $(x+1)^2 \equiv 29\pmod{89}$. for $y=x+1$, I need to determine whether $y^2 \equiv 29\pmod{89}$ is solvable, and it is not. Am I able to conclude something about the original equation in this way? what is the correct way to solve this problem?

Thanks a lot!

share|improve this question
2  
Yes. This is the way to do it. You need check, whether 29 is a quadratic residue modulo 89. A standard way of reducing the number to manageable size is to use quadratic reciprocity (it works well, when you can factor the integers such as here). Alternatively you can check, whether the discriminant $$d=b^2-4ac=6^2-4\cdot3\cdot5\equiv 65\pmod{89}$$ is a quadratic residue. –  Jyrki Lahtonen May 20 '12 at 12:45
    
@anon: Yes, you are right. I fixed it. Thanks! –  Jozef May 21 '12 at 9:08

2 Answers 2

up vote 8 down vote accepted

Yes, your inference is correct. Essentially it is a special case of the well-known discriminant test. Namely, 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 R (so in $ \mathbb Z/89 = $ integers mod $89$), viz. $$\rm\: \ \ 4a\:(a\:x^2 + b\:x + c = 0)\:\Rightarrow\: (2a\:x+b)^2 =\: b^2 - 4ac $$

When learning about (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).

share|improve this answer

If you know about the law of quadratic reciprocity, it gives you a way to tell whether $y^2\equiv29\pmod{89}$ is solvable.

Here's how it goes: Since 29 and 89 are both prime and congruent 1 mod 4, $y^2\equiv29\pmod{89}$ is solvable if and only if $y^2\equiv89\pmod{29}$ is solvable. That reduces to $y^2\equiv2\pmod{29}$. Then there's a little result that says if $p$ is an odd prime then $y^2\equiv2\pmod p$ is solvable if and only if $p\equiv\pm1\pmod8$.

There's more to quadratic reciprocity than what I've done here. It's in every intro number theory text, and all over the web.

share|improve this answer
    
As I wrote in the question, I know whether it is solvable or not. I am talking about the original equation where $y=x+1$ and asking whether I can conclude about the original equation by knowing that $y^2=29(mod 89)$ is not solvable. –  Jozef May 20 '12 at 12:45
1  
Sorry. Yes, your approach to deciding whether the original congruence is solvable is fine---provided you have some way to decide whether $y^2\equiv29\pmod{89}$ is solvable. Evidently, you have some way to do this, but what? Quadratic reciprocity will generally be the quickest way to decide. –  Gerry Myerson May 20 '12 at 12:54
    
I did it the same way you did, I just wasn't sure whether it was correct to conclude from y to x regarding the solution of the congruence. Thanks Gerry! –  Jozef May 20 '12 at 12:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.