The Euclidean algorithm is often taken for granted, but it is extremely powerful. An algebraic structure (ring) that possesses the Euclidean algorithm enjoys a lot of nice properties.
Euclidean algorithm works because of the well ordering of natural numbers which is then derived from induction.I think if a ring structure that derived from objects that don't have well ordering the euclidean algorithm does not even stop.
@@jimallysonnevado3973 There is an algebraic structure called Euclidean ring. It is a ring where a more general form of the Euclidean algorithm holds. It is probably the best ring structure you can have if the ring isn't already a field, because as OP pointed out, a LOT of nice properties can be derived from this alone, like the existence of a gcd.
@@jimallysonnevado3973 Well ordering is not required for the Euclidean algorithm to work. There are deeper underlying structural reasons. As the reply above says, there are many rings with the Euclidean algorithm.
It's cool that the list of quotients you get from the algorithm 1,1,3,3,4 are the entries in the continued fraction for 693/392 in reduced form which is 99/56. 1+1/(1+(1/(3+1/(3+1/4))))=99/56.
Thank you so so so so much to provide this invaluable education on youtube I am 15 year old and wanted to study number theory from last 2 years, i was unable to understand it from books and did not find a formal course on youtube explaining it before yesterday when i found yours, Your videos are very very helpful, i rewrite what you teach to understand more deeply, I am side by side studying from Number theory book by David M Burton, just because of your videos i am able to understand from that book Again Thank you very much sir for this help
5:54 that is true only if both d and d' have the same sign. (Which in this case they have since you defined a common divisor to be a natural number (and not an integer)) 6|(-6) and (-6)|6 and clearly they are not the same number. It is a point that needs to be clarified otherwise mistakes will be made
The way I solve ax+by=gcd(a,b): 1) Do the forward Euclidean algorithm. Use it to write a/b as a continued fraction. Ex: 693/392 = 1+1/(1+1/(3+1/(3+1/4))). (These numbers are just the quotients qk that Michael came up with.) 2) Delete the last fraction. Ex: 1+1/(1+1/(3+1/3)): I just dropped the 1/4. 3) Collapse the fraction. Ex: 1+1/(1+1/(3+1/3)) = 1+1/(1+1/(10/3)) = 1+1/(1+3/10) = 1+1/(13/10) = 1+10/13 = 23/13 4) The new fraction is -(x/y), you decide whether the negative goes on the x or y. Ex: 13*693 = 9009, 23*392=9016. So 7=693*(-13)+392*23 as Michael got. This method is pretty much the same, but it just feels a little less messy to me. You use the same technique going down as you do going back up, continued fractions.
Just tried the last question. I started with a^n -1 = (a^m - 1)(a^(n-m)) + a^(n-m) -1 in a manner similar to completing squares, and continued with the Euclidean algorithm. At some point there would be a linear combination of m and n which gives 0 (lying in the remainder a^(km-ln) - 1 = 0), and it should be when they reach LCM(m, n). But I'm not sure how I could arrive at the conclusion, when I have a vague feeling that the combination should be in a form related to Fib sequence.
I believe if km - ln = 0, then the on Fib sequence they would be: ..., k-l, l, k, k+l, ... giving gcd(a^m -1, a^n -1) = a^((k-l)n - lm) - 1... while (k-l)n - lm is a linear combination of m and n, I could not show that this is the gcd of m and n.
let d = gcd(m,n) and d'= gcd((a^m) - 1,(a^n) -1). I have shown that ((a^d) - 1) divides d'. How do i show that d' divides ((a^d) - 1), to s.t. d'=((a^d) - 1)
d'= gcd((a^m) - 1,(a^n) -1) implies that d' divides (a^m) - 1 which implies x'd'= (a^m) - 1 for some x' ( an element of N U {0} ). Also (a^m) - 1 =(a^xd) - 1 for m = xd ( from d divides m). Therefore, (a^m) - 1 = (a^d)^x - 1 = ((a^d) - 1) ((a^d)^(x-1) + (a^d)^(x-2) + .......+ a^d + 1) => (a^m) - 1 = ((a^d) - 1) S , for S = ((a^d)^(x-1) + (a^d)^(x-2) + .......+ a^d + 1) Now d is a non-zero integer (Z+) and a is a Z+ implies S is a Z+, and ((a^d) - 1) is a Z+ U {0}. So x'd' = ((a^d) - 1) S ((a^d) - 1) = (x'/S) d' x' is a Z+ U {0} and S is a Z+ , and d' is a Z+ and ((a^d) - 1) is a Z+ U {0} implies (x'/S) is a Z+ U {0}. so we have ((a^d) - 1) as an integer multiple of d'. so d' divides ((a^d) - 1) . so we have both d' divides ((a^d) - 1) and ((a^d) - 1) divides d'. since d'>=1, this implies d' = ((a^d) - 1).
Here's my late solution to the last problem: To prove that gcd(a^m - 1, a^n - 1) = a^gcd(m, n) - 1: First, gcd(m, n) can be written as a linear combination of m and n, i.e., gcd(m, n) = xm + yn for some integers x and y. Let d = gcd(m, n). Therefore, a^d - 1 = a^(xm + yn) - 1. Notice that a^(xm + yn) - 1 divides both a^m - 1 and a^n - 1. This implies that gcd(a^m - 1, a^n - 1) must divide a^d - 1. Conversely, since m = dx and n = dy, we have a^m - 1 = a^(dx) - 1 and a^n - 1 = a^(dy) - 1. Thus, a^d - 1 divides both a^m - 1 and a^n - 1, so a^d - 1 divides gcd(a^m - 1, a^n - 1). Since we’ve shown that gcd(a^m - 1, a^n - 1) divides a^d - 1 and a^d - 1 divides gcd(a^m - 1, a^n - 1), we conclude that gcd(a^m - 1, a^n - 1) = a^d - 1.
Professor M. Penn, thank you for a solid proof and excellent examples of The Euclidean Algorithm in Number Theory Five. I fully understand this video/lecture from start to finish.
The Euclidean algorithm is often taken for granted, but it is extremely powerful. An algebraic structure (ring) that possesses the Euclidean algorithm enjoys a lot of nice properties.
Euclidean algorithm works because of the well ordering of natural numbers which is then derived from induction.I think if a ring structure that derived from objects that don't have well ordering the euclidean algorithm does not even stop.
@@jimallysonnevado3973 There is an algebraic structure called Euclidean ring. It is a ring where a more general form of the Euclidean algorithm holds. It is probably the best ring structure you can have if the ring isn't already a field, because as OP pointed out, a LOT of nice properties can be derived from this alone, like the existence of a gcd.
@@jimallysonnevado3973 Well ordering is not required for the Euclidean algorithm to work. There are deeper underlying structural reasons. As the reply above says, there are many rings with the Euclidean algorithm.
It's cool that the list of quotients you get from the algorithm 1,1,3,3,4 are the entries in the continued fraction for 693/392 in reduced form which is 99/56. 1+1/(1+(1/(3+1/(3+1/4))))=99/56.
Thank you so so so so much to provide this invaluable education on youtube
I am 15 year old and wanted to study number theory from last 2 years, i was unable to understand it from books and did not find a formal course on youtube explaining it before yesterday when i found yours,
Your videos are very very helpful, i rewrite what you teach to understand more deeply, I am side by side studying from Number theory book by David M Burton, just because of your videos i am able to understand from that book
Again Thank you very much sir for this help
5:54 that is true only if both d and d' have the same sign. (Which in this case they have since you defined a common divisor to be a natural number (and not an integer))
6|(-6) and (-6)|6 and clearly they are not the same number.
It is a point that needs to be clarified otherwise mistakes will be made
No gcd is defined as a positive number only
Yeah what I was concerned of, but then i saw the ds were gcds so positive for sure
Ahh this is so cool I literally just finished a problem set on Euclidean domains and came on yt to relax and saw this lol
Last problem:
Let gcd(m, n) = d
Let gcd(a^m-1, a^n-1) = d’
a^m - 1
= a^kd - 1
= (a^d - 1)(1 + a^d + a^2d + … + a^(k-1)d)
Thus, (a^d - 1) | a^m - 1
By a similar argument, (a^d - 1) | a^n - 1
Since (a^d - 1) is a common divisor of (a^m - 1) and (a^n - 1),
(a^d - 1) | d’
The way I solve ax+by=gcd(a,b):
1) Do the forward Euclidean algorithm. Use it to write a/b as a continued fraction.
Ex: 693/392 = 1+1/(1+1/(3+1/(3+1/4))). (These numbers are just the quotients qk that Michael came up with.)
2) Delete the last fraction.
Ex: 1+1/(1+1/(3+1/3)): I just dropped the 1/4.
3) Collapse the fraction.
Ex: 1+1/(1+1/(3+1/3)) = 1+1/(1+1/(10/3)) = 1+1/(1+3/10) = 1+1/(13/10) = 1+10/13 = 23/13
4) The new fraction is -(x/y), you decide whether the negative goes on the x or y.
Ex: 13*693 = 9009, 23*392=9016. So 7=693*(-13)+392*23 as Michael got.
This method is pretty much the same, but it just feels a little less messy to me. You use the same technique going down as you do going back up, continued fractions.
Wow! That's a nice method
I'm studying gcd in algebra, i just realized today you were uploading gcd videos recently. Nice.
4:35 a banan appears 🍌
Just tried the last question. I started with a^n -1 = (a^m - 1)(a^(n-m)) + a^(n-m) -1 in a manner similar to completing squares, and continued with the Euclidean algorithm. At some point there would be a linear combination of m and n which gives 0 (lying in the remainder a^(km-ln) - 1 = 0), and it should be when they reach LCM(m, n). But I'm not sure how I could arrive at the conclusion, when I have a vague feeling that the combination should be in a form related to Fib sequence.
I believe if km - ln = 0, then the on Fib sequence they would be: ..., k-l, l, k, k+l, ... giving gcd(a^m -1, a^n -1) = a^((k-l)n - lm) - 1... while (k-l)n - lm is a linear combination of m and n, I could not show that this is the gcd of m and n.
I agree with you, it does seem like its becoming some sort of fib type sequence for the exponents.
Can I get the answers of the warm up problems somewhere ..I am having trouble solving the last one...
Can you explore this in a video? It's related to Pythagoras and Euclid, regarding the difference between the legs of a primitive PRT: if m,n∈N, 0
let d = gcd(m,n) and d'= gcd((a^m) - 1,(a^n) -1). I have shown that ((a^d) - 1) divides d'. How do i show that d' divides ((a^d) - 1), to s.t. d'=((a^d) - 1)
d'= gcd((a^m) - 1,(a^n) -1) implies that d' divides (a^m) - 1 which implies x'd'= (a^m) - 1 for some x' ( an element of N U {0} ). Also (a^m) - 1 =(a^xd) - 1 for m = xd ( from d divides m).
Therefore, (a^m) - 1 = (a^d)^x - 1 = ((a^d) - 1) ((a^d)^(x-1) + (a^d)^(x-2) + .......+ a^d + 1)
=> (a^m) - 1 = ((a^d) - 1) S , for S = ((a^d)^(x-1) + (a^d)^(x-2) + .......+ a^d + 1)
Now d is a non-zero integer (Z+) and a is a Z+ implies S is a Z+, and ((a^d) - 1) is a Z+ U {0}.
So x'd' = ((a^d) - 1) S
((a^d) - 1) = (x'/S) d'
x' is a Z+ U {0} and S is a Z+ , and d' is a Z+ and ((a^d) - 1) is a Z+ U {0} implies (x'/S) is a Z+ U {0}. so we have ((a^d) - 1) as an integer multiple of d'. so d' divides ((a^d) - 1) .
so we have both d' divides ((a^d) - 1) and ((a^d) - 1) divides d'. since d'>=1, this implies d' = ((a^d) - 1).
You should do more video about number theory like this. It’s really helpful for student.
18:08 Good Place To Stop?
21:15 Homework
22:08 Good Place To Stop
Good Place To Stop
Here's my late solution to the last problem:
To prove that gcd(a^m - 1, a^n - 1) = a^gcd(m, n) - 1:
First, gcd(m, n) can be written as a linear combination of m and n, i.e., gcd(m, n) = xm + yn for some integers x and y. Let d = gcd(m, n). Therefore, a^d - 1 = a^(xm + yn) - 1.
Notice that a^(xm + yn) - 1 divides both a^m - 1 and a^n - 1. This implies that gcd(a^m - 1, a^n - 1) must divide a^d - 1.
Conversely, since m = dx and n = dy, we have a^m - 1 = a^(dx) - 1 and a^n - 1 = a^(dy) - 1. Thus, a^d - 1 divides both a^m - 1 and a^n - 1, so a^d - 1 divides gcd(a^m - 1, a^n - 1).
Since we’ve shown that gcd(a^m - 1, a^n - 1) divides a^d - 1 and a^d - 1 divides gcd(a^m - 1, a^n - 1), we conclude that gcd(a^m - 1, a^n - 1) = a^d - 1.
Greenchalkwhitechalk
lol *flashback intensifies*
can someone leave a proof of the last exercise?
Professor M. Penn, thank you for a solid proof and excellent examples of The Euclidean Algorithm in Number Theory Five. I fully understand this video/lecture from start to finish.
Shouldn't it be: r(k-1) = r(k) * q(k) (i.e. without the 1) for the last step?
No, it's q(k+1)
In which playlist do I find these reloaded number theory videos?
You needed one of the example numbers to be 2021. :)
anyone got a path to solving the second homework?
This video also teaches you the basics of calculus. Since a = dx & b = dy, this gives dy/dx = b/a.
Wtf
d is a random variable here, it doesn't tell a shit about extremely small quantities
That just means that y = (b/a)x
Mind size: Mega