How to solve a non-factorable quadratic congruence

We will see how to solve a non-factorable quadratic congruence by completing the square and also a clever trick. This is a fun math topic in number theory or discrete math!

[Ni]

"We can do it because we have this powerful green marker..."

_Perfect!_ Seriously, perfect.

[thedoublehelix]

Method #3: Check all the numbers from 0-6 to see if any of them work

[holyshit]

x_{1}=3+7k_{1}
x_{2}=2+7k_{2}
where k_{1} and k_{2} in Z
Calculated mentally and used 2nd version - the factorization

[jeremy]

And i just started learning modular arithmetic today, thank you!!!!

[SmileyMPV]

In general you can actually just use the quadratic formula. For the square root you just have to calculate the quadratic residue. Since the quadratic residues of 2 mod 7 are 3 and 4, we find x=-1+3=2 and x=-1+4. Interestingly, some numbers don't have a quadratic residue mod 7, for example 3. This means that some quadratic equations, such as x^2+2x-2=0mod7, do not have any solutions.

[balancedactguy]

Can you give an introduction to TENSORS??

[robertlozyniak]

Because it is "mod 7", there are only seven possible cases that you need to look at. You could plug in x=0, x=1, and so forth, up to x=6, and see which values of x actually work.

[dwaipayandattaroy]

Tell honestly that hasnt you mugged up this thing, you are patient, kudos

[JM-usfr]

This is pretty cool! I hope you make more number theory videos

[WildAnimalChannel]

I don't know why but I don't like modular arithmetic. It just feels like counting gone wrong!

[Jordan-zkwd]

x^2+2x+1=2 mod 7
x^2+2x+1=9 mod 7

Doesn't that also mean:

x^2+2x+1=16 mod 7 (because 9+7=16).

Therefore:

(x+1)^2=4^2 mod 7
x+1=4 mod 7 and x+1=-4 mod 7
x=3 mod 7 and x=-5 mod 7
Adding 7 to the last one, we get...

Wait x=3 and x=2, same solutions opposite order. Huh.

Is it always as easy as checking one case (9 is enough and 16 is unnecessary) for all quadratic equations mod some prime?

[ericthegreat]

You can also do
X2+2x=-1 mod7 = 6 mod7
X2+2x-6=0 mod7
(X-3)(x-2) = 0 mod7
X = 2 mod 7, 3 mod 7

[deidara_]

x^2 + 2x - 1 = 0 (mod 7)

x^2 + 2x = 1 mod 7
x + 2 = inv(x) mod 7
15 = 3*5 = 1 mod 7
3 + 2 = inv(3) mod 7
x = 3 mod 7
8 = 2*4 = 1 mod 7
x = 2 mod 7

x = 2 or 3 mod 7

Of course that only works here because we easily found 15 and 8. A more general solution would require the quadratic formula, of course keepin in mind that division would have to be replaced with multiplying with the inverse, and the square root would be calculated with Tonelli-Shanks

[jzanimates]

Can you try to differentiate x! using the definition of factorial as pi or gamma function plz!!!

[superjugy]

Oh shit, green pen! This is getting serious now

[nicholasleclerc]

If all this is 0 modulus 7, then that means the answer is a *multiple* (i.e. “k”) of 7, right ?

Then:
x^2+2x-1=7k
x^2+2x-(7k+1)=0
x=-1+/- sqrt(-28k-3)
x=-1 +/- i*sqrt(28)*sqrt(k+3/28)

So:
k<-3/28
k belongs (-Inf, -1]

[BeauBreedlove]

You could also change it to x^2+2x-15 and factor that to (x-3)(x+5) to get x=3 or x=2


Or you can factor the original x^2+2x-1 to (x-2)(x-3) knowing that -2 * -3 is congruent to -1 (mod 7) and -2 - 3 is congruent to 2 (mod 7)

[thetetrix]

Juste make a congruence table and take values from 1to7

[helloitsme]

Another way: substitute x=7k+c, then thus we have to find c between 0 and 7 for which c^2+2c-1 is congruent to 0 mod 7. And then check for all those numbers

[jonathanhanon]

I just did it as x^2 + 2x - 1 = x^2 - 5x + 6 = (x-3)(x-2) mod 7