# Euclidean algorithm

Announcements
#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
Last edited by Student 999; 1 month ago
0
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
#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
Confused on how they deduced that gcd(a,b) <= gcd(b,r)
Last edited by Student 999; 1 month ago
0
1 month ago
#4
(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
Last edited by mqb2766; 1 month ago
0
#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
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
#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
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
#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
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
#11

Not quite sure where exactly euclidean's algorithm is applied here, but I do understand the method being applied here
0
1 month ago
#12
(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
Last edited by mqb2766; 1 month ago
0
#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
#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
1 month ago
#15
(Original post by 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 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
X

new posts Back
to top
Latest

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### Poll

Join the discussion

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%