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'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 2

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 3

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 4

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 5

Corrrect, $\ d\mid a,0\iff d\mid a,\ $ so $\ \gcd(a,0) = \gcd(a) =$ ${\rm greatest\_divisor}(a) = |a|,\,$ for $a\neq 0$.

Remark $ $ This is a special case $\,b=0\,$ of

$$\,a\mid b\,\Rightarrow\,\gcd(a,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).