Solving linear congruences -- Number Theory 10

Suggest a problem: forms.gle/ea7P...
Please Subscribe: www.youtube.co...
Patreon: / michaelpennmath
Merch: teespring.com/...
Personal Website: www.michael-pen...
Randolph College Math: www.randolphcol...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu...
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/s...
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ

[@goodplacetostop2973]

17:48 Homework 18:04 Good Place To Stop

[@PunmasterSTP]

Solving linear congruences? More like “Super learning video this is!” Even though I have to go back through things to try to understand them, I really appreciate everything Michael has done for the community on KZbin.

[@danielfarias1154]

this video section helps a lot to understand Number Theory books!!!! Michael helps us a lot with this kind of material

[@PunmasterSTP]

@@danielfarias1154 I never took a formal class in number theory, but I definitely enjoy learning about it as a hobby. There’s tons of great information on YT if one knows where to look…

[@danielfarias1154]

@@PunmasterSTP yes!! , me too hahah, is funny to learn Number Theory, is a good hobby where you can learn a lot

[@iceandteas]

holy crap thank you so much im literally like 2 days away from my exam and linear congruences were really really reaaaallly hard for me to visualise but ur video is helping me make a load of sense !!!

[@criskity]

I like to call the congruence sign (triple equals sign) "threequals". So, "a threequals b mod n".

[@samuelmarger9031]

Not gonna lie, that's a pretty cute name.

[@2070user]

@@samuelmarger9031 Cute and cool but not professional lol

[@anonymous_4276]

How about calling the equals sign "two thirds congruence"?

[@anshumanagrawal346]

@@anonymous_4276 lol

[@anshumanagrawal346]

Whole like one and a half equal signs

[@chilling00000]

9:11, I don't understand why gcd(n/d, n)=1, but it seems that we didn't use it later...

[@ethannguyen2754]

It isn’t; he made a mistake a = 5 n = 25 d = gcd(a, n) = gcd(5, 25) = 5 n/d = 5 gcd(n/d, n) = gcd(5, 25) = 5 ≠ 1

[@paulkohl9267]

Love all your videos! Keep on going, unless it is a good place to stop.

[@schrodingerbracat2927]

In the reduced equation 13x + 21y = 4, the algo takes some time to stop, because 13 and 21 are Fibonacci numbers. Fibonacci numbers makes Euclidean types of algorithm take the longest time. . btw, my algo is a modified Euclidean algorithm where you start with 1,0 and 0,1 and run forward only. No back-substitution is necessary in this version of the Euclidean algorithm.

[@ansonpang8468]

Video request: Find the general form of the indefinite integral \int dx/[a+b(cot(x))] and substitute in (a,b)=(0,1) to simplify the expression down to the well known integral of tan(x).

[@Mehraj_IITKGP]

Thanks a ton! Feeling bad for your left hand. Wish you a quick recovery.

[@madihachaklader2378]

10:46 idk how gcd of (12,20) is 4. Can someone explain please… even if I do like 20= 12*2 - 4… so should I just think 4 as positive?

[@Happy_Abe]

What about showing there aren’t any other solutions besides these d solutions

[@anshumanagrawal346]

I was also thinking the same thing

[@iabervon]

There are (n/d-1) other values for b that each have d solutions, so, of the n incongruent options for x, (n-d) of them are congruent to a value incongruent to b and aren't solutions.

[@BOO_BOP_]

2:50 in what video did you prove it?

[@lordstevenson9619]

Love this series

[@eamon_concannon]

6:45 I'm not sure that you have shown that all the solutions to ax=b modn must have the form x_0 + l(n/d) for any integer l and a particular solution x_0. Let x be any solution, then x = x_0 + r for some integer r and particular solution x_0. Plugging in we get ax-b= ax_0+ar - b. Since n|ax_0 - b, we must have n|ar which means n/d | (a/d)r. Since gcd(n/d, a/d) = 1 we have n/d | r so x = x_0 + l(n/d) for some integer l. Furthermore, we can create more solutions by adding multiples of n onto x, so x_0 + l(n/d) + kn is easily shown to be a solution as x_0 + l(n/d) + kn = x_0 + (l+kd)(n/d). We can also show that this solution is congruent to x_0 + m(n/d) for some m between 0 and d-1 by using division algorithm on l to get x_0 + (qd+m+kd)(n/d) = x_0 + m(n/d) + (q+k)n = x_0 + m(n/d) (modn)

[@schrodingerbracat2927]

