1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ A common divisor of $k$ and $n$ is a common divisor of ......... and $n$. $\endgroup$ – user296602 Feb 16 '16 at 4:35
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Will Byrne Feb 16 '16 at 4:59
  • $\begingroup$ for the gcd being 1 the condition is if and only if $\endgroup$ – user300 Feb 16 '16 at 5:25
  • $\begingroup$ Ok cool, anywhere where I could look up that proof? $\endgroup$ – Will Byrne Feb 16 '16 at 5:40
  • $\begingroup$ 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. $\endgroup$ – user300 Feb 16 '16 at 5:48
  • $\begingroup$ That makes sense. It's essentially the same argument I used below. Thanks! $\endgroup$ – Will Byrne Feb 16 '16 at 6:08
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.