Question

How to solve quadratic congruences?

Answer 1

For example x^2-6x+1 = 0 mod 31

When our professor did the problem in class they got x = 12, 13
But wolfram alpha says the solutions are 18 and 19

Who's wrong here? If my professor is wrong, what is the correct way to go about the problem?

Answer 2

start by completing the square

Answer 3

So x^2-6x+1+8 = 8 mod 31
(x-3)^2 = 8 mod 31?

Answer 4

let x-3 = y and the congruence is
\[y^2\equiv 8\pmod{31}\]

Answer 5

Sorry just looking things up real quick

Answer 6

clear so far right ?
nothing fancy, just substituted x-3 = y

Answer 7

Yes, and I've seen people online mention that x^2 = a mod p is solving for the quadratic residue

Answer 8

So I'm just trying to figure that out

Answer 9

Since the modulus, 31, is small you may simply check 1-30 integers to see which one satisfies the congruence above

Answer 10

there is a direct formula though, which is not so interesting

Answer 11

Mind just posting the formula in case the mod is large?

Answer 12

If \(p\equiv 3\pmod{4}\) and if a solution exists, then the solutions to quadratic congruence \(x^2\equiv a\pmod{p}\) are :
\[x\equiv \pm a^{(p+1)/4}\pmod{p}\]

Answer 13

Since \(31\equiv 3\pmod{4}\), the solutions to \(y^2\equiv 8\pmod{31}\) are :
\[y\equiv \pm 8^{(31+1)/4}\pmod{31}\]

simplify

Answer 14

So x = 3+- 8 mod 31?

Answer 15

what do you get for \(y\) ?

Answer 16

Or wait 16 my bad.

Answer 17

x=3+-16 mod 31?

Answer 18

\[y\equiv \pm 8^{(31+1)/4}\equiv \pm 16\pmod{31}\]

and we have
\[x-3\equiv y\pmod{31}\]
therefore
\[x-3\equiv \pm 16\pmod{31}\]

Answer 19

This might be a dumb question and me not having completed the square before, but what if the second term is odd?

Like one problem has 2x^2+5x-7 = 0 mod 17
-> x^2 + 11x +5 = 0 mod 17?

Answer 20

Not having completed the square in a while* I've done it before =p

Answer 21

based on your teachers answer it looks like he actually solved
http://www.wolframalpha.com/input/?i=%28x%5E2%2B6x%2B1%29+congruent+0+%28mod+31%29
which kinda looks similar what you guys had after completing the square except you know there is a + between the x and 3 instead of a minus sign
\[(x+3)^2 \equiv 8 (\mod 31)\]
still involves solving the following first:
\[u^2 \equiv 8 (\mod 31)\]
where u=x+3
---anyways
you would get
\[u \equiv 16,(-16+31)=16,15 (\mod 31) \\ x+3=16, 15 (\mod 31) \\ x \equiv (16-3),(15-3) (\mod 31) \\ x \equiv 13,12 (\mod 31)\]
just in case you wanted to know how your teacher got his answer (and this is my prediction anyways)

Answer 22

Oh yeah, looking at work thing he has up now I'm surprised I didn't catch the typo before.

Answer 23

\[ax^2+bx+c \\ a(x^2+\frac{b}{a}x)+c \\ a(x^2+\frac{b}{a}x+(\frac{b}{2a})^2)+c-a (\frac{b}{2a})^2 \\ a(x+\frac{b}{2a})^2+c-a \frac{b^2}{4a^2} \\ a(x+\frac{b}{2a})^2+c-\frac{b^2}{4a} \\ a(x+\frac{b}{2a})^2+\frac{-b^2+4ac}{4a}\]

Answer 24

That makes me feel a lot better

Answer 25

as you can see multiplying each side by \(4a\) does the trick

Answer 26

both the congruences are equivalent as \(4\nmid 17\)

Answer 27

typo fixed\[ x^2 + 11x +5 \equiv 0 \pmod{17}\]

multiply each side by \(4\) and get
\[4x^2+4*11x+4*5\equiv 0\pmod{17}\]

now try completing the square

Answer 28

So 44 mod 17 -> 10x, which you can't factor a 4 out of?

Answer 29

