How to solve a non-factorable quadratic congruence

Подписаться 1,3 млн

Просмотров 49 тыс.

50% 1

Learn how to solve a non-factorable quadratic congruence with prime modulus. Then check out brilliant.org/... and try their daily problems now.
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!
Check out an example if the module isn't prime: 👉 • How to solve a quadrat...
💪 Support this channel, / blackpenredpen

Опубликовано:

14 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 111

@Ni999 5 лет назад

"We can do it because we have this powerful green marker..." _Perfect!_ Seriously, perfect.

@wongbob4813 5 лет назад

Do a mod 6 next time!

@jeremy2719 5 лет назад

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

@thedoublehelix5661 4 года назад

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

@JM-us3fr 5 лет назад

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

@balancedactguy 5 лет назад

Can you give an introduction to TENSORS??

@dectorey7233 5 лет назад

I'd love to see BPRP tackle tensors but if you want, Andrew Dotson has a great ongoing series on the topic right now

@balancedactguy 5 лет назад

@@dectorey7233 Thank You!

@holyshit922 5 лет назад

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

@dwaipayandattaroy9801 5 лет назад

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

@petermhart Год назад

Very cool! Thanks for posting!

@SmileyMPV 5 лет назад

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.

@jzanimates2352 5 лет назад

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

@srpenguinbr 5 лет назад

Once I did it and the result was in terms of psi(x) a special function I had never heard about

@maxwongpt2channel328 5 лет назад

@@srpenguinbr That's the digamma function.

@marcushendriksen8415 5 лет назад

Excellent video and thought-provoking material as usual! It's got me wondering about cubic congruences now...

@blackpenredpen 5 лет назад

Marcus Hendriksen It’s just crazier. : )

@BeauBreedlove 5 лет назад

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)

@Sesquipedalia Год назад

IS THIS ALLOWED??

@helloitsme7553 5 лет назад

Another way: substitute x=7k+c, then (7k+c)^2+2(7k+c)-1=49k^2+14kc+c^2+14k+2c-1=7(7k^2+2kc+2k)+c^2+2c-1 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

@reeeeeplease1178 Год назад

Good one! 😂

@nicholasleclerc1583 5 лет назад

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

@salmamuhammad5416 3 года назад

Thank you very much, i was stuck in a quadratic congruence like that and you helped me .. all respect

@ericthegreat7805 2 года назад

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

@satoruai3475 2 года назад

I hope there are more of number theory videos. Thanks for the videos😁

@robertlozyniak3661 5 лет назад

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.

@WildAnimalChannel 5 лет назад

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

@Daydreamer-h1t 4 года назад

your vidoes are so useful

@theactualbowmonk 5 лет назад

So using mod 7 means we can add as many 7s as we want to the righthand side because there is no remainder?

@Domestofobia 5 лет назад

