I was reading someone explanation about Euclid's GCD. I understand some things that the person explain but I don't get some points. This is the explanation:
If both the large numbers $a$ and $b$ have a common factor, say $f$, then
$$a=n_1f$$
$$b=n_2f$$
where (by definition) both $n_1$ and $n_2$ are integers. Lets say $a > b$. Then it follows that $n_1 > n_2$. Now if we subtract the two numbers:
$a-b= (n_1-n_2)f$, where $n_1-n_2$ is also an integer.
This intuitively shows you that if two numbers share a common divisor, then the difference between the two numbers also shares the same divisor.
Euclid's theorem exploits this property of natural numbers to make the subsequent dividends smaller with each iteration, until the common factor is revealed.
Since $$a\mod\ b = a – kb\ (where\ kb<=a)$$
$$= n_1f – kn_2f\ (where\ n_1 > kn_2)$$
$$= (n_1-kn_2)f\ (where\ n_1 > kn_2)$$
$a \mod b$ shares this factor with $b$ as well. Now that $b$ is the greater of the two numbers, we pass $b$ as the first argument. gcd(b,a%b) will give us the answer.
Now, for the base case, if the second argument is equal to 0, that means that the previous division had no remainder. Put in simpler terms, the previous b was an exact multiple of a. We know there was no exact multiple before (larger than) that one, else the algorithm would have terminated. Therefore, this must be our answer and we return $a$.
My question is if $kb<=a$ why $n_1 > kn_2$ is the author implicit saying that this is for the case that $kb<a$ and not $kb=a$?
Also, I get that if two numbers share a common factor their difference does to but why explaining this first and then explain the modulo. Is there a relation between the two?
This are my two questions
Best Answer
The explanation is not well written. There’s really no need to introduce $a\bmod b$, though it does no real harm to do so. The real point is that there are unique integers $k$ and $r$ such that $a=kb+r$ and $0\le r<b$. Of course it’s true that $r=a\bmod b$, and if this explanation is being given in a computer science context it may be that pointing this out will help those who are already accustomed to using the $\bmod$ operator. Since $r\ge 0$, it’s also true that $kb\le a$. And of course we have
$$0\le r=a-kb=n_1f-kn_2f=(n_1-kn_2)f\;,$$
so $f$ is a factor of $r$.
Although it doesn’t actually say so, at this point the explanation splits into two cases, and your guess is correct: the author treats first the case $r>0$, which of course is equivalent to $n_1>kn_2$. It could be more clearly written something like this: