¿Es el máximo común divisor inyectivo? ¿Es biyectiva?

Question

En una hoja de examen, había las siguientes preguntas:

1. ¿Es gcd una función inyectiva?

2. ¿Es gcd una función biyectiva?

Encontré estas preguntas impar porque pensé que necesitamos conocer primero el dominio y el codominio de una función antes de poder decidir si es inyectiva o biyectiva. La pregunta no especificaba cuál era el dominio y el codominio.

Dado que todos los enteros dividen a 0 (excepto el propio 0), entonces gcd(0, 0) sería indefinido ya que no hay ningún entero "mayor" que divida a 0 y a 0. Por lo tanto, parece razonable excluir el 0 del dominio.

Además, como el 0 no divide ningún número, es imposible que el 0 sea el gcd de dos enteros cualesquiera a y b, por lo que el 0 debe ser excluido del codominio.

Ahora, supongamos que tanto el dominio como el codominio son el conjunto de todos los números naturales positivos. ¿Sería válido este dominio? Estoy confundido porque la función gcd contiene dos argumentos, es decir, a y b en gcd(a, b). Dado que este es el caso, ¿el dominio debería ser el producto cartesiano N*N?

Está claro que gcd es una función porque no es de uno a varios. Cada vez que realizamos gcd obtenemos exactamente una salida.

¿Es correcto afirmar que gcd no es una función inyectiva porque asigna dos números naturales a y b a un único resultado c, es decir, gcd(a, b) = c, por lo que es de muchos a uno? ¿O la razón correcta debería ser que gcd no es inyectiva porque más de un par de números puede tener el mismo gcd, por lo que no hay una correspondencia unívoca estricta entre el dominio y el codominio? Por ejemplo, gcd(2, 4) = 2 y gcd(2, 8) = 2.

Además, ¿es correcto afirmar que gcd es una función suryectiva porque cada elemento del codominio es el gcd de un par de números naturales positivos, es decir, cada elemento del codominio es mapeado por al menos un elemento del dominio? He llegado a esta conclusión porque cada número natural positivo k puede expresarse como k = gcd(k, k). Por favor, corrígeme si me equivoco.

Answer 1

Tiene usted toda la razón en que la pregunta no es precisa. Hay varias maneras de formalizar la pregunta; has hecho un buen comienzo pero déjame continuar un poco ya que hay algunos trozos que no son correctos.

Como bien dices para hablar del gcd de forma sensata y no trivial se necesitan dos enteros (o aún más).

La siguiente sería una pregunta precisa:

Considere $$\gcd: \begin{cases} \mathbb{N}\times \mathbb{N} & \to \mathbb{N} \\ (a,b) & \mapsto \gcd(a,b) \end{cases}$$ ¿Esto es inyectable? ¿Es biyectiva?

La respuesta es "no", ya que por ejemplo $\gcd(3,6)= \gcd(3,9)$ .

Sin embargo, para:

¿Es correcto afirmar que gcd no es una función inyectiva porque mapea dos números naturales a y b a un único resultado c

Esto no es correcto a mi entender.

$$ \begin{cases} \mathbb{N}\times \mathbb{N} & \to \mathbb{N} \\ (a,b) & \mapsto 2^a3^b\end{cases}$$ mapea dos números a una sola salida, pero sigue siendo inyectiva.

Un mapa no es inyectivo si asigna dos elementos distintos del dominio al mismo elemento del codominio. En este caso, el dominio son los pares de números naturales, $(a,b)$ es un elemento del dominio asignado a $\gcd(a,b)$ un elemento del codominio.

La razón por la que no es inyectiva es que hay parejas distintas de enteros $(a,b)\neq (c,d)$ tal que $\gcd(a,b)= \gcd(c,d)$ .

--

Observación adicional: lo que dice sobre $\gcd$ con $0$ no es la forma en que las cosas se manejan comúnmente. Todo número natural divide $0$ , por lo que tenemos que $\gcd(a,0)= a$ para cada $a$ ; y nosotros típicamente uno dice $\gcd(0,0)=0$ (el "mayor" se entiende con respecto al orden dado sea la divisibilidad).

Answer 2

Lo has pensado muy bien. La función del máximo común divisor es efectivamente una función $\gcd: \mathbb N \times \mathbb N \to \mathbb N,\,$ donde $\mathbb N$ se toma aquí como el conjunto de enteros positivos (excluyendo el cero por las razones que das). De esta manera, podemos denotar la función por su entrada y salida:

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

Es no inyectiva, por la segunda razón que das: p. ej. $\gcd(2, 3) = \gcd(3, 4) = 1$ pero $(2, 3) \neq (3, 4)$ .

Es una función suryectiva, y usted proporciona una razón sucinta de por qué es así.