Las pruebas que implican estrictamente la multiplicación, la división y la $\gcd$ de los enteros son a menudo muy naturalmente el pensamiento de utilizando el teorema fundamental de la aritmética, que conduce a un suplente en representación de los números: ordenado tuplas de sus principales exponentes.
Por ejemplo, $21 = 3 \times 7$. Si nos fijamos en la infinita lista ordenada de números primos, también podemos ver que $21 = 2^0 \times 3^1 \times 5^0 \times 7^1 \times \dots$. Así que ordenó tupla representación de sus principales exponentes serían $(0, 1, 0, 1, 0, \dots)$.
Ahora las operaciones son muy sencillas:
- $a\times b$: simplemente sumar los exponentes de a pares. Tenemos $3 \times 5 = (0, 1, 0, \dots) + (0, 0, 1,\dots) = (0, 1, 1, \dots).$
- $a \div b$: basta con restar los exponentes de a pares. Si por alguna par te gustaría obtener un número negativo, significa que el $a$ no es divisible por $b$.
$\gcd(a, b)$: tener el mínimo de los exponentes de a pares. Por ejemplo, para $12$ $18$ obtendríamos:
$\min((2, 1, 0, \dots), (1, 2, 0, \dots)) = (1, 1, 0, \dots) = 6$
En este contexto, el problema es realmente fácil de probar:
El problema dice que si $c$ divide $ab$$\gcd(b,c)=1$, luego de demostrar que $c$ divide $a$. $gcd(a,c)=?$
Deje $a_i, b_i, c_i$, respectivamente, de ser el $i$th el primer exponente de $a, b, c$. A continuación, $c \mid ab$ nos dice $c_i \leq a_i + b_i$ $\gcd(b, c) = 1$ nos dice $\min(b_i, c_i) = 0$. Esto nos permite sustituto $c_i$ $b_i + c_i$ en nuestra primera ecuación, dando a $b_i + c_i \leq a_i + b_i \Rightarrow c_i \leq a_i$. Que nos dice $c \mid a$. También nos dice $\min(c_i, a_i) = c_i$, lo $\gcd(a, c) = c$.
