Proofs involving strictly multiplication, division and $\gcd$ of the integers are often very naturally thought of by using the fundamental theorem of arithmetic, leading to an alternate representation of the numbers: ordered tuples of their prime exponents.
For example, $21 = 3 \times 7$. If we look at the infinite ordered list of primes, we can also see that $21 = 2^0 \times 3^1 \times 5^0 \times 7^1 \times \dots$. So it's ordered tuple representation of its prime exponents would be $(0, 1, 0, 1, 0, \dots)$.
Now the operations are very simple:
- $a\times b$: simply add the exponents pairwise. We have $3 \times 5 = (0, 1, 0, \dots) + (0, 0, 1,\dots) = (0, 1, 1, \dots).$
- $a \div b$: simply subtract the exponents pairwise. If for some pair you'd get a negative number, it means that $a$ is not divisible by $b$.
$\gcd(a, b)$: take the minimum of the exponents pairwise. For example for $12$ and $18$ we'd get:
$\min((2, 1, 0, \dots), (1, 2, 0, \dots)) = (1, 1, 0, \dots) = 6$
In this context the problem is really easy to prove:
The problem says that if $c$ divides $ab$ and $\gcd(b,c)=1$, then prove that $c$ divides $a$. $gcd(a,c)=?$
Let $a_i, b_i, c_i$ respectively be the $i$th prime exponent of $a, b, c$. Then $c \mid ab$ tells us $c_i \leq a_i + b_i$ and $\gcd(b, c) = 1$ tells us $\min(b_i, c_i) = 0$. This allows us to substitute $c_i$ for $b_i + c_i$ in our first equation, giving $b_i + c_i \leq a_i + b_i \Rightarrow c_i \leq a_i$. That tells us $c \mid a$. It also tells us $\min(c_i, a_i) = c_i$, thus $\gcd(a, c) = c$.