# 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 common divisor of $k$ and $n$ is a common divisor of ......... and $n$. – user296602 Feb 16 '16 at 4:35

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.

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$

• Hmmm, just because you have a pair $p,q$ satisfying such an equality, does that really ensure that such a pair is satisfying the Bézout identity? It seems to me that this doesn't ensure that $1$ is the gcd. – Will Byrne Feb 16 '16 at 4:59
• for the gcd being 1 the condition is if and only if – user300 Feb 16 '16 at 5:25
• Ok cool, anywhere where I could look up that proof? – Will Byrne Feb 16 '16 at 5:40
• let there be two integers $p,q$ satisfying $mp+nq=1$ then if $d$ is gcd of $m,n$ then it divides both $m,n$ hence divides $1$ so $d=1$ . other way is obvious. – user300 Feb 16 '16 at 5:48
• That makes sense. It's essentially the same argument I used below. Thanks! – Will Byrne Feb 16 '16 at 6:08

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.

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$.