Show that $\gcd(a, 0)$ exists and equals $|a|$ for all $a$ in $\mathbb Z$

Question

I came up with the proof in the paragraph below. My question is about how I expressed the proof, and about the first part of the question above.

For one, my proof seems to me very wordy compared to proofs in my textbook or shown by my professors, so I'd appreciate input on how to express it in a more formal way. Also, I haven't shown that $d$ (where $d = \gcd(a, 0)$) exists and I don't see how I'd do so.

PROOF: Suppose $d = \gcd(a, 0)$, where $d$ is an integer. Then $d \mid a$ and $d \mid 0$. As every integer divides $0$, $d$ will be the largest divider of $a$. The largest divider of any integer is itself. However, $a$ may be negative and $d$, by definition, is greater or equal than zero, so $d = |a|$.

I appreciate any answers. Thanks!

Answer 1

You can use the Bezout related definition of the gcd:

Understanding the Existence and Uniqueness of the GCD

$$\gcd(a,b)=\min\,\{au+bv\mid au+bv > 0,\, (u,v)\in \mathbb Z^2\}$$

For $b=0$ you get (for $a\neq 0$)

$\gcd(a,0)=\min\,\{au\mid au>0,\, u\in \mathbb Z\}$ and it is clear that $u=\pm 1=\operatorname{sgn}(a)$

Making $\gcd(a,0)=|a|$ as a result.

---

To go further, there are factorial rings where the notion of sign (positivity or negativity) is not defined (think about complexes for instance).

In this case the gcd is defined down to a multiplication by a unit, where units are all divisors of $1$.

So it is just a convention for integers that we take $d>0$.

Answer 2

It depends on what is the definition of greatest common divisor you use. However, your attempt at a proof is not good, because you prove nothing at all.

If your definition is

the greatest common divisor of the integers $a$ and $b$, not both zero, is the largest integer $d$ such that $d\mid a$ and $d\mid b$

then the proof that $|a|=\gcd(a,0)$, for $a\ne0$, is very simple: $|a|$ is a divisor of both $a$ and $0$. If $d$ is a divisor of $a$, then $d\le |a|$: indeed, if $d$ divides $a$, then $a=cd$, so $|a|=|c|\,|d|\ge|d|$, because $|c|\ge1$, and therefore $d\le|d|\le|a|$.

If your definition is

the greatest common divisor of the integers $a$ and $b$ is a nonnegative integer $d$ such that

1. $d\mid a$ and $d\mid b$;
2. for every integer $c$, if $c\mid a$ and $c\mid b$, then $c\mid d$

then the statement that $|a|=\gcd(a,0)$ is obvious.

Note that the first definition requires that $a$ and $b$ are not both zero, whereas for the second definition, the condition is not necessary.

Answer 3

You're on the right track! The zero thing is true, but the gcd isn't by definition nonnegative (greater than or equal to 0.) Since the gcd is, well, the greatest number that divides both, consider all divisors of each. Here's how I would prove it:

Since any nonzero number divides 0, the divisors of 0 are $ ..., -2, -1, 1, 2, ..., |a|-1, |a|, |a|+1, ... $.

And $a$ will have some number of divisors, but it's largest will be $|a|$, since $|a|$ divides $a$, and anything larger than $|a|$ cannot possibly divide $a$.

Therefore, the largest number that divides both is just the largest number that divides $a$, which is $|a|$.

Answer 4

Correct, $\ d\mid a,0\!\iff\! d\mid a,\, $ thus $\, \gcd(a,0) = \!\!\overbrace{\gcd(a) = |a|}^{\text{greatest divisor of }\,a}\!\!,\,$ for $a\neq 0$.

Remark $ $ This is a special case $\,\color{#c00}{b=0}\,$ of

$$\,a\mid\color{#c00} b\,\Rightarrow\,\gcd(a,\color{#c00}b,c,\ldots) = \gcd(a,c,\ldots)$$

which is a special case of: $\ \gcd(a,b,c,\ldots)\, =\, \gcd(a,\, b\bmod a,\, c\bmod a,\ldots)$

i.e. gcds are unchanged by modding out other gcd args by any given arg - a fact familiar from the Euclidean gcd algorithm. You may find it instructive to prove these more general results (the proof is similar and only slightly more difficult).

Beware $ $ The above proof works in every gcd domain (domains where all gcds $\:\!(a,b)\:\!$ exist), but common proofs in $\,\Bbb Z\,$ via Bezout fail to generalize to familiar UFDs like $\,\Bbb Z[x],\, \Bbb Q[x,y]\,$ where gcds generally do not have linear (Bezout) form, e.g. in $\,\Bbb Q[x,y]\,$ we have $\,(x,y) = 1\,$ but this gcd is not of Bezout form, else $\,x\:\!g(x,y) + y\:\! f(x,y) = 1,\,$ so eval at $\,x = y = 0\,$ yields $\,0 = 1.\,$ Ditto for $(2,x)$ in $\,\Bbb Z[x]$.

Answer 5

For what it's worth, I would reword it thus:

Suppose $d = \gcd(a, 0)$, where $d$ is an integer and $a$ is a positive integer. Then $d \mid a$ and $d \mid 0$. As every nonzero integer divides $0$, $d$ will be the largest divisor of $a$. The largest divisor of any positive integer is that positive integer itself, and so $d = a$. Given that $\gcd(a, -a) = |a|$, it follows that if $a$ is allowed to be negative, then $d = |a|$.

Okay, so that has a greater word count than what you wrote, but hopefully it's clearer.

I'm not a math teacher nor any kind of professional mathematician, so feel free to take this with a grain of salt.

Answer 6

Several years late to this answer, but here is how I approached it.

---

Proof: Suppose $d = gcd(a, 0)$ is the greatest common divisor of $a$ and $0$. Then $d|a$ by definition, which means $d \leq a$.

Bezout's identity tells us that we can always express the greatest common divisor of two numbers as an integral linear combination for some integers $x$ and $y$:

$$ d = ax + by \\ = ax + 0y \\ = ax $$

But if $d = ax$, then clearly $d$ can be written as an integer multiple of $a$. That, by definition, means that $a|d$, and $a \leq d$.

Taken together, $a \leq d \land d \leq a \implies d = a$. And by definition of greatest common divisor, $d$ must be a positive integer, so $d = |a|$.