Question: Let $m, n, k \in \mathbb{Z}$ with $\operatorname{gcd}(m, n) = 1 = \operatorname{gcd}(n, k)$

Determine if it is true that necessarily $\operatorname{gcd}(m, k) = 1$.

Answer: The statement is FALSE.

Proof : [By Contradiction]

Let $m=3, n=5, k=6$.

The $\operatorname{gcd}(3,5)=1=\operatorname{gcd}(5,6)$ , then the $\operatorname{gcd}(3,6)\neq1$ .

Hence, the statement is FALSE.

  • 1
    $\begingroup$ Your proof is ok. You could even set $k=m$ ! $\endgroup$ – Evariste Aug 23 '16 at 11:32
  • $\begingroup$ It's not exactly a proof by contraduction (= reductio ad absurdum). It's only a counter-example (which is well enough, anyway). $\endgroup$ – Bernard Aug 23 '16 at 11:42

Your proof is correct. Another example would be $m=k=2$ and $n=1$.


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.