Maybe you need to go more basic than Bézout's identity: every integer can be expressed as the product of two integers in at least one way. Though of course, for the primes, one of those two integers is a unit.
Then $m = st$ and $n = uv$, where $s, t, u, v$ are also integers. If $\gcd(a, m) > 1$, this means that $a$ must share a prime factor with $s$ or $t$.
For example, let's say $a = 14$, $m = 91$ and $n = 19$. We find that $\gcd(14, 1729) = 7$. Then we verify that $14 = 2 \times 7$ and $91 = 7 \times 13$.
Let's say that $a = 15$ instead, $m$ and $n$ remain the same. We find that $\gcd(15, 1729) = 1$ and also $\gcd(15, 91) = 1$ and $\gcd(15, 19) = 1$. Clearly 15 is not divisible by either 7 or 13. Quite obviously 15 is divisible by 1 (and also by $-1$ for that matter), but that's trivial. The important thing is that 15 is not divisible by 19, nor by $-19$.