let me do something a little further to what I have
\[ax^2+bx+c \\ a(x^2+\frac{b}{a}x)+c \\ a(x^2+\frac{b}{a}x+(\frac{b}{2a})^2)+c-a (\frac{b}{2a})^2 \\ a(x+\frac{b}{2a})^2+c-a \frac{b^2}{4a^2} \\ a(x+\frac{b}{2a})^2+c-\frac{b^2}{4a} \\ a(x+\frac{b}{2a})^2+\frac{-b^2+4ac}{4a} \\ a(\frac{2ax+b}{2a})^2+\frac{-b^2+4ac}{4a} \\ a \frac{(2ax+b)^2}{(2a)^2}+\frac{-b+4ac}{4a} \\ a \frac{(2ax+b)^2}{4a^2}+\frac{-b^2+4ac}{4a} \\ \frac{(2ax+b)^2}{4a}+\frac{-b^2+4ac}{4a} \\ \frac{(2ax+b)^2-b^2+4ac}{4a}\]
there now it should be more obvious to multiply both sides by 4a

Answer 30

Okay that's pretty neat. Thank you so much for all your help

Answer 31

and we can only do that as long as 4a doesn't divide the number we are modding right @ganeshie8

Answer 32

All the questions I see have prime mod so I don't think it should be an issue otherwise

Answer 33

Again, thanks so much both of you

Answer 34

we should be able to come up with a general formula for
\[ax^2+bx+c \equiv 0 (\mod q) \text{ where } 4a \cancel{ |}q \]
I think

Answer 35

Exactly! \(x\equiv y\) is not same as \(ax\equiv ay\)
however \(x\equiv y\implies ax\equiv ay\) is correct though

Answer 36

\[\frac{(2ax+b)^2-b^2+4ac}{4a} \equiv 0 (\mod q ) \\ (2ax+b)^2-b^2+4ac \equiv 0 (\mod q ) \\ (2ax+b)^2 \equiv b^2-4ac (\mod q ) \\ 2ax+b \equiv \pm (b^2-4ac)^\frac{q+1}{4} (\mod q ) \\ 2ax \equiv -b \pm (b^2-4ac)^\frac{q+1}{4} (\mod q) \]

Answer 37

so then you have a linear congruence equation to solve

Answer 38

looks neat! but that works only if \(q\) is a prime of form \(4k+3\)
notice \((q+1)/4\) produces an integer only when \(q\) is of above form

Answer 39

oh yeah lets add that in there :p

Answer 40

or that restriction I mean

Answer 41

I kinda would like to look at other cases too
but I have to do some chore type things

Answer 42

there is only one other case to look at \(p=4k+1\)
no direct formula this

Answer 43

at least not so simple direct formula..

Answer 44

sounds like something to play with if I get a chance
peace guys

Answer 45

In above example \(17\) is not of form \(4k+3\), so we cannot use that direct formula

Answer 46

@ganeshie8 Sorry to bother you again, so I've tried using freckles formula (I'd also seen it elsewhere) but it's just not returning what I would expect from wolfram.

2x^2 +5x -7 = 0 mod 17

=>

(4x+5)^2 = 25+4(2)(7) mod 17
(4x+5)^2 = 13 mod 17
4x+5 = +-16 mod 17
x= 7,16

But wolfram is telling me I should get 1,5.

What am I doing wrong here?

Answer 47

(4x+5)^2 = 13 mod 17

looks good till that step

Answer 48

in the next step, how did get 4x+5 = +- 16 mod 17

Answer 49

I found a table of values, but I don't think it even applies. My bad.

Answer 50

So for squares I should just guess and check values most of the time?

Answer 51

(4x+5)^2 = 13 mod 17

let 4x+5 = y and you have

y^2 = 13 mod 17

Answer 52

1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16
5^2 = 25 = 8
6^2 = 36 = 2
7^2 = 49 = 15
8^2 = 64 = 13

so we're done, 8 is a solution to y^2 = 14 mod 17

Answer 53

Alright. Thank you

Answer 54

And if no values return anything there's just no solution correct?

Answer 55

Notice, since 8 is a solution to y^2 = 13 mod 17, the integer 17-8 will also be a solution

Answer 56

In general :
if \(x=x_0\) is a solution to \(x^2\equiv a\pmod{p}\), then \(p-x_0\) is the second solution.

Answer 57

you're correct, but isn't that kinda obvious

Answer 58

Haha yeah. Okay then, again thank you.

Answer 59

studied euler's criterian yet ?

Answer 60

euler's criterian is one "not so fast" way of knowing whether a quadratic congruence admits a solution or not