Proof about relatively prime numbers. 
Let $a,m,n, \in \mathbb{N}$. I want to show that if $a$ and $mn$ are relatively prime, then $a$ and $m$ are relatively prime.

To start us off, To say $a$ and $mn$ are relatively prime means that gcd($a,mn) = 1.$ I've tried using Bezout's Identity, but have not gotten anywhere. Also, can we assume that $a$ and $n$ are relatively prime? 
 A: Try the contrapositive: If $a$ and $m$ are not relatively prime, then $d=\gcd(a,m)>1$ and clearly $d$ divides both $a$ and $mn$, so $\gcd(a,mn)\ge d > 1$, and thus $a$ and $mn$ are not relatively prime.  
Since Not B implies Not A is logically equivalent to A implies B, you are done.
A: 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$.
