Solving congruences, 3 introductory examples
ฝัง
- เผยแพร่เมื่อ 8 ก.พ. 2025
- 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
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！！！
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)
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!
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]
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?
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.
4x ≡ 3 mod 5. There exists a solution because gcd(4, 5) = 1 which divides 3.
Observe that ([4]₅)⁻¹ = [4]₅ since [4]₅[4]₅ = [4•4]₅ = [16]₅ = [1]₅. So we have
4x ≡ 3 mod 5
⇔ x ≡ 12 mod 5
⇔ x ≡ 2 mod 5
For the third one, just add 5 to the right side and it becomes the same as the first equation.
these helped out a ton, thank you so much
3:38 When you finish the number theory
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 ).
this was so helpful! thanks!
The one I even want u to do u did not do it self🤨
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
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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
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!
So that's where the black pen red pen yay coming from
Rex Evan yes!!!!
Did u read what I wrote?
2:53 Why do we want the answer to be as positive as possible?
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.
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 : )
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.
I'm very grateful to u.
Thanks and nice timing that i need this one.
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.
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......
NEEDED THIS!!
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!!!!!
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.
What is the purpose of doing this in the real world Applications?
This is just what I needed. Thank you!
7x^3+2x^2+x congruent to 0[2]
Plz
Thanks for making this video, It really helps me🙏😭
Bro you helped me thank you
Thank you for all the high quality videos bprp, they are much appreciated 💜
Multiply by 4^{-1} mod 5 = 4
tysm this video helped a lot :)
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
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 🤘🤘🤘
Très intéressant !
Merci beaucoup.
4X cong 3 mod 5, 5+3=8, 8/4=2. X=2.
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
Awesome quick solver
Great job!!!
Lord god and savior! I have found you! My professor and the book made everything so much complicated!
Frank Maayn : )
At 2:49 you went against my prediction. You should have multiplied both sides by -1.
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.
3) x = 2(mod 5)
Thank you very much for these!
4 x k 2(mod3) find the value of integer x
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!!
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.
Blackpen-Redpen!!!!!! yay!!!!!!
Yesss
why does the gcd = 1 thing work for dividing?
I love these videos!!!
Can one solve:5x is congruent to 1 modulo 12 with the same method??
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!
Can you solve this equation step by step (2)^x +x =37
How Prove that for all n the following congruence holds: n^3≡n(mod 3)?
Is the last one x congruent to 2 mod 5
-x=-2(mod 5)
x=2(mod 5)
No se nada de inglés pero me ayudo mucho jajajaj gracias!!!
4x=3 (mod 5)
4x=8 (mod 5)
x=2 (mod 5)
Am I right ?
How we solve 2x congrent(mod7)?? Please
Can you do the inegral of ln(ln(x))?
Yoav Shati
That is not elementary
Very good sir
2x congrent 7 (mod17)
Please l want you to solve some questions 4X =1
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
4mod5 =-1?? Remainder cannot be negative
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.
Obrigado!!!
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
Goodexplaining
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
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?
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.
Is 8 mod 5 even legit?
I don't think it is
x=2(mod5)
Excelent!!! what the result of a^((p-1)/k) mod p where a^(1/k) not integer.
Thanks in advance.
What's mod tho. New concept for me
Alpha Designs you can watch my previous video. :)
blackpenredpen Thank you
I love you.
Hello sir
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
Puedes ayudarme con este ejercicio x^5 - 3x^4 + x - 2=0( mod 165)
Yayyyy
mfkr i opened the video for the third example
Please enlighten me please. 😭
Bhai ap apna bolny ka styl thk kryn xara b ni smj ati apki
...actions e ni khtm hoty ap k tou
Yay!!!!!
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.
lee le kmkl
That's was damn easy to learn, thanks bruh! 🫂❤️
x=2(mod 5)