Relatively Prime Integers 
If $m$ and $n$ are relatively prime and $k\mid m$, show that $k$ and $n$ are also relatively prime.

I haven't really any idea where to start with this. I have that if k|m then m=km' but I'm not really sure where to go after that. Thanks!
 A: There are already some good answers here. I'll try something basic.
Since $m$ and $n$ are relatively prime, $\gcd(m,n) = 1.$ Since $k \mid m$, $m = rk, \exists r \in \mathbb{Z}$. But then we can just write $\gcd(rk, n) = 1$.
This implies $\gcd(k, n) = 1.$ You can see this by contradiction.
A: since $m$ and $n$ are relatively prime so there're two integers $p,q$ such that $pm+nq=1$ now as $k$ divides $m$ so $m=dk$ for some $d$ thus having $k(dp)+nq=1$. hence the conclusion
FYI: two numbers $m,n$ are relatively prime if and only if there exist two integers $p,q$ such that $mp+nq=1$
A: Suppose they are not. Then $\exists d \in \mathbb{N}$ such that $\gcd{(k,n)}=d \ (d \neq 1)$. Then, $d \mid m$ as $k \mid m$. It also divides $n$. So, $d$ is a common divisor of $m$ and $n$. That's a contradiction as $m$ and $n$ are supposed to be relatively prime. Thus, our assumption was wrong. Which means, $k$ and $n$ are relatively prime.
A: Since the integers are a Principal Ideal Domain, we have a Bézout identity and can write $am+bn=1$ for some $a,b \in \mathbb{Z}$. Since $k\, |\, m$, we have $atk+bn=1$ for some $t \in \mathbb{Z}$. Now suppose for contradiction that $gcd(k,n) \neq 1$. Then, clearly $gcd(k,n) \, | \, atk+bn$ and moreover $gcd(k,n) \, | \, 1$. Since $gcd(k,n)$ is an integer, this implies that $gcd(k,n)=1$, a contradiction. Hence, $gcd(k,n)=1$.
