In an examination paper, there were the following questions:
Is gcd an injective function?
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!