Given 143x = 44 (mod 231) ---------- [0] this is equivalent to 143x + 231y = 44 ---------- [1] where we look for your x (ex) but don't care so much about y (why) dividing through by 11 = gcd(143, 231) gives 13x + 21y = 4 ---------- [2] We can solve this (see my Python program output below). Note the slight differences: for [0], solutions are unique up to modulo 231. for [1], solutions are unique up to modulo lcm(143,231)=3003, whereas for [2], solutions are unique up to modulo lcm(13,21)=273 Solving 143x + 231y = 44 143 231 | 44 -------------------- 1 0 | 143 0 1 | 231 -------------------- 1 0 | 143 , q=0 -1 1 | 88 , q=1 2 -1 | 55 , q=1 -3 2 | 33 , q=1 5 -3 | 22 , q=1 10 -6 | 44 Particular solution: x=10, y=-6 General solution x=10 -21*t y=-6 + 13*t Solutions are unique up to modulo lcm(143,231)=3003 Solving 13x + 21y = 4 13 21 | 4 -------------------- 1 0 | 13 0 1 | 21 -------------------- 1 0 | 13 , q=0 -1 1 | 8 , q=1 2 -1 | 5 , q=1 -3 2 | 3 , q=1 5 -3 | 2 , q=1 10 -6 | 4 Particular solution: x=10, y=-6 General solution x=10 -21*t y=-6 + 13*t Solutions are unique up to modulo lcm(13,21)=273

[@liliepepe65]

Fantastic video. How do you work your videos with your students?

[@lvl5popcap]

I'm getting 10+21m for the second example, like a couple of other comments have pointed out too, instead of 199+21m

[@infopek3221]

The homework made me realize that the gcd(F_n, F_(n+1)) = 1, where F_n is the n-th Fibonacci number.

[@abdallahal-dalleh6453]

In the first example 12x = 8 (mod 20), 24, 29, 34, etc. are all solutions. In other words, doesn't continuously adding 5 gives us a solution? Why the limitation for the # solutions to be

[@thomasdemilio6164]

It's because having just one more solution would mean that one of the solutions that we already have is congruent to the new one IN THE MODULO WE'RE IN. For example, for 12x=8(mod20) we have gcd(20,12)=4 distinct solutions IN MODULO 20. In fact, 4 is congruent to 24 mod 20, 9 is congruent to 29 or -11 mod 20... so you can really choose your soultions, as long as they're distinct in that modulo, and your set of solutions could be {4, 9, 14, 19}, but also {24, -11, 54, -1}

[@thomasdemilio6164]

Typically they tell you which solutions to take, for example in competitions you could get "the number wanted is the sum of the first 5 positive solutions" or "the first 10 negative incongruent solutions (among a set of 12 for ex)"

[@trueriver1950]

Number theory 10 comes out half a day after 13. I wonder if Michael knows that the natural nos are sometimes called counting numbers? ;)

[@sarvesh_soni]

All videos till 20th had came, they are unlisted, you can find them on playlist

[@skwbusaidi]

143x = 44 (mod 231) Devide by the gcd(143,231)= 11 13x = 4 ( mod 21) Check a mutiple of 21 that you can add to 4 to make the total multiple of 13 ( it is 126) 13x = 130 (mod 21) x = 10 (mod 21) x = 10 + 21k

[@2070user]

False. You should check your answer by substituting the solution back into the original congruence. Take x=10+21(0), k=0 143(10) is not congruent to 44 mod 231 Take x=10+21(1), k=1 143(31) is also not congruent to 44 mod 231 But that was a good try nonetheless

[@skwbusaidi]

Letting k=6 give you 199 which Mr Penn get first.

[@Karatemaci]

143*10=6*231+44 is true so skw is right. The other 10 solutions are also correct mod 231.

[@particleonazock2246]

thanks from the zhushikou flyover in beijing

[@johnriverz]

I thought it was n divides a-b?

[@liliepepe65]

Ps .Iam professor my name is Marcos. Lili and pepe are my sons...lol

[@nickw-dt7jz]

Can you post some videos for 2-D plane geometry problem?

[@anshumanagrawal346]

He does have some videos from 2-D Co-ordinate Geometry on his channel

[@marc-andredesrosiers523]

Great video. Like the proofs. Would have been nice to provide intuition with an integer lattice torus with the drawn lines. Especially, if it is to become a stand-alone video. Keep it up.

[@L0wLevel01]

Cheers

[@qdrtytre]

Do the examples before the proof.

[@nhatminhcnhhn]

Nice

[@cameronspalding9792]

The theorem at the start of the video could be proven using powers of complex numbers

[@trueriver1950]

Yes and no. If following the order that number theory builds up from its axioms, at this stage we don't have complex numbers so it would introduce a circular dependency to use that "proof", which therefore becomes more of a consistency check between different parts of number theory

[@schweinmachtbree1013]

@@trueriver1950 You don't need any number theory to define the complex numbers so there is no circular reasoning. The complex numbers can be defined simply as pairs (a, b) (written a+bi) which add componentwise as (a, b)+(c, d) := (a+c, b+d) and multiply as (a, b)(c, d) = (ac-bd, ad+bc), from which one can easily verify the field axioms, although it is a bit tedious. more abstractly the complex numbers can be defined as the quotient ring R[x]/ which is automatically a field because is a maximal ideal of R[x] (because x^2+1 has no roots in R so is a nonzero prime ideal, and every non-zero prime ideal in R[x] is maximal as R[x] is a principal ideal domain since R is a field)