Euclidean algorithm

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

(edited 1 year ago)

Reply 1

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

(edited 1 year ago)

Reply 2

Student 999

Original post by mqb2766

Confused on how they deduced that gcd(a,b) <= gcd(b,r)

(edited 1 year ago)

Reply 3

mqb2766

Original post by Student 999

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

(edited 1 year ago)

Reply 4

Student 999

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?

Reply 5

mqb2766

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.

(edited 1 year ago)

Reply 6

Student 999

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?

Reply 7

mqb2766

Original post by Student 999

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.

(edited 1 year ago)

Reply 8

Student 999

Original post by mqb2766

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 ?

Reply 9

mqb2766

Original post by Student 999

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?

Reply 10

Student 999

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

Reply 11

mqb2766

Original post by Student 999

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

(edited 1 year ago)

Reply 12

Student 999

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

Reply 13

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)

Reply 14

mqb2766

Original post by Student 999

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