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!

  • 2
    $\begingroup$ Your proof looks good, but it seems that there is a problem if $a = 0$. Should it be for all $a \in \mathbb{Z}$,$a \ne 0$? $\endgroup$
    – D.B.
    Dec 26, 2018 at 21:25
  • $\begingroup$ As for existence, surely $a$ must have a non-zero number of divisors, each of which is also a divisor for $0$. Then $a$ and $0$ have some divisors in common. Then there is a largest such divisor. $\endgroup$
    – Alex
    Dec 26, 2018 at 21:28
  • $\begingroup$ @D.B. A related MSE question is What is gcd(0,0)?. Also, for carraig, I agree with D.B. that your proof looks good. $\endgroup$ Dec 26, 2018 at 21:29
  • $\begingroup$ @D.B. Is there a problem if a = 0? It seems to me that the gcd(0,0) would be 0. Regardless, I copied the question word for word from my textbook. $\endgroup$
    – carraig
    Dec 26, 2018 at 21:30
  • $\begingroup$ I think the last sentence needs to spell out why $a<0$ implies $d=|a|$, rather than just asserting it. Something to the effect that $a$ and $-a$ have the same divisors, maybe. $\endgroup$
    – timtfj
    Dec 26, 2018 at 21:32

6 Answers 6


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


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.


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


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.

  • 1
    $\begingroup$ I used the definition given as follows: For a and b in Z, the integer d is a greatest common divisor of a and b if: (i) d|a and d|b; (ii) if e in Z satisfies both e|a and e|b, then e|d; (iii) d ≥ 0. $\endgroup$
    – carraig
    Dec 27, 2018 at 0:00
  • 1
    $\begingroup$ @carraig That's the second definition I gave. I confirm that with that definition, $\gcd(a,0)=|a|$ is obvious: (i) $|a|$ divides both $a$ and $0$; (ii) if $e$ divides both $a$ and $0$, then $e$ divides $|a|$; (iii) $|a|\ge0$. In other words, you just check that $|a|$ fits the definition for being called a greatest common divisor of $a$ and $0$, which it does. $\endgroup$
    – egreg
    Dec 27, 2018 at 0:05
  • $\begingroup$ Thanks. I've a question about your proof if we're using the first definition you provided. In that case, you've shown very clearly that |d| ≤ |a|, so is this equivalent to proving that d = |a| under the condition that we're assuming d to be the largest integer that divides a? $\endgroup$
    – carraig
    Dec 27, 2018 at 0:13
  • $\begingroup$ @carraig You're starting from the wrong point: you want to show that $|a|$ is the gcd; in the proof $d$ denotes an arbitrary common divisor, so you cannot prove it is equal to $|a|$. $\endgroup$
    – egreg
    Dec 27, 2018 at 0:15

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


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .