0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I admit that is weirdly worded. I'm thinking it is most likely a typo. But as you point out, if a - kb = 0 (which happens if and only if n_1 = n_2k) we don't have to go any further as we are done. So maybe the author meant that. But, yes, if a- kb = n1f - n2kf = (n1 - n2k)f = 0f if n1 = n2 if a = kb and n1 = n2k. $\endgroup$ – fleablood May 20 '16 at 17:13
1
$\begingroup$

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:

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<b$.

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.

$\endgroup$
  • $\begingroup$ I think the a mod b = a - kb notation is okay. I think when I first saw mod notation as a student I naively thought of it as "the remainder after removing a bunch of b's to get to the very least remainder" and it's that context that we wan to use to find the gcd. It wouldn't be immediately clear that we replace a with a - kb. I'd ask which k? and how do we know such a switch can then apply to kb and why do we think this will end? Or continue to the end? Somehow know a' = a - kb "equal" "the" a mod b-- the "bottom" residue makes the process clearer. sort of... but in a naive way. $\endgroup$ – fleablood May 20 '16 at 22:19
  • $\begingroup$ @fleablood: There's nothing wrong with it; it's just unnecessary, and that notation, with $\bmod$ as a binary operation, isn't universally used or understood. For someone coming to the algorithm from elementary number theory, the fact that there are unique integers $k$ and $r$ with the stated properties is the natural starting point. But it appears that this passage was aimed more at students approaching the subject from a computer science or programming background, and as I said, in that case it may be a nice, familiar way to think about the remainder. $\endgroup$ – Brian M. Scott May 20 '16 at 22:29
0
$\begingroup$

Since the OP had the word intuition in the title, this answer 'paints a picture' that can be examined for another viewpoint/angle.

The wikipedia states

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Division is just repeated subtraction, so the important thing is to understand this first.

Let $a$ and $b$ be two integers greater than $1$ with $a \gt b$ and set $\hat a = a - b$.

To trust the algorithm means that you accept this,

$$ \gcd(\hat a, b)) = \gcd(a, b) $$

If $c$ divides both $a$ and $b$ then it divides $\hat a$.

So without much work you know that $\gcd(a, b)$ divides $\gcd(\hat a, b))$ but you also need to be sure that $\gcd(\hat a, b))$ has not 'grown bigger'.

Using the prime factorization theorem, write

$$\tag 1 a = Q_a P \; \text{, }\; b = Q_b P $$

where each of $Q_a, Q_b, P $ represent a product of primes (or equal to $1$) and $P$ is the gcd of $a$ and $b$. You might say that $Q_a$ and $Q_b$ are 'disjoint'.

Then

$$ \hat a = (Q_a - Q_b)P$$

We have to show that if a prime $q$ divides $(Q_a - Q_b)$ it can't be one of the factors of $Q_b$ (if it did the gcd $P$ would 'grow'). To get a contradiction assume it divides both.

$$ q \mid (Q_a - Q_b) \; \text{ and } q \mid Q_b $$

But then $q$ would have to divide $Q_a$. This would imply that $q$ was (already) a common prime factor in both $Q_a$ and $Q_b$. But then $\text{(1)}$ wouldn't make sense, since we could then 'roll' $q$ into $P$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.