Euclidean algorithm

Watch this thread
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
Report Thread starter 1 month ago
#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 poorlyName:  IMG_64C854B24CE1-1.jpeg
Views: 9
Size:  43.8 KBName:  Screenshot 2022-07-03 at 14.28.51.jpg
Views: 10
Size:  51.4 KB
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 1 month ago
#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
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
Report Thread starter 1 month ago
#3
Name:  Screenshot 2022-07-03 at 16.07.28.png
Views: 11
Size:  98.2 KB
(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
Confused on how they deduced that gcd(a,b) <= gcd(b,r)
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 1 month ago
#4
(Original post by Student 999)
Name:  Screenshot 2022-07-03 at 16.07.28.png
Views: 11
Size:  98.2 KB


Confused on how they deduced that gcd(a,b) <= gcd(b,r)
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
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
Report Thread starter 1 month ago
#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
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?
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 1 month ago
#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?
They're just using an approach 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.
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
Report Thread starter 1 month ago
#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.
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?
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 1 month ago
#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?
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.
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
Report Thread starter 1 month ago
#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.
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
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 1 month ago
#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 ?
Is there a context to what youre asking? Given the hcf of two numbers and one of the numbers, you can't uniquely determine the other, though you can modulo ... Its closely tied into solving diophantine equations if thats whats youre alluding to?
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
Report Thread starter 1 month ago
#11
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
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 1 month ago
#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
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 = 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
Report Thread starter 1 month ago
#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
Oh I keep getting confused by the rearranged form of the division algorithm a=qb + r .
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
Report Thread starter 1 month ago
#14
Name:  Screenshot 2022-07-03 at 22.28.30.png
Views: 5
Size:  108.6 KBName:  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)
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 1 month ago
#15
(Original post by Student 999)
Name:  Screenshot 2022-07-03 at 22.28.30.png
Views: 5
Size:  108.6 KBName:  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)
For line 3, I can only guess that theyre working towards the orginal euclidean algorithm where you kept subtracting b off a (c=-1) until you hit the remainder. For your example, if you choose a as the second argument and c=0, youd get gcd() = a.

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

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest

How are you feeling about your SQA results?

They're better than I expected (20)
32.79%
They're what I expected (19)
31.15%
They're worse than what I expected (22)
36.07%

Watched Threads

View All