Prove that if $a \mid b$ then $\gcd(a,b) = |a|$

Question

I am having trouble completing the proof if $a \mid b$ then $\gcd(a,b) = |a|$.

My attempt: If $a\mid b$ there is a $k \in \mathbb{Z}$ such that $b = ak$. Let $d = \gcd(a,b)$. Then $d \mid a$ and $d\mid b$ so by hypothesis we have $d\mid a$ and $d\mid ak$. Hence, $d \leq \gcd(a,ak)$. We can easily see that the largest common denominator of $a$ and $ak$ is $|a|$, thus $d \leq\gcd(a,ak) = |a|$ so $\gcd(a,b) \leq |a|$.

I am stuck and not sure how to show the reverse inequality $|a| \leq \gcd(a,b)$ to complete the proof.

Answer 1

Clearly $|a|$ is a divisor of $a$.

Also, since $b=ak$. We have $b=\operatorname{sign}(b)|a||k|$, that is $|a|$ is a divisor of $b$.

Hence as a common divisor of $a$ and $b$., it is at most the greatest common divisor of $\gcd(a,b)$.

$$|a| \le \gcd(a,b)$$

Answer 2

$\gcd(a,b)$ is a divisor of $a$ by definition and in turn of $|a|$. It is a known fact that if $x,y>0$ such that $x\mid |y$, then $x\leq y$. Hence, $\gcd(a,b)\mid |a|$ implies $\gcd(a,b)\leq |a|$.

Now $a\mid b$ implies $|a|$ is a common divisor of $a$ and $b$. $\gcd(a,b)$ is the greatest of such common divisors. Hence, $|a|\leq \gcd(a,b)$.

Answer 3

"such that b=ak.... d≤gcd(a,ak)

You seem to be overlooking that if $b = ak$ then ..... $b = ak$!

So if $b=ak$ then $\gcd(a,b) = \gcd(a,ak)$. There is not need to conclude that if $d = \gcd(a,b)$ then $d \le \gcd(a,ak)$. If $d=\gcd(a,b)$ and $b = ak$ then $d$ EQUALS $\gcd(a,ak)$.

But I can not accept your claim "We can easily see that the largest common denominator of $a$ and $ak$ is $|a|$". I think that is the entire point of the proof and must be spelled out. (I have an explanation below)

====== Complete Answer======

Dont let the absolute value throw you. The integer factors of a negative number are exactly the same as the factors of the equivalent positive number (i.e. the absolute value), and if $d$ is a factor of an integer then $-d$ is as well, and positive numbers are larger than even numbers so a $\gcd$ is always positive. We can assume without loss of generality all numbers are non-negative.

If $|a| = a'>0$ and $|b| = b' \ge 0$ then $a|b \iff a'|b'$ and $\gcd(a,b) = \gcd(a',b')$ by the argument in the paragraph above. So we just need to prove the following.

if $a$ and $b$ are non-negative integers and $a|b$ then prove $\gcd(a,b) = a$.

Pf: Well, $a = 1\cdot a$ so $a|a$ and $a|b$ so $a$ is a common divisor. We know that $a\ne 0$ because $0$ does not divide anything. If $d > a$ then $0 < \frac ad < 1$. But there is no such integer so $d\not \mid a$. So $d$ is not a common divisor of $a$ and $b$. So the greatest common divisor of $a$ and $b$ is $a$.

This assumes your definition of $\gcd(a,b)$ is the largest common divisors of $a$ and $b$. Many texts uses $\gcd(a,b)$ is the positive common divisor so that every possible common divisor is a divisor of $\gcd(a,b)$.

Proof using that definition: Now $a$ is a common divisor of $a$ and $b$ so by this definition of $\gcd$ we must have $a|\gcd(a,b)$. If $a > \gcd(a,b)$ then $a\not \mid \gcd(a,b)$ so $a \le \gcd(a,b)$. And if $a < \gcd(a,b)$ then $\gcd(a,b) \not \mid a$ and $\gcd(a,b)$ is not a common divisor of $a$ and $b$. So $a \ge \gcd(a,b)$. So $a \ge \gcd(a,b)$ and $a \le \gcd(a,b)$. So $a = \gcd(a,b)$.

Answer 4

This is very easy if you use that $\mathbf Z$ is a P.I.D.: $\:\gcd(a,b)$ is the positive generator of the ideal $(a, b)$.

Now, if $a\mid b$, it obvious that this ideal is none other than the principal ideal generated by $a$, whence the result.

Answer 5

$a\mid b\,\Rightarrow\, \{a,b\}$ and $\{a\}$ have $\rm\color{#e00}{same}$ set of $\,\rm \color{#0a0}{cd} :=$ common divisors (since $\,d\mid a\mid b\,\Rightarrow\,d\mid b),\,$ so same greatest common divisor: $\, {\rm g\color{#0a0}{cd}}\{a,b\} = \max {\rm \color{#0a0}{cd}}\{a,b\} \, {\bf \color{#e00}=} \max {\rm \color{#0a0}{cd}}\{a\} = |a|$.

OR $\ \ (a,\,b)\, =\, (a)\,(1,\,b/a) = |a|\cdot 1 = |a|\ $ by the GCD distributive law.

OR by Euclid $\,(a,b) = (a, b\bmod a) = (a,0) = |a|$.

OR by Bezout the gcd = least positive integer of form $\,ja\!+\!kb = a(j+kb/a) = a\Bbb Z\,$ by $\,k=0\,$