6
$\begingroup$

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!

$\endgroup$
  • 1
    $\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 '18 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 '18 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$ – John Omielan Dec 26 '18 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 '18 at 21:30
  • $\begingroup$ @carraig As I mentioned in my other comment, a fairly good discussion about $\gcd\left(0,0\right)$ is at What is gcd(0,0)?. $\endgroup$ – John Omielan Dec 26 '18 at 21:31
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 '18 at 0:00
  • $\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 '18 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 '18 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 '18 at 0:15
0
$\begingroup$

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

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