Number Theory: The Euclidean Algorithm Proof 

Do you know other channel like this, I want to learn more math

Thanks!

Yes it is a typo

By the division algorithm, a = bq + r where r < b because if it is great than or equal, it gets absorbed into q. So each r(n) < r(n-1)

that's because if the remained is not zero, then the sequence will keep going on

had the same question

In the previous "Divisibility Basic" part, there is a propositon that " If a|b and a|c, then for any x and y as integers, there is a|bx+cy". So according to this, we have d|a and d|b, then d|ax+by where x = 1, y = -q1.

@@bingqingwang850 okay thank you very much !!!

if d|a and d|b then we can write this as a = dx and b = dy (all integers). Any linear combination like pa + qb (p and q integers, again) can be written as dxa + dyb which you can factorize to d(xa + yb) which of course would be a multiple of d, the thing we initially sought to prove.

​@@mominahmed7-044 thank you very much

Here we are using the definition of the gcd. We start by showing that r_{n-1} is a common division of a and b then suppose we have another common divisor of a and b and show that must divide r_{n-1}. This is precisely the definition of gcd(a,b). That d in the proof is only a divisor of the gcd, it may not be the gcd itself.

d is assumed to be ANY common divisor of a and b, so if d | r_(n-1) then that means d

@@xRabidz I hope you see this comment :P As it drives me nuts :S we know that r__(n-1) is some common divisor, we do not know by the proof that it is the greatest one it may not be. So we take some divisor d, it may be the greatest but it also may not be the greatest, if we would take a d that is not the greatest one and r_(n-1) may not be the greatest one we are left with a d equal to r_(n-1), how does this proof that r_(n-1) is the greatest one ...

​@@mateuszpachulski6211r_(n-1) MUST be the greatest, we are not trying to prove with contradiction here. Basically gcd(a,b) is defined that ANY divisor d of a and b must divide the gcd. Think about it, any common factors of 30 and 40 must divide 10.

thanks helped alot@@xRabidz

Great job punmaster, you’ve successfully ruined my day😂

@@MonkeyAssassin-qi8gw Then my work here is done 👍 On the flip side, if you keep listening to painful puns, eventually you’ll become numb(er)…

@@PunmasterSTP you’re ruthless

@@MonkeyAssassin-qi8gw I once told someone something ridiculous, and they said "Euclid-en' me!"

rn-2 is not a divisor of rn-3, because rn-3/ rn-2 have a rest ≠ 0. I mean an example is 12 = rn-3 ,8 = rn-2 and 4 = rn-1. There you see 12/8 = 1*8 + 4 = 1,5. Not a divisor.

We know, r_{n-1} | r_{n-2}, hence q_{n-2} * r_{n-2} + r_{n-1} | r_{n-3}.

r1 < b otherwise the choice for q1 was wrong. r2 < r1 otherwise the choice for q2 was wrong. and so on and so forth. this is a consequence of how remainder upon division is defined.

It's greatest common divisor, emphasis on greatest.

Because we can write r_{n-2} = r_{n-1}*q_{n}, which is equivalent to saying r_{n-1}|r_{n-2} (by divisibility definition: a=bn then a|n)

@@rayzewis3361 but r_{n-2} = r_{n-1}*q_{n} + r_{n} sir you can use it not this r_{n-2} = r_{n-1}*q_{n}

Then there would be no purpose in proving😅,we assume that d does not equal one as there would be no point.

Huh can you clarify what you mean or give an example?

Yes I think so but either way the point is clear I guess