how to solve a non-factorable quadratic congruence
Vložit
- čas přidán 10. 09. 2024
- 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: 👉 • solving a quadratic co...
Subscribe for more math for fun videos 👉 bit.ly/3o2fMNo
💪 Support this channel, / blackpenredpen
🛍 Shop math t-shirt & hoodies: bit.ly/bprpmerch. (10% off with the code "WELCOME10")
🛍 I use these markers: amzn.to/3skwj1E
"We can do it because we have this powerful green marker..."
_Perfect!_ Seriously, perfect.
Method #3: Check all the numbers from 0-6 to see if any of them work
Do a mod 6 next time!
And i just started learning modular arithmetic today, thank you!!!!
Can you give an introduction to TENSORS??
I'd love to see BPRP tackle tensors but if you want, Andrew Dotson has a great ongoing series on the topic right now
@@dectorey7233 Thank You!
Tell honestly that hasnt you mugged up this thing , you are patient , kudos
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
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?
Oh shit, green pen! This is getting serious now
I don't know why but I don't like modular arithmetic. It just feels like counting gone wrong!
This is pretty cool! I hope you make more number theory videos
5:02 "indi-k"
Gordon Chan hahhahaha
Can you try to differentiate x! using the definition of factorial as pi or gamma function plz!!!
Once I did it and the result was in terms of psi(x) a special function I had never heard about
@@srpenguinbr That's the digamma function.
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.
I just did it as x^2 + 2x - 1 = x^2 - 5x + 6 = (x-3)(x-2) mod 7
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.
I'm trying to click on the in video, "Video" Link that says, "Chen Lu" and Dr. ¿Peyam? ... where is that video.
Thank you very much, i was stuck in a quadratic congruence like that and you helped me .. all respect
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
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
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
So using mod 7 means we can add as many 7s as we want to the righthand side because there is no remainder?
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
@@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
Juste make a congruence table and take values from 1to7
your vidoes are so useful
Very cool! Thanks for posting!
Nice😍😍thx
I hope there are more of number theory videos. Thanks for the videos😁
Where i can get this subject? I dont get it in high school
its anything related to modular algebra. usually given in abstract algebra or number theory
You will find this in basic NumberTheory. See if you can find an "Introductory Number Theory" book.
yep, just go for number theory.
Are you only restricted to integers in modular arithmetic?
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.
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.
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)
IS THIS ALLOWED??
You are a life saver!
Great video!
Excellent video and thought-provoking material as usual! It's got me wondering about cubic congruences now...
Marcus Hendriksen
It’s just crazier. : )
Thanks man! That was so cool.
You should do geometry.
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
Good one! 😂
you areThe Brilliant one keep it up
Really good,,, sir
Very good
Wow~that's amazing
1 step seems forced logic like nah ? But solvable a+b whole sq , what training impact on mind
Very nice
From Algebra I to Either an advanced form of Calculus or Pre-Calc.
advanced?
Bro that intro was so gangsta my supreme boi
Goes to show how cool math really is
Good bro keep on
Nice subjct thanks a lot for u
How can I send you a problem?🤔
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
@Blackpenredpen you can solve this : ∫1/(e^x + e^-x +1) dx ?
可能加了別的倍數也是解，怎麼證明這就是全部的解？
What about non prime numbers in place of 7?
That's a very general question.
And my very general answer would be: use the Chinese remainder theorem.
Amazing
What about some integrals again?
👍
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.
That intro 😂
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
I have some problems in 3 dimensional geometry
Can you do a day in my life?
but what about (x+1)^2=16mod7? since 16mod7=2mod7
That will give you x+1=+-4 (mod 7).
x=3,-5 (mod 7).
x=2,3 (mod 7).
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.
Can we differentiate both sides of the congruence?
Video on cycloids next?
Sir what is the answer of X^2 congruent 27(mod59)
Can you integrate cos (x^2) next , hint : use taylor series
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
You should run in 2020
What if it is even?
Even means not prime so...
Ah, the elusive green pen
If there is any coefficient in x² then what should to do ???
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
doraemon in the middle of the video
Up the mods.
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
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.
Make a video of mod is even..
John Aries Sarza I have another video when mod is composite. See description
blackpenredpen thanks bprp.. hope i can meet you personally. Always watching your tutorial blog, thanks.
@@johnariessarza3622 : ))))) Thank you!!
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
Jabir Fatah I like it!!!
so... what do you do if it isn't prime?
mrBorkD I have that video in the video already. It’s unlisted so be the first few to watch!! : )
@@blackpenredpen oh cool, thanks
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.
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!)
When the congruence has no solution
؟
BRO PLZ SPEAK LITTLE BIT LOUDER
SORRY BRO MY EAR PHONE HAD A PROBLEM
BY THE WAY YOU ARE A BI..CH
1st like
I think 2nd