# 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

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

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

**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

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

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

**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

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

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?

**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?

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

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

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.

**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.

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

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

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?

**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?

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

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

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.

**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.

0

reply

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

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 ?

**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 ?

0

reply

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

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

Not quite sure where exactly euclidean's algorithm is applied here, but I do understand the method being applied here

**Student 999**)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

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

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

**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

Thanks

0

reply

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

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

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)

**Student 999**)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

Back

to top

to top