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