elementary number theory - Euclid GCD intuition

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

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

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

$$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:

If $r>0$, we invoke the algorithm on $b$ and $r=a\bmod b$, since we’ve just seen that $b$ and $r$ have the same common factors (and hence the same greatest common divisor) as $a$ and $b$. Note that $r

If $r=0$, then $a$ is a multiple of $b$, and therefore $\gcd(a,b)=b$. This is the first step at which the remainder was $0$, as otherwise the algorithm would have terminated at an earlier step, so we return $b$ (not $a$).

Finally, the algorithm must terminate, as the second argument is always a positive integer and decreases at each step.