Solving congruences, 3 introductory examples
HTML-код
- Опубликовано: 21 дек 2024
- Learn how to solve basic linear congruences for your number theory class. We will solve
1. 4x is congruent to 8 (mod 5)
2. 4x is congruent to 2 (mod 5)
3. 4x is congruent to 3 (mod 5)
💪 Support this channel and get my math notes by becoming a patron: / blackpenredpen
note, for this comment = will replace the congruence symbol
4x = 3 (mod 5)
4x = 8 (mod 5)
x = 2 (mod 5)
Yup!
Piyush Sarangi Yes, but there's no reason to.
Why do we add mod 5 to 3? Please send the respective theorem.
@@ritwiksharma7021 it's because 3 (mod 5) is the same as 8 (mod 5)
-x = 3 (mod 5)
x = -3 (mod 5)
x = 2 (mod 5)
You can solve the third one either way,
1)
4x = 3 (mod 5)
-1x = 3 (mod 5)
x = -3 (mod 5)
x = 2 (mod 5)
2)
4x = 3 (mod 5)
4x = 3 + 5 (mod 5)
4x / 4 = 8 / 4 (mod 5) (gcd(4, 5) = 1)
x = 2 (mod 5)
It's interesting how you can simplify either side by multiples of 5 to get the answer, really enforces the idea that it is "mod 5".
BLACK PEN RED PEN
*_YAYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY_*
Oon Han yay！！！
I wish it had the final solution to self-check understanding, because if it was "so easy," I wouldn't have googled help. Cute vid, good explanation, just please finish the examples!
First!!!!!
eigth ...
Blackpenredpen 57th
(2^2=2(2)=2+2=4)th reply
551st (mod2)
Is the answer to the third question:
x is congruent to 2 (mod 5)?
Steps:
4x ≡ 3 (mod 5)
-1x ≡ 3 (mod 5) like step 2.
x ≡ -3 (mod 5)
x ≡ 2 (mod 5)
One doubt: Y didn't you use the same method of making it -1x in example 1?
Not certain if this is a weird method for the second one but...
4x≡2(mod 5)
2x≡1(mod 5) [divide by two, since gcd(2,5)=1 and 2/2 gives an integer answer]
2x≡6(mod 5) [increasing 1 by one modular 5 cycle to 6]
x≡3(mod 5) [divide by two, since again gcd (2,5)=1 and 6/2 gives an integer answer]
3:38 When you finish the number theory
4x=3 mod 5
(5x-x)=3 mod 5
-x=3 mod 5
x=-3 mod 5
x=2 mod 5
Thank you so much Black Pen Red Pen.
For the third one, just add 5 to the right side and it becomes the same as the first equation.
So that's where the black pen red pen yay coming from
Rex Evan yes!!!!
Did u read what I wrote?
these helped out a ton, thank you so much
wow finally in understand the mod function thank u so much !!!
I really love your mic! still!!! And that intro was soooooooooo cute!!
Thank you!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
this was so helpful! thanks!
can u tell how can I solve similar questions where equation is x^2 = a (mod p), here value of x and a is known , how can i find p
2 videos on modular arithmetic back after back! :D thanks again. I really like the videos a lot thnx. Mainly cuz I actually like modular arithmetic haha thnx again!!!!!!!
Yay!!!!!
For the second one you could also do:
4x = 2mod5
4x = 12mod5 (+10)
x = 3mod5 (/4)
76
Danicker, I think you didn't divide by three but by four, ao because I used this method myself, too.
@@Apollorion Yes, you're right!
I'm very grateful to u.
Thanks and nice timing that i need this one.
The answer to the last one is 2(mod5) right?
Yes, that is correct. Basically, apply the same method as no. 2 to get x = -3 (mod 5), i.e. x = 2 (mod 5)
Yeah!!
why does the gcd = 1 thing work for dividing?
The one I even want u to do u did not do it self🤨
2:53 Why do we want the answer to be as positive as possible?
Trick: 4 = -1 (mod 5)
4x = 8 (mod 5) -x = 8 (mod 5)
4x = 2 (mod 5) -x = 2 (mod 5)
4x = 3 (mod 5) -x = 3 (mod 5)
Of course all of them are trivial
-x = 8 (mod 5) x = 5k-3 for any integer k (8 = 3 mod 5)
-x = 2 (mod 5) x = 5k-2 for any integer k
-x = 3 (mod 5) x = 5k-3 for any integer k
Thank you for all the high quality videos bprp, they are much appreciated 💜
Multiply by 4^{-1} mod 5 = 4
Assume the equal signs are congruences, due to keyboard limitations.
Given 4x=2 (mod 5),
Can you just do:
4x=2=12 (mod 5)
=> 12/4=3, hence
{xEZ: x=3 (mod 5/1)} is set of all solutions.
Thanks for making this video, It really helps me🙏😭
7x^3+2x^2+x congruent to 0[2]
Plz
This is just what I needed. Thank you!
alternative method would be multiplying by the inverse of 4 aka 4. Granted this is harder in the general case because computing the inverse usually takes more time.
yup!
With the Euclidian algorithm it usually only takes 2 or 3 rounds on smaller numbers, can be done in seconds on a calculator.
How Prove that for all n the following congruence holds: n^3≡n(mod 3)?
Bro you helped me thank you
No need to combine. Just add 5 to right side and you get the 1st
Yup, that's exactly the way I had in mind : )
Is the last one x congruent to 2 mod 5
I have not perused all the answers, but we can clearly multiply both sides by 4.
Left side, 4*4X = 16 X = 1 X (mod 5) --- since (A*B) | C == ( (A|C) * (B|C) ) | C
Right side : 4* 3 = 12 = 2 (mod 5)
So X = 2 (mod 5).
In fact, in AX=B (mod C), when pgcd(A, C) =1, then A has an inverse, Q, such that Q*A=A*Q = 1 ( mod C).
Note that 1 and (C-1) are their own inverse mod C, that is, (C-1)^2 = 1 mod C (since C^2 -2C + 1 = 1 mod C )
Otherwise, A has a zero-producing-multiplier such that A*P = P*A = 0 (mod C) while neither A, neither P being 0 (such as 2*3 = 0 (mod 6) )
An integer A can either have an inverse, either a zero-multiplier, but not both, for given modulo.
So, C as prime number will have all its classes having an inverse (except its class 0) since C being prime cannot have A*B = C, with A and B integers between 1 and C-1, so modulo C cannot produce any zero-multiplier among its classes.
If the pgcd(A, C) > 1, we may have multiple solutions ( 3X = 6 mod 9 has X=2, 5 and 8 as solutions), or none ( 3X = 5 mod 9 has no solution). The second member, B in AX=B mod C, must be divisible by D = pgcd(A, C) to have at least a solution, and owns D distinct solutions (among its classes) each of them "distant" for C\D
(back to 3X = 6 mod 9, we have D=3, and the D solutions are distant of C\D = 3, as are 2+3 = 5, 5+3=8 and 8+3 = 2 mod 9 ).
4x=3(mod 5)
-1x=3(mod 5)
-1×-1x=-1×3(mod 5)
x=-3(mod 5)
x=2(mod 5)
Yaa i got it ...Yahoo 🤘🤘🤘
How we solve 2x congrent(mod7)?? Please
4 x k 2(mod3) find the value of integer x
Lord god and savior! I have found you! My professor and the book made everything so much complicated!
Frank Maayn : )
Awesome quick solver
Great job!!!
Can one solve:5x is congruent to 1 modulo 12 with the same method??
At 2:49 you went against my prediction. You should have multiplied both sides by -1.
Blackpen-Redpen!!!!!! yay!!!!!!
Yesss
It's interesting how fast you solve these equations!
I'm in highschool in France, and to solve for example 4x ≡ 3 [5] we do so:
4x ≡ 3 [5] ⇔ ∃y ∈ ℤ, 4x − 5y = 3
Considering the equation 4x − 5y = 3, where (x ; y) ∈ ℤ², we will first find a particular solution. In this case, we can just take x = − 3 and y = − 3, which leads us to 4x − 5y = 4 × (− 3) − 5 × (− 3) = − 12 + 15 = 3.
Next, we can say that if (x ; y) is solution, then we have 4x − 5y = 3 = 4 × (− 3) − 5 × (− 3), so
4x − 5y − (4 × (− 3) − 5 × (− 3)) = 4x − 5y + 4 × 3 − 5 × 3, and finally 4(x + 3) = 5(y + 3).
At this point, we use the Gauss' theorem that tells us that because GCD(4 ; 5) = 1, (x + 3) can be divided by 5 and (y + 3) can be divided by 4. So we get x + 3 = 5k and y + 3 = 5k', where (k ; k') ∈ ℤ², which means that x ≡ − 3 [5], which can be written as x ≡ 2 [5].
Bonjour,
Très vite resolu, en effet ! Ça fait une sacrée différence.
J'ai été encore plus surpris quand il a divisé par 4 dans 4x=8 [5] : c'est tabou en France d'utiliser la division dans les congruences.
Je me suis penché sur sa démonstration, je n'y ai jamais pensé auparavant.
En fait, c'est très simple ;
ax=b[n] il exst k dans Z tq:
ax=b+n×k ce qu'on sait en France mais on n'allait pas plus loin:
Ici, 4x=8[4] eqvt à 4(x-2)=5×k eqvt à 4 divise k car pgcd(4,5)=1 (Bezout):
k=4×k' , k' dans Z. k existe bel et bien d'où l'équivalence.
Bonne journée.
Thank you very much for these!
How can you solve 720n ≡ -1 (mod 2027) ?
I can only make use of Chinese remainder theorem and solving Diophantine equation. I look forward to learn other methods from you. You are a great teacher. Thanks for your sharing.
Bonjour
je pense que votre question concerne la résolution de l'équation 720n_=-1[2027]. Si c'est cela alors voila cette solution obtenue au moyen du schéma d'Ouragh
2027....720.......587......133......55.......23......9.......5.....4.......1
...............-2.........-1.........-4.........-2........-2.....-2.......-1...-1
.............442.....-157......128......-29.......12....-5........2...-1.......1
et donc on aura n_=442*(-1)[2027] soit n_=2026[2027]
Cordialement.
Can you solve this equation step by step (2)^x +x =37
3) x = 2(mod 5)
i love this intro!!!
sidenote! have you seen the simpson's 'fake fermat' equations?
[3987]^12 + [4365]^12 = [4472]^12
[1782]^12 + [1841]^12 = [1922]^12
are these statements true? illustrate why or why not using only pencil, paper, and/or calculator.
but not a computer or computer algebra program!
Early Kyler The second one is pretty easy, you easily see that if it were true, that would imply that an odd number plus an even number equals an even number, and that's not true, you can do the same with the second but in mod 4 I think
Bruno Andrades mod 3! But yes lol
Early Kyler Oh, ty, I didn't actually try it, but it seemed like
Thanks!!! And yes I have seen them and will do a video on them too.
Early Kyler BlackPenRedPen can't do it using only pencil, paper and calculator....
He needs the power of Blue marker......
4X cong 3 mod 5, 5+3=8, 8/4=2. X=2.
tysm this video helped a lot :)
NEEDED THIS!!
Très intéressant !
Merci beaucoup.
Alternatively:
4x = 2 mod 5
2 is not divisible by 4, try adding 5.
4x = 7 mod 5
7 is also not divisible by 4, try adding 5 a second time.
4x = 12 mod 5
12 is divisible by 4, and gcd(4,5) = 1, so we can divide by 4.
x = 3 mod 5.
If you add 5 five times, and it's never divisible by 4, then there is no answer.
4x=3(mod5)
-x=3 (mod5)
x=-3 (mod5)
x=2 (mod 5)
----- final answer
is the process correct?
It is one of the correct processes. I myself added 0 mod 5 = 5 mod 5 to the equation and got a copy of question (1) en retour. Same question? -> Same results.
No se nada de inglés pero me ayudo mucho jajajaj gracias!!!
Can you do the inegral of ln(ln(x))?
Yoav Shati
That is not elementary
Very good sir
What is the answer of 4x=3 mod 7
It is (sort of) known.
> 4-7=-3 => 4x=-3x mod 7 => (4x=3 mod 7 -3x=3 mod 7)
> 7-1=6 => -1=6 mod 7
And so:
4x=3 mod 7 -3x=3 mod 7 x=-1 mod 7 x=6 mod 7 => x=6+7k with k being any integer
Sir, Can I ask you something?
Ved Prakash yes?
Sir, What is your wife's name?😂😂😂
You already know!
Really Sir, I don't know.
What is the purpose of doing this in the real world Applications?
2x congrent 7 (mod17)
4x congruent to 3 (mod 5)
4x congruent to -2 (mod 5)
-x congruent to -2 (mod 5)
x congruent to 2 (mod 5)
yay!
Is this correct
Note :- please replace = sign with congruent sign.
4x=3(mod5)
X=-3(mod5)
X=2(mod5) thats it!!!
Please check my answer.
Yes.
blackpenredpen thanks
Hey plz help with this
17x = 1 mod 5
17x mod 5 = 15x+2x mod 5 = 2x mod 5
1 mod 5 = 1 + 0 mod 5 = 1 + 5 mod 5 = 6 mod 5
And so:
17x = 1 mod 5 = 2x = 6 mod 5 => x = 3 mod 5
That was very difficult, right?
-x=-2(mod 5)
x=2(mod 5)
I love these videos!!!
Excelent!!! what the result of a^((p-1)/k) mod p where a^(1/k) not integer.
Thanks in advance.
Please l want you to solve some questions 4X =1
x=2(mod5)
You can show proof if the sum of each number of a big number is divided by 3, then this number is divided by 3.
Goodexplaining
Sir,if a^5 b+3 is congruent to o,1,or -1 mod 9 then a^5 b is congruence to 5,6,or 7mod 9.why????????sir, i request u to explain it asap becoz i am in trouble.
Let's start with, for ease of expression: a^5 b = y then the question becomes:
y+3=x mod 9 with x equal to 0, 1 or --1 then why is y = 5, 6 or 7 mod 9 ?
All you have to do is subtract 3 from LHS and RHS, and add 9 to the RHS to get it positive. You can do so because 9 mod 9 = 0 mod 9
4mod5 =-1?? Remainder cannot be negative
4x=3 (mod 5)
4x=8 (mod 5)
x=2 (mod 5)
Am I right ?
2.
Notice that 4x=2 (mod 5)=12 (mod 5)
So we have 4x=12 (mod 5). Dividing both sides by 4, we have x=3 (mod 5)
3.
Notice that 4x=3 (mod 5)=8 (mod 5)
So we have 4x=8 (mod 5). Dividing both sides by 4, we have x=2 (mod 5)
Remark:
Note that the 'mod 5' will stay no matter what. This means that we can try values, and guess and check.
Best,
The Math Aces
Is 8 mod 5 even legit?
I don't think it is
What's mod tho. New concept for me
Alpha Designs you can watch my previous video. :)
blackpenredpen Thank you
mfkr i opened the video for the third example
I love you.
Puedes ayudarme con este ejercicio x^5 - 3x^4 + x - 2=0( mod 165)
Hello sir
Obrigado!!!
Please enlighten me please. 😭
On n'a pas le droit de diviser des congruences aussi facilement que ça. Il suffit de faire un tableau de congruences et on trouve facilement les solutions
Hey! could someone please help me with this problem on geometry of complex numbers?
Find the centre, radius and arc length of the arc of the circle formed by the set of all complex numbers satisfying arg [(z-5+4i) ÷ (z+3-2i)] = -π/4.
Yayyyy
Yay!!!!!
Bhai ap apna bolny ka styl thk kryn xara b ni smj ati apki
...actions e ni khtm hoty ap k tou
lee le kmkl
That's was damn easy to learn, thanks bruh! 🫂❤️
x=2(mod 5)