A Modular Arithmetic Equation | Number Theory
Vložit
- čas přidán 20. 05. 2023
- ⭐ Join this channel to get access to perks:
/ @sybermath
⭐SUBSCRIBE to MAIN CHANNEL → www.youtube.com/@SyberMath?su...
⭐ SUBSCRIBE to SHORTS Channel → www.youtube.com/@SyberMathSho...
⭐Follow me → / sybermath
#shorts #shortsvideo #shortsyoutube
via @CZcams @Apple @Desmos @NotabilityApp @googledocs @canva
(x+1)² ≡ 2 (mod 7)
a ≡ 0 (mod 7) ⇒ a² ≡ 0 (mod 7)
a ≡ 1 (mod 7) ⇒ a² ≡ 1 (mod 7)
a ≡ 2 (mod 7) ⇒ a² ≡ 4 (mod 7)
a ≡ 3 (mod 7) ⇒ a² ≡ 2 (mod 7)
Then since a ≡ 4, 5, 6, 7 (mod 7) are equivalent to a ≡ -3, -2, -1, 0 (mod 7), so after squaring they will become the same as the negative becomes positive.
So a² ≡ 0 , 1 , 4 , 2 (mod 7)
If a² ≡ 2 (mod 7) then a ≡ 3 (mod 7) or a ≡ 4 (mod 7)
So we must have x+1 ≡ 3 or 4 (mod 7)
Thus x ≡ 2 or 3 (mod 7)
How do you type that equivalent sign?
@@aaronslittleworld9326 I got a special keyboard that has it stored it as a character. I think you can also copy it elsewhere too.
Yeah that’s what I did
I like the smiley face at the end
x^2 + 2x - 8 ≡ 0 (mod 7) works too
Yes, that's how I did it!
What where I'd eight come from..this ames no senseand neither does what he did this thr video..where did 5x come from he didn't add and subtract 7x so he can't do that
@@leif1075 Syber assumes a basic understanding of modulo arithmetic for his videos on modulo arithmetic. If you don't know what's happening, pop over to google and make sure you get the basic concepts. If you don't understand the concepts in the video, then you won't understand what the comments are talking about, and getting up the commenters because you don't understand what is happening is ludicrous. If you have tried to understand the video, and are struggling, then sure, ask in the comments what is going on, but if you don't understand the video, don't tell the commenters who are using similar logic that they are wrong because you don't understand what is going on.
Of course, it will works with -1,-8,-15,-22,-29 etc..... because all have a difference of 7 when you add always -7 of mod 7.😂
Generic approach.
x^2 + 2x + 7n = 1
x^2 + 2x + 7n-1 = 0
We want x to be an integer, so the determinant needs to be a perfect square
(2)^2 - 4(1)(7n-1) = m^2
4 - 4(7n-1) = m^2
4(2 - 7n) = m^2
Note that m will have to be even, since the LHS is even. So, let m = 2k.
4(2-7n) = (2k)^2
2 - 7n = 2k
2 - 2k = 7n
2(1-k) = 7n
We can make this work by letting k = 8. Then n = -2. Going backto the original equation, (7n-1) is now -15, so...
x^2 + 2x - 15 = 0
x^2 + 2x + 1 = 16
x + 1 = +/- 4
x = -1 +/- 4
x = -5 or 3
In the mod 7 world, this is 2 or 3.
What made you think to put 7n since x squared plus 2x is also a multiple kf 7? Arebt you forgetting to out a mod 7 after the 1 in the first equation?
@@leif1075 I didn't put the mod 7 because I put the 7n instead. a = b (mod k) means there exists some integer n such that a + kn = b.
This effectively converted it to a diophantine equation where x had to be from [0 .. 6] and n could be any integer (positive or negative). I can then use standard techniques for diophantine equations and get my answer that way.
@@chaosredefined3834 oh but you'd have to excited state that the 7n means thst right otherwise ppl wouldn't knkw and think it's just a standard quadratic equation with a7n term right?.they might not necessarily interpret it in terms of mods. Thanks for answering.
@@leif1075 Not really. It would be like if the equation was ln x = 2, and I wrote it as e^2 = x, because that is what the definition of ln is. In the same way, the definition of `a = b mod k` is that there exists some integer n such that `a = b + kn`. People who are familiar with modulo arithmetic won't need that explicitly stated.
@@chaosredefined3834 but that's my point ..if yiu don't explicitly state it, the equation is ambiguous..see what I mean? Because it looks like a standard quadratic equation.
Quadratic equation will solve it😉
How can you know there are not 4 solutions?
Because Z/7Z is a field. By the fundamental theorem of algebra, a degree n polynomial can have at most n roots in any field.
We can used the table and the exercice become not difficulte
Sure. What do you do when the problem asks for x^2 + 2x = 1 (mod 1009) though?
you can actually just use the quadratic formula
Look, I’m impressed you get it. But I’m just not gonna lol
I don't think it is a universal method, it seems like a coincidence that there are exactly two solutions and then they should correspond to the roots.
The squaring possibility given by the presence of the quadratic equation only guarantees an even number of solutions, so they should come in pairs.
Or how do you show that function x^2 (mod p) where p is prime number covers numbers between 0 and (p-1) zero times or two times and not more times?
Shouldn’t n power equations have exactly n solutions? I’m not familiar with mod and triple equal sign, so this a genuine question.
There are an infinite number of solutions all given by x ≡ 2 or 3 (mod 7). So x = 9 or 10 also work, as do x = 16 or 17, etc.
However, there are only two _sets_ of solutions (sometimes called "equivalence classes"), and any quadratic congruence equation can have no more than two classes of solutions. Modular arithmetic has many similarities with the usual algebra we are all familiar with and arithmetic modulo 7 has the same property that polynomials of degree n have no more than n roots (i.e. n sets of solutions)
In general there are some techniques for solving many congruences of the form x^2 ≡ a (mod p). Some have no solution.
To solve anything of the form y^2 + ny ≡ m (mod p), we substitute y = (x - n/2) giving x^2 - nx + (n/2)^2 + nx - n^2/2 ≡ a (mod p).
That simplifies to x^2 ≡ ( m - (n^2)/4 )(mod p). If n is odd we just use n+p for n as p is normally an odd prime.
The following results are known for solving x^2 ≡ a (mod p):
If p ≡ 3 or 7 (mod 8), then any solutions must be of the form x ≡ ± a^((p+1)/4) (mod p) if a solution exists.
If p ≡ 5 (mod 8), then any solutions must be of the form either x ≡ ± a^((p+3)/8) (mod p) or x ≡ ± a^((p+3)/8).2^((p-1)/4) (mod p) if a solution exists.
If p ≡ 1 (mod 8), then we have no "easy" solutions.
@@ScrewY0UguyS Maybe you have an answer already, but if you don’t here is a quick explanation.
The triple equals stands for “congruent to”.
One way to explain it is that it is the remainder when you divide by the “modulus”, the number after the word mod.
So 8 is congruent to 1(mod 7) because when you divide 8 by 7 the remainder is 1. 15 is also congruent to 1 mod 7, since 15 divided by 7 is 2 with a remainder of 1. So that is why the equation in the video has more than two solutions. There are infinitely many integers that are congruent to 1 mod 7, like 1,8,15,22,29 etc.
You use this modular arithmetic all the time using time. If it is 10AM, what time is it in 5 hours. You are actually asking what is 10+5 mod 12. Add to get 15, divide by 12 the remainder is 3, or 3pm.
Ok that 7-1= *6* , but why 7-2= *-5* ?? I don't understand it well.
that's 2 - 7
@@SyberMath i know that 2-7= -5. But then why in the first you don't subtract 1-7= -6??? You used 2 method opposed
what is this "modular" thing 😵💫
en.m.wikipedia.org/wiki/Modular_arithmetic
pt.m.wikipedia.org/wiki/Aritm%C3%A9tica_modular
@@MichaelRothwell1 thanks