Congruencia: ¿Cómo demostrar que un conjunto asume todos los valores?

Question

Encontré esta pregunta en un libro de matemáticas de la Olimpiada:

Dejemos que $\gcd(m,n) = 1$ , $A = \{x\mid0\le x \le m-1, \gcd(x,m) = 1\}$ y $B = \{x\mid0\le x \le n-1, \gcd(x,n) = 1\}$ . Si $C= \{na+mb \mid a \in A, b\in B\}$ entonces demuestre que $C$ asume todos los valores $ \equiv 0 \le x \le mn-1$ modulo $mn$ .

He demostrado con éxito que $\gcd (mn, na+mb) = 1$ para todos $a, b.$ Esto implicaría que $\forall c \in C, $ $0 \le c \le mn-1$ tomada en el módulo $mn$ .

Sin embargo, tengo dificultades para seguir adelante. Mi corazonada dice que tiene algo que ver con la función phi de Euler, ya que el número de elementos en $A$ y $B$ son respectivamente $\phi(m)$ y $\phi(n)$ y $C$ debe asumir $\phi(mn) \Rightarrow \phi(m) \phi(n)$ elementos.

¿Cómo puedo demostrar que esto es válido para todo ¿esos valores?

Answer 1

Tu corazonada está en la línea correcta.

Supongamos que dos elementos de $C$ eran equivalentes módulo a módulo $mn$ ; $$ a_1 n + b_1 m \equiv a_2 n + b_2 m \pmod{mn}. $$ Entonces $mn \mid (a_2 - a_1) n + (b_2 - b_1)m$ . Por lo tanto, el lado derecho es un múltiplo de $m$ Así que $m \mid (a_2 - a_1) n$ . Desde $\gcd(m,n) = 1$ Esto significa que $m \mid (a_2 - a_1)$ es decir $a_2 \equiv a_1 \pmod{m}$ . Desde $a_1$ y $a_2$ siendo de $A$ están entre 0 y $m-1$ si son equivalentes modulo $m$ son de hecho iguales.

De la misma manera, $b_2 = b_1$ .

Hemos demostrado que cualquier elección distinta de $a$ o $b$ producen elementos de $C$ que no son equivalentes módulo $mn$ . Dado que hay $\phi(m)$ opciones para $a$ y $\phi(n)$ opciones para $b$ Hay $\phi(m)\phi(n)$ elementos de $C$ , todos los cuales son distintos módulo $mn$ y todos ellos son relativamente primos para $mn$ .

Pero, como $m$ y $n$ son relativamente primos, $\phi(mn) = \phi(m)\phi(n)$ por lo que sólo hay esa cantidad de números naturales menores que $mn$ y relativamente primo a $mn$ . Así que $C$ contiene un elemento equivalente a cada uno.