2
$\begingroup$

This question is more general, but I am going to use a theorem to motivate it.

Suppose I want to prove that there exists a rational $r$ such that $r^3 + r + 1 = 0$. The first step is to assume that there is such an $r$, so $r = \frac{p}{q}$ where $p,q \in \mathbb{Z}$, $q \neq 0$ where $p,q$ are relatively prime.

Here's my question. If this $r$ were $0$ (it's not, and I can rule out it out, but I'm interested in whether I need to actually rule it out for full rigor), that $r = \frac{0}{q}$. But $0 \cdot 0 = 0$ and $0 \cdot q = 0$, so both $p$ and $q$ have a common factor of $0$.

But $\gcd(p,q) = 1$, still, since $1 > 0$, and it doesn't seem to matter if $q$ is negative.

Based on this, my conclusion is that it doesn't actualy matter if $p = 0$ and I don't need to consider this. Is that right? If I wrote "assume $p$ and $q$ have no common factors," that's already a bit ambiguous because they surely have a common factor of $1$, but the more formal "relatively prime" assumption seems ok.

$\endgroup$
3
  • 1
    $\begingroup$ This may answer your question: math.stackexchange.com/questions/1156814/… $\endgroup$
    – Théophile
    Jan 10, 2021 at 4:39
  • 2
    $\begingroup$ $\gcd(m, n)$ can be defined uniformly as the unique positive generator of the ideal generated by $m$ and $n$ in the integers $\mathbb{Z}$. With this definition it follows that $\gcd(0, n) = n$ (for $n$ a positive integer) and hence that $\pm 1$ are the only integers relatively prime to $0$. In particular, $0$ is not relatively prime to itself. But $\frac{0}{1}$ is still a fraction in lowest terms. This definition has the benefit of baking in Bezout's theorem. $\endgroup$ Jan 10, 2021 at 4:58
  • $\begingroup$ "But 0⋅0=0 and 0⋅q=0, so both p and q have a common factor of 0." Reread this. ... $0\cdot q = 0$ means that $q$ is a factor of $0$. Not that $0$ is a factor of $q$. To have $0$ be a factor of $q$ we need $0\cdot factor = q$ and that can never happen..... I think what you mean to say is that as $0\cdot q=0$ and $1\cdot q = q$ then $q$ is a common factor of $0$ and $q$. (Not that $0$ and $q$ are both common factors of anything.) $\endgroup$
    – fleablood
    Jan 10, 2021 at 6:26

1 Answer 1

2
$\begingroup$

If we replace "$p,q$ are relatively prime" with "$\frac pq$ is in 'lowest term'" would it change how you think of it?

If $q > 1$ then $\frac 0q = \frac 01$ so $\frac 0q$ is not in lowest terms.

If we use the notation of $\gcd$ and "relative prime" though the arguement is the same.

As $0\cdot q = 0$ we have the $q$ is a divisor of $0$ and so $\gcd(0, q) = q$ and if $q > 1$ then $\gcd(0,q) = q$ and therefore

If $q>1$ then $0$ and $q$ are not relatively prime.

But $\gcd(0,1) = 1$ so

$0$ and $1$ are relatively prime.

And we can just continue.

====

But in your analysis you got confused and made a convolution.

You say:

But 0⋅0=0 and 0⋅q=0, so both p and q have a common factor of 0.

Not quite. we have $0\cdot q =0$. You do not have $0\cdot something = q$. So $0$ is NOT a factor of $q$. So $0$ is not a factor of anything except of itself.

What you do have and should have said is because $0\cdot q = 0$ and $1\cdot q = q$ that it is $q$ (and not $0$) that is a common factor of $0$ and $q$.

In fact every thing is a factor of $0$ so $\gcd(0,anything) = |anything|$. (Bear in mind $\gcd(a,b) = \gcd(a,-b) = \gcd(-a, b)=\gcd(-a, -b)$ because if anything divides both $a$ and $b$ it also divides $-a$ and $-b$.)

And $0$ and $q$ are relatively prime means $\gcd(0, q) = 1$. But $\gcd(0, q) = |q|$ so to have $0$ and $q$ relatively prime we must have $q = \pm 1$.

....

oh, I should point out, as Prasun Biswas correct me, that when we define $\gcd(a,b)$ and the "greatest" common divisor, most texts don't necessarily mean "greatest" in magnitude, but "greatest" in divisibility. We define $a\preceq b$ to mean that $a$ divides $b$ and that is a partial order (not total, not any two elements compare). Using this order the "greatest" common divisor is the common divisor that all other common divisor divide into.

For the most part the definition are the same as if $a,b$ are both positive $a\preceq b \implies a \le b$. And if $a,b$ are positive integers the largest common divisor in magnitude and the common divisor greatest in divisibility are the same.

But in this case as everything divides $0$, we always have $q\preceq 0$ and $\max_{\preceq} \mathbb Z = 0$ and $0$ is the greater in divisibility than all integers. So although all $q$ are common divisors of $0$ and $0$, $\gcd(0,0) = 0$.

$\endgroup$
2
  • 1
    $\begingroup$ Regarding your last paragraph, $\gcd(0,0)$ can be given a value depending on how you define the order on the integers; if you think of the integers ordered by the partial order of divisibility, ie, we define $a\leq b$ iff $a$ divides $b$, then $0$ is the maximal element under this order since every number divides $0$, so $\gcd(0,0)=0$; cf. math.stackexchange.com/a/495125/215900 and math.stackexchange.com/a/495457/215900 $\endgroup$ Jan 10, 2021 at 8:14
  • $\begingroup$ Good point. In fact that is certainly the more pertinent meaning of gcd as the (non-negative) common divisors all other common divisors divide, rather than the common divisor that is has the rather irrelevent property of being largest. As such, you are correct. $\endgroup$
    – fleablood
    Jan 10, 2021 at 16:30

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.