yes, in congruences you can replace anything with anything as long as they are im the same /remain group/(not sure if it is called this in english but for example x :=: y (mod n) then you can replace x with y

@ahmedbenlahrech5352 3 года назад

@@Domestofobia Exactly , thats what differentiates modular arithmetics from standard math but the type of problems and questions asked in this field is kinda hard ngl

@Quadratic4mula 5 лет назад

I'm trying to click on the in video, "Video" Link that says, "Chen Lu" and Dr. ¿Peyam? ... where is that video.

@deidara_8598 3 года назад

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

@Jordan-zk2wd 5 лет назад

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?

@mathforbem 5 лет назад

Nice😍😍thx

@andywright8803 5 лет назад

Are you only restricted to integers in modular arithmetic?

@willnewman9783 5 лет назад

Modular arithmetic refers to only doing things in the integers, I believe. You can extend it to all real numbers, but only addition makes sense in this realm.

@WilliamLeeSims 5 лет назад

Not unless your solution requires it. For example, 12 mod 6.28 = 5.72. In that example, you have an angle of 12 radians which is one turn around the circle (2 pi) plus another 5.72 radians. Another example is the sawtooth wave function y = x - floor(x); I like to think of it instead as y = x mod 1.

@gordonchan4801 5 лет назад

5:02 "indi-k"

@blackpenredpen 5 лет назад

Gordon Chan hahhahaha

@amaliacoughlan7071 4 года назад

Thanks man! That was so cool.

@jonathanhanon9372 3 года назад

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

@superjugy 5 лет назад

Oh shit, green pen! This is getting serious now

@KatzKitz10 5 лет назад

Where i can get this subject? I dont get it in high school

@98danielray 5 лет назад

its anything related to modular algebra. usually given in abstract algebra or number theory

@balancedactguy 5 лет назад

You will find this in basic NumberTheory. See if you can find an "Introductory Number Theory" book.

@Rafael-oq9vu 5 лет назад

yep, just go for number theory.

@lonigaming5880 5 лет назад

Great video!

@thetetrix4474 5 лет назад

Juste make a congruence table and take values from 1to7

@hero947 5 лет назад

@Blackpenredpen you can solve this : ∫1/(e^x + e^-x +1) dx ?

@mathematicsanalysis7213 5 лет назад

Really good,,, sir

@swarnakshi_official8533 5 лет назад

Sir what is the answer of X^2 congruent 27(mod59)

@lakhwinderhairtransplantco6803 5 лет назад

I have some problems in 3 dimensional geometry

@solomonbirhane3648 5 лет назад

you areThe Brilliant one keep it up

@أبوبراء-ظ5ي 3 года назад

Very good

@6c15adamsconradwilliam3 4 года назад

Can we differentiate both sides of the congruence?

@dwaipayandattaroy9801 5 лет назад

1 step seems forced logic like nah ? But solvable a+b whole sq , what training impact on mind

@srpenguinbr 5 лет назад

Maybe you could that the quadratic is equal to 7k and use the quadratic formula. Then, use those formulas for the pithagorean triples and find what values for k give an integer solution to x

@shandyverdyo7688 5 лет назад

What about some integrals again?

@AaronHe 5 лет назад

You should do geometry.

@thebloxxer22 5 лет назад

From Algebra I to Either an advanced form of Calculus or Pre-Calc.

@98danielray 5 лет назад

advanced?

@ΑΝΤΩΝΗΣΠΑΠΑΔΟΠΟΥΛΟΣ-ρ4τ 2 года назад

or just complete the square lol. x^2+2x+1-2=0 x^2+2x+1= 2 (x+1)^2 = 2 x+1 = sqrt(2) x sqrt(2)-1 OOOOR x+1= -sqrt(2) x = -sqrt(2) - 1. or just use the determinant lol

@christiansmakingmusic777 2 года назад

You can’t take the square root unless it is a quadratic residue. Only half the non-zero residues are quadratic residues. 1,2,4 are the quadratic residues, 3,5,6 have no square root over the finite field of integers modulo seven.

@hassanalihusseini1717 5 лет назад

If you have x^2+2x-1==0 mod 7 it is much easier to try all possible reminders: 0: 6 1: 2 2: 0 This is a solution 3: 0 This is also a solution. 4: 2 5: 6 6: 5

@drpeyam 5 лет назад

That intro 😂

@xcalibur6482 5 лет назад

How can I send you a problem?🤔

@DarrenMcStravick 5 лет назад

Bro that intro was so gangsta my supreme boi

@LS-Moto 5 лет назад

Goes to show how cool math really is

@radouaniabdelhadi332 5 лет назад

Very nice

@DeepakKumar-qv1zb 5 лет назад

Good bro keep on

@wojtek9395 5 лет назад

What about non prime numbers in place of 7?

@ivan1793 5 лет назад

That's a very general question. And my very general answer would be: use the Chinese remainder theorem.

@conorbrennan5838 5 лет назад

Can you integrate cos (x^2) next , hint : use taylor series

@nicolassamanez6590 5 лет назад

but what about (x+1)^2=16mod7? since 16mod7=2mod7

@skallos_ 5 лет назад

That will give you x+1=+-4 (mod 7). x=3,-5 (mod 7). x=2,3 (mod 7).

@Theraot 5 лет назад

Ends up the same, even if you take (x+1)^2 = 2+7*14 (mod 7) or any other square of the form 2+7n. Note: 2+7*14 = 100. Proof? Hmm... This is what I have been able to come up with: Any other square you can build form adding 7 multiple times to 9 will be 2+7+7m where m is positive integer... And must be a square, at least equal to 9 = 3^2. Thus, 2+7+7m = 9 + 7m = (3 + k)^2 => 9 + 7m = (3 + k)^2 => 9 + 7m = 3^2 + 2(3)k + k^2 => 9 + 7m = 9 + 6k + k^2 => 7m = 6k + k^2 Given that 6 = 2 * 3, 6 does not share factors with 7, thus this factor must come from m.... 7a +7(6)b = 6+k^2 => 6 = 7(6)b 7a = k^2 Given that 7a must be a square, therefore a must be a multiple of 7, in fact, it must be a square by 7: a = 7c^2 => 7(7c^2) = k^2 => 7c = k Or simply, given that we know that 6k = 7(6)b => k = 7b We conclude that k must be a multiple of 7, in other words k = 0 (mod 7) Alright, go back to (x+1)^2 = 2 (mod 7) knowing that 7m = 0 (mod 7) and 7m = 6k + k^2 => (x+1)^2 = 2 + 7 (mod 7) => (x+1)^2 = 2 + 7 + 7m (mod 7) => (x+1)^2 = 2 + 7 + 6k + k^2 (mod 7) => (x+1)^2 = 9 + 6k + k^2 (mod 7) => (x+1)^2 = 9 + 2(3)k+k^2 (mod 7) => (x+1)^2 = (3 + k)^2 (mod 7) => (x+1)^2 = (3 + k)^2 (mod 7) => (x+1)^2 = (3 + k)^2 (mod 7) => x + 1 = 3 + k (mod 7), x + 1 = -3 - k (mod 7) => x = 2 + k (mod 7), x = -4 - k (mod 7) And since we know that k = 0 (mod 7): x = 2 + k (mod 7), x = -4 - k (mod 7) => x = 2 (mod 7), x = -4 (mod 7) => x = 2 (mod 7), x = 3 (mod 7) That is the same result on the video (4:36), this shows that the selection of square is irrelevant for this case.

@呂永志-x7o 5 лет назад

可能加了別的倍數也是解，怎麼證明這就是全部的解？

@muhammadqasim7056 5 лет назад

Video on cycloids next?

@snigdhasahoo9952 4 года назад

If there is any coefficient in x² then what should to do ???

@ZipplyZane 11 месяцев назад

Then you divide all the terms by the the coefficient. Since you divide by the same thing on both sides, the equation remains valid, and thus it doesn't mess up the value of x. So, say, 3x²+4x=-3 becomes x²+(4/3)x=-1

@newtonnewtonnewton1587 5 лет назад

Nice subjct thanks a lot for u

@josephhtoo1 5 лет назад

Can you do a day in my life?

@mryip06 3 года назад

Amazing

@UrViridescentLeaf 5 лет назад

👍

@Random12260 4 года назад

Ah, the elusive green pen

@diederickfloor4261 4 года назад

why doesn't this work: x^2 + 2x - 1 cong. 0 mod 7 x^2 + 2x cong. 1 mod 7 x(x + 2) cong. 1 mod 7 x cong. 1 mod 7 x + 2 cong 1 mod 7 x cong. 6 mod 7 edit: I know line 4 is not justified you can only split the factors with 0 mod n.

@scimaniac 5 лет назад

What if it is even?

@onlystudy5733 5 лет назад

Even means not prime so...

@thomaswilliams9320 5 лет назад

You should run in 2020

@BigDBrian 5 лет назад

so... what do you do if it isn't prime?

@blackpenredpen 5 лет назад

mrBorkD I have that video in the video already. It’s unlisted so be the first few to watch!! : )

