4
$\begingroup$

In an examination paper, there were the following questions:

  1. Is gcd an injective function?

  2. Is gcd a bijective function?

I found these questions odd because I thought that we need to first know the domain and codomain of a function before we can decide whether it is injective or bijective. The question did not specify what was the domain and codomain.

Since every integer divides 0 (except 0 itself), then gcd(0, 0) would be undefined as there is no "greatest" integer that divides 0 and 0. Hence, it seems reasonable to exclude 0 from the domain.

Also, since 0 does not divide any number, it is impossible for 0 to be the gcd of any two integers a and b, so 0 should be excluded from the codomain.

Now, suppose we let both the domain and codomain be the set of all positive natural numbers. Would this domain be valid? I am confused because the gcd function contains two arguments, i.e. a and b in gcd(a, b). Since this is the case, should the domain instead be the cartesian product N*N?

Clearly gcd is a function because it is not one-to-many. Every time we perform gcd we get exactly one output.

Is it correct to claim that gcd is not an injective function because it maps two natural numbers a and b to a single output c, i.e. gcd(a, b) = c, hence it is many-to-one? Or should the correct reason be that gcd is not injective because more than one pair of numbers can have the same gcd, hence there is no strict one-one correspondence between the domain and the codomain? For example, gcd(2, 4) = 2 and gcd(2, 8) = 2.

Also, is it correct to claim that gcd is a surjective function because every element in the codomain is the gcd of a pair of positive natural numbers, i.e. every element in the codomain is mapped to by at least one element in the domain? I came to this conclusion because every positive natural number k can be expressed as k = gcd(k, k). Please correct me if I am wrong!

$\endgroup$
  • $\begingroup$ I only skimmed through your question, but you seem to be perfectly aware of what's going on except for the injectivity of $\gcd$. In the penultimate paragraph the second fact is the reason why it isn't injective. $\endgroup$ – Git Gud Nov 8 '14 at 12:57
  • $\begingroup$ Thank you for your reply. Given that gcd is a function with two arguments, should the domain be the cartesian product N*N, where N is the set of all positive natural numbers? Or should the domain just be N? $\endgroup$ – Vizuna Nov 8 '14 at 13:02
  • $\begingroup$ Actually it is much more natural to allow $0$. We have $\gcd(a, 0) = a$ for all $a$, and in particular $\gcd(0, 0) = 0$. You have to interpret "greatest" common divisor in a way such that $0$ is the largest of all numbers. $\endgroup$ – 6005 Jan 7 '15 at 17:22
5
$\begingroup$

You are completely correct that the question is not precise. There are several ways to formalize the question; you made a good start but let me continue a bit as there are some bits that are not correct.

As you say correctly for speaking about the gcd in a sensible way and nontrivial way one needs two integers (or still more).

The following would be a precise question:

Consider $$\gcd: \begin{cases} \mathbb{N}\times \mathbb{N} & \to \mathbb{N} \\ (a,b) & \mapsto \gcd(a,b) \end{cases}$$ Is this injective? Is this bijective?

The answer being "no" as for example $\gcd(3,6)= \gcd(3,9)$.

Howver for:

Is it correct to claim that gcd is not an injective function because it maps two natural numbers a and b to a single output c

This is not correct in the way I understand it.

$$ \begin{cases} \mathbb{N}\times \mathbb{N} & \to \mathbb{N} \\ (a,b) & \mapsto 2^a3^b\end{cases}$$ maps two number to a single output, but it is still injective.

A map is not injective if it maps two distinct elements from the domain to the same element of the codomain. In this case the domain is pairs of natural numbers so, $(a,b)$ is one element of the domain mapped to $\gcd(a,b)$ one element of the codomain.

The reason it is not injective is that there are distinct couples of integers $(a,b)\neq (c,d)$ such that $\gcd(a,b)= \gcd(c,d)$.

--

Additional remark: what you say about $\gcd$ involving $0$ is not the way things are commonly handled. Every natural number divides $0$, so we have that $\gcd(a,0)= a$ for each $a$; and we typically one says $\gcd(0,0)=0$ (the "greatest" is understood with respect to the order given be divisibility).

$\endgroup$
  • $\begingroup$ Great answer. Thanks! $\endgroup$ – Vizuna Nov 8 '14 at 13:17
  • $\begingroup$ Glad you liked it! :-) $\endgroup$ – quid Nov 8 '14 at 13:18
3
$\begingroup$

You've thought it out quite well. The greatest common divisor function is indeed a function $\gcd: \mathbb N \times \mathbb N \to \mathbb N,\,$ where $\mathbb N$ is taken here to be the set of positive integers (excluding zero for the reasons you give). In this way, we can denote the function by its input and output:

$$(a, b) \in \mathbb N\times \mathbb N \quad \mapsto \quad \gcd(a, b)\in \mathbb N$$

It is non-injective, for the second reason you give: e.g. $\gcd(2, 3) = \gcd(3, 4) = 1$, but $(2, 3) \neq (3, 4)$.

It IS a surjective function, and you provide a succinct reason as to why this is the case.

$\endgroup$
  • $\begingroup$ You're welcome, Vizuna! $\endgroup$ – Namaste Nov 8 '14 at 13:16

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.