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? 

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.
