Back
to top
Euclidean algorithm
Watch this thread
Announcements
Page 1 of 1
Go to first unread
Skip to page:
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Is the reason as to why it works for the case that r1 =/=0 is mainly because r1 and q1 do not share common factors hence you keep cycling through b by your assumed GCD (r_n) until you reach the point where you find a r_n that doesn't produce a remainder.
Sorry if my thoughts are worded very poorly![Name: IMG_64C854B24CE1-1.jpeg
Views: 9
Size: 43.8 KB]()
![Name: Screenshot 2022-07-03 at 14.28.51.jpg
Views: 10
Size: 51.4 KB]()
Sorry if my thoughts are worded very poorly
Last edited by Student 999; 1 month ago
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report
#2
Have you tried writing something like
a = rk
b = sk
where k is the hcf(a,b) so r and s don't share any common factors and thinking about what happens? Failing that, its a classic problem and well covered in many places on the web.
wiki
https://en.wikipedia.org/wiki/Euclidean_algorithm
with rectangle animation
a = rk
b = sk
where k is the hcf(a,b) so r and s don't share any common factors and thinking about what happens? Failing that, its a classic problem and well covered in many places on the web.
wiki
https://en.wikipedia.org/wiki/Euclidean_algorithm
with rectangle animation
Last edited by mqb2766; 1 month ago
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
(Original post by mqb2766)
Have you tried writing something like
a = rk
b = sk
where k is the hcf(a,b) so r and s don't share any common factors and thinking about what happens? Failing that, its a classic problem and well covered in many places on the web.
wiki
https://en.wikipedia.org/wiki/Euclidean_algorithm
with rectangle animation
Have you tried writing something like
a = rk
b = sk
where k is the hcf(a,b) so r and s don't share any common factors and thinking about what happens? Failing that, its a classic problem and well covered in many places on the web.
wiki
https://en.wikipedia.org/wiki/Euclidean_algorithm
with rectangle animation
Last edited by Student 999; 1 month ago
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report
#4
a = b*q + r
if k divides both a and b, then it must divide b and r as well. Hence the inequality. However, with a bit more reasoning, you'd expect equality to hold
Last edited by mqb2766; 1 month ago
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
(Original post by mqb2766)
As
a = b*q + r
if k divides both a and b, then it must divide b and r as well. Hence the inequality. However, with a bit more reasoning, you'd expect equality to hold
As
a = b*q + r
if k divides both a and b, then it must divide b and r as well. Hence the inequality. However, with a bit more reasoning, you'd expect equality to hold
I can't see what the difference is between the two situations?
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report
#6
(Original post by Student 999)
In the statement they presented two cases so d|a d|b and case 2 of e|b and e|r
I can't see what the difference is between the two situations?
In the statement they presented two cases so d|a d|b and case 2 of e|b and e|r
I can't see what the difference is between the two situations?
a - bq = r
Similarly if e|r and e|b then e|a comes from
a = bq - r
The <= and >= so must be = approach goes back to Archimedes proof of the quadrature of the parabola.
Last edited by mqb2766; 1 month ago
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
(Original post by mqb2766)
They're just using a symmetry argument to argue its <= and >=, so it must be =. They argue that d|a and d|b, then d|r which comes about from writing as
a - bq = r
Similarly if e|r and e|b then e|a comes from
a = bq - r
The <= and >= so must be = approach goes back to Archimedes proof of the quadrature of the parabola.
They're just using a symmetry argument to argue its <= and >=, so it must be =. They argue that d|a and d|b, then d|r which comes about from writing as
a - bq = r
Similarly if e|r and e|b then e|a comes from
a = bq - r
The <= and >= so must be = approach goes back to Archimedes proof of the quadrature of the parabola.
for the first case the idea of the inequality is based off euclidean's algorithm
so a=bq+r whereas the second case is a-bq = r.
However I still don't quite get how why it isn't just gcd(a,b)= gcd(b,r)
could you provide an example of numbers to demonstrate the inequality?
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report
#8
(Original post by Student 999)
Oh I see now
for the first case the idea of the inequality is based off euclidean's algorithm
so a=bq+r whereas the second case is a-bq = r.
However I still don't quite get how why it isn't just gcd(a,b)= gcd(b,r)
could you provide an example of numbers to demonstrate the inequality?
Oh I see now
for the first case the idea of the inequality is based off euclidean's algorithm
so a=bq+r whereas the second case is a-bq = r.
However I still don't quite get how why it isn't just gcd(a,b)= gcd(b,r)
could you provide an example of numbers to demonstrate the inequality?
If you said d|a and d|b, then d|r using
a-bq = r
then youve shown that gcd(a,b)|r so gcd(a,b) <= gcd(b,r) as there could be a divisor of both b and r which doesn't divide a (there isnt, but you have to show it). Doing the 2nd part allows you to conclude the result.
Last edited by mqb2766; 1 month ago
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
(Original post by mqb2766)
Jumping to the result, you want to establish that gcd(a,b)= gcd(b,r), which indeed it is.
If you said d|a and d|b, then d|r using
a-bq = r
then youve shown that gcd(a,b)|r so gcd(a,b) <= gcd(b,r) as there could be a divisor of both b and r which doesn't divide a (there isnt, but you have to show it). Doing the 2nd part allows you to conclude the result.
Jumping to the result, you want to establish that gcd(a,b)= gcd(b,r), which indeed it is.
If you said d|a and d|b, then d|r using
a-bq = r
then youve shown that gcd(a,b)|r so gcd(a,b) <= gcd(b,r) as there could be a divisor of both b and r which doesn't divide a (there isnt, but you have to show it). Doing the 2nd part allows you to conclude the result.
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report
#10
(Original post by Student 999)
I see that makes a bit more sense now thanks, for the bezout identity what is the intuition behind it, you can break down remainders using Euclidean algorithm and if you reverse the process you can sum up/rewrite the all the remainders back to it's primary equation of a= bq +r ?
I see that makes a bit more sense now thanks, for the bezout identity what is the intuition behind it, you can break down remainders using Euclidean algorithm and if you reverse the process you can sum up/rewrite the all the remainders back to it's primary equation of a= bq +r ?
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Not quite sure where exactly euclidean's algorithm is applied here, but I do understand the method being applied here
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#12
Report
#12
(Original post by Student 999)
![Name: Screenshot 2022-07-03 at 21.06.54.png
Views: 5
Size: 92.7 KB]()
Not quite sure where exactly euclidean's algorithm is applied here, but I do understand the method being applied here
Not quite sure where exactly euclidean's algorithm is applied here, but I do understand the method being applied here
2016!+1 = 2016(2015!+1) - 2015 = 2015(2015!+1) + (2015!+1 - 2015)
so using euclid (allowing/a bit of reasoning for negative remainder)
gcd(2016!+1, 2015!+1) = gcd(2015!+1, 2015) = 1
Last edited by mqb2766; 1 month ago
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#13
(Original post by mqb2766)
Assuming you want to find gcd(2016!+1, 2015!+1), then its as the text states. 2015!+1 does not have a divisor <= 2015. Noting (a = qb + r)
2016!+1 = 2016(2015!+1) - 2015 =
so using euclid (allowing/a bit of reasoning for negative remainder)
gcd(2016!+1, 2015!+1) = gcd(2015!+1, 2015) = 1
Assuming you want to find gcd(2016!+1, 2015!+1), then its as the text states. 2015!+1 does not have a divisor <= 2015. Noting (a = qb + r)
2016!+1 = 2016(2015!+1) - 2015 =
so using euclid (allowing/a bit of reasoning for negative remainder)
gcd(2016!+1, 2015!+1) = gcd(2015!+1, 2015) = 1
Thanks
0
reply
Student 999
Badges:
12
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#14
In line three of the solution why is it they chose gcd(a,b)<=gcd(a+bc, b)
Isn't gcd(a,b) <= gcd(a+bc, a) also valid? Or does it not matter in the overall proof
Not fully sure what they're done on line 4 ,
is it just the fact that by euclidean algorithm
a + bc = bc + a hence the gcd(a+ bc , b) = gcd(a,b)
since gcd( a+bc,b) <= gcd ( a+bc,b)
which is equivalent to gcd( a+bc,b) <= gcd (a,b)
hence for both equations to be true gcd(a,b)=gcd(a+bc,b)
0
reply
mqb2766
Badges:
19
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#15
Report
#15
(Original post by Student 999)
![Name: Screenshot 2022-07-03 at 22.28.30.png
Views: 5
Size: 108.6 KB]()
![Name: Screenshot 2022-07-03 at 22.28.50.png
Views: 5
Size: 219.9 KB]()
In line three of the solution why is it they chose gcd(a,b)<=gcd(a+bc, b)
Isn't gcd(a,b) <= gcd(a+bc, a) also valid? Or does it not matter in the overall proof
Not fully sure what they're done on line 4 ,
is it just the fact that by euclidean algorithm
a + bc = bc + a hence the gcd(a+ bc , b) = gcd(a,b)
since gcd( a+bc,b) <= gcd ( a+bc,b)
which is equivalent to gcd( a+bc,b) <= gcd (a,b)
hence for both equations to be true gcd(a,b)=gcd(a+bc,b)
In line three of the solution why is it they chose gcd(a,b)<=gcd(a+bc, b)
Isn't gcd(a,b) <= gcd(a+bc, a) also valid? Or does it not matter in the overall proof
Not fully sure what they're done on line 4 ,
is it just the fact that by euclidean algorithm
a + bc = bc + a hence the gcd(a+ bc , b) = gcd(a,b)
since gcd( a+bc,b) <= gcd ( a+bc,b)
which is equivalent to gcd( a+bc,b) <= gcd (a,b)
hence for both equations to be true gcd(a,b)=gcd(a+bc,b)
For line 4, its very similar to the previous posts. You know d|(a+bc), d|b gives d|r as
a+bc = qb + r
So
a = a+bc-bc = qb -bc + r = (q-c)b + r
as d divides the right hand side, d|a, so you again have the double inequality ....
0
reply
X
Page 1 of 1
Go to first unread
Skip to page:
Quick Reply