@BigDBrian 5 лет назад

@@blackpenredpen oh cool, thanks

@ssdd9911 5 лет назад

doraemon in the middle of the video

@RexxSchneider 3 года назад

At 4:32 "Two answers - that's it, right?" Not really. You failed to consider that 4^2 is also congruent to 2 mod 7. Now, it turns out that we will end up with the same values for x, but how is the viewer to know that will always be the case? It is in fact true that quadratic residues (mod p) occur in pairs in Z/pZ, if p is an odd prime, but that also isn't obvious to the viewer, and you haven't proven it. You can also use the quadratic formula directly to find solutions by changing from a congruence to an equality with an extra (integer) variable: x^2 + 2x - 1 ≡ 0 mod 7 is equivalent to x^2 + 2x - 1 = 7n where n is an integer. So x^2 + 2x - (1 + 7n) = 0 and we can use the quadratic formula: x = (-2 ± √(4 + 4(1+7n)))/2 = -1 ± √(1 + 1+7n) after diving top and bottom by 2 x = -1 ± √(2+7n) but we require integer solutions, so the term inside the square root must be a perfect square, which we can call m^2 x = -1 ± m where m^2 = 2 + 7n. The condition m^2 = 2 + 7n is equivalent to m^2 ≡ 2 mod 7 and the only values of m that have quadratic residues of 2 mod 7 are m=3 and m=4 mod 7. So either m = 3 + 7k or m = 4 + 7k where k is an integer. That gives x = -1 ± (3 + 7k), producing x = 2 + 7k or x = -4 - 7k; or x = -1 ± (4 + 7k), producing x = 3 + 7k or x = -5 - 7k. But -4 - 7k gives the same set of numbers as 3 + 7k does, and -5 - 7k gives the same set of numbers as 2 + 7k does, as k takes on all positive and negative values. The complete set of x values may therefore be summarised as 2 + 7k and 3 + 7k.

@isaacmojica3463 4 года назад

Dude you're very awsome. I was looking this kind of way s¡to solve that equiation for hours an nothing: Ty. This is a beautiful simple way and easy to understand :D

@rogerkearns8094 5 лет назад

Up the mods.

@johnariessarza3622 5 лет назад

Make a video of mod is even..

@blackpenredpen 5 лет назад

John Aries Sarza I have another video when mod is composite. See description

@johnariessarza3622 5 лет назад

blackpenredpen thanks bprp.. hope i can meet you personally. Always watching your tutorial blog, thanks.

@blackpenredpen 5 лет назад

@@johnariessarza3622 : ))))) Thank you!!

@jabir5768 5 лет назад

How to be good at maths: 1) Be crazy about maths 2)There is no number 2 3)There is no number 3 ... n)There is no number n Pls validate my worthless existence

@blackpenredpen 5 лет назад

Jabir Fatah I like it!!!

@garavelustagaravelusta9717 4 года назад

Better Solution: x^2 + 2x = 1mod7 x(x+2) = 1 mod7 (x+2) = (1/x)mod7 Find pair elements in mod7 such that their multiplication is equal to 1 in mod7. (Hence they form a pair of x and 1/x) Pair 1: 1 1 x+2 = 1mod7 and x = 1mod7 ? No solution for the system! Pair 2: 2 4 (8 = 1mod7) Option 1: x = 2mod7 and x+2 = 4mod7 x = 2mod7 (Valid) Option 2: x = 4mod7 and x+2 = 2mod7 -> x=0mod7 (Not Valid!) Pair 3: 3 5 (15 = 1mod7) Option 1: x = 3mod7 and x+2 = 5mod7 x = 3mod7 (Valid) Option 2: x = 5mod7 and x+2 = 3mod7 -> x = 1mod7 (Not Valid!)