Could someone please give me pointers on how to solve this quadratic congruence? Thanks!!

Question

sepeario · Answer

attachment

fwizbang · Answer

When you say  $$x^2 +6x+10= 0 (mod  17)$$ 
you mean that  $$x^2 +6x+10= 17N $$  for some integer N.

kainui · Answer

Since $10 \equiv -7 \mod 17$ I plugged it in and got:

$$x^2+6x-7 \equiv 0 \mod 17$$

And then I just got lucky because some math teacher made this problem up to work nicely.

$$(x-1)(x+7) \equiv 0 \mod 17$$

So now the solutions are just like in regular algebra,

$$x \equiv 1$$$$x \equiv -7$$

Although people sometimes don't like negative numbers in modular arithmetic so you can replace that -7 with 10.

sepeario · Answer

Thanks, but could you please explain again how you got from the first step to the second? @Kainui

kainui · Answer

I don't really know what the first or second steps I took were, can you be more specific?

sepeario · Answer

"Since 10≡−7mod17 I plugged it in and got:

x2+6x−7≡0mod17"

kainui · Answer

Ah ok this is what I plugged in:

$$x^2+6x+10 \equiv x^2+6x-7 \mod 17$$

sepeario · Answer

but x^2+6x-7 is not equal to 0? sorry I don't understand the addition and stuff so I don't really understand the plugged in bit.

kainui · Answer

It is equal to 0 I just didn't write that right there in my last post is all

kainui · Answer

This is your problem:
$$x^2+6x+10 \equiv 0 \mod 17$$
This is the substitution I made:
$$ x^2+6x-7 \equiv 0 \mod 17$$

All I did was change 10 into -7 because in mod 17 they are congruent. Congruent is what that triple equals sign is, it's not the same as equals but similar. Tell me what you know about modular arithmetic if you're still feeling confused and I'll try to help you maybe fix your misconceptions or help your understanding.

zepdrix · Answer

Here is another way to think of the step he applied, if it helps at all.
Subtracting 17 from each side,
$\large\rm x^2+6x-7=-17$
But -17 is congruent to 0 in mod17, ya?
$\large\rm x^2+6x-7=0$

sepeario · Answer

oh, I understand now, so you're saying that the answer to -7 mod 17 is the same as 10 mod 17, right?

sepeario · Answer

and so i just use null factor law to find the solutions to the quadratic? @Kainui  @zepdrix

ganeshie8 · Answer

Yes. That works nicely here as it gives you two different solutions, and two solutions is what you need for a quadratic congruence.
 
Be careful though, this "null factor law" doesn't work for congruences in general. There is no guarantee that you get all the solutions using this law. Consider below for example : 

$2*3 \equiv 0 \mod 6$ doesn't imply $2\equiv 0$ or $3\equiv 0$

sepeario · Answer

Ok thank you @ganeshie8 , so just to make sure, that means that the solutions for the quadratic congruence would be 1 and -7?

ganeshie8 · Answer

Its considered a crime to ask such a question when you can simply plugin the values in the quadratic to check if they are indeed the solutions ;)

ganeshie8 · Answer

Solving 
x^2 + 6x + 10 = 0 mod 17

is exactly same as finding the integers x that make the expression x^2 + 6x + 10 divisible by 17.

ganeshie8 · Answer

You may plugin x = 1, -7 in the quadratic, and if it is divisible by 17, it is a solution.