Third para from here, i write a basic explanation of Euclid's algorithm for calculating G.C.D.
Why i write this version is because, it baffles me when i see an opening statement:
'we need to find g.c.d of numbers a and b .. consider (a - b)'
[or]
'we need to find g.c.d of numbers a and b .. consider a = (q1)b + (r1) and b = (q2)(r1) + (r2)'
The 'consider this or that' version might be terse and tight to prove, but i think the motivation behind how such consideration came into being gets lost...
It is like for example, you want to understand how red-black trees are designed the way they are without knowing their evolution from the 2-3 trees.
You will keep wondering forever as how such 'considerations' occur.
Maybe even resigning to a false notion that it just can't happen to you and so get on with the considerations that are already laid out.
But then while your ability to memorize how something works enhances, your ability to arrive at how something can work diminishes...
So you have two numbers a and b, and you need to find their greatest common denominator, G.C.D.
Let d be the G.C.D of a and b.
Now, what do we want to know? we want to know what d is... But what do we actually know?
We only know about two numbers a and b whose G.C.D, d we want... How can we get to d from there?
We know a and b ... and we also know that a and b are actually a bunch of 'd's lumped together... [ ex: a = xd and b = yd ]
So a maybe some x number of 'd's and b maybe some y numbers 'd's ...
But, we don't want x or y number of 'd's , we just want "a" 'd' ..
We some how need a way to reduce that x or y down to one, and we will be at our prize.
If a > b, we can reduce the numbers of 'd's in a by the number of 'd's in b ...
How can we do that? Well, just subtract b from a... and now we have (x-y) number of 'd's in a as opposed to the previous x number of 'd's ..
Now that is some progress... And we can do this chopping off, till a > b...
What if a becomes less than b ? Simple, just swap them... and repeat...
So, where does this repeated chopping down of the number of 'd's from either a or b lead us to?
What happens in the end?
In the end, a will have become equal to b.
What does it mean when a equals b? It means both of them have the same number of 'd's . And when we are looking at the d as the "greatest" common denominator, both have them, exactly have one 'd'.
This explanation is no different* from others except for the emphasis on the thought process that leads one to the first step in problem size reduction.
* Or even deficient w.r.t completeness.
