I am looking for even integers $n$ and $k$ such that $k$ does not divide $n$ and $\gcd(n,k) = 3$. Is this possible?

With the help of some online tools I tried, but every time I am not getting the desired result. Kindly help.

  • $\begingroup$ @Mark: $9$ is not much even, is it ? $\endgroup$ – Yves Daoust Apr 21 at 8:47
  • $\begingroup$ Yeah, didn't read the question well. Nevermind then. $\endgroup$ – Mark Apr 21 at 8:48
  • 1
    $\begingroup$ It is a little weird that you needed online tools. And after just a few attempts, you should have understood why this is impossible. $\endgroup$ – Yves Daoust Apr 21 at 8:49
  • $\begingroup$ @YvesDaoust I was just trying to cross check. That's why. $\endgroup$ – monalisa Apr 21 at 8:52
  • 1
    $\begingroup$ Please edit the question to tell us what results you already know, e.g. do you know any of the named theorems in my answer? (If you don't add such context then some users may close and delete the question, so the answers will be lost). $\endgroup$ – Bill Dubuque Apr 21 at 15:58

Even numbers are all multiples of $2$, hence the $\text{gcd}$ is perforce even.

  • $\begingroup$ One should justify why that inference holds given that nature of the question. $\endgroup$ – Bill Dubuque Apr 21 at 15:03

The greatest common divisor of even integers is even. Though this follows easily from deeper GCD properties it also has a simple direct proof. Suppose $c$ is an odd common divisor of $2a$ and $2b$. By the Lemma below we infer that $2c$ is also a common divisor, so $c$ is not the greatest common divisor.

Lemma $\ $ Suppose that an odd integer $\,c\,$ divides $\,2k$. Then if follows that $\,2c$ divides $2k$

Proof $\ $ By hypothesis $\,nc = 2k.\,$ So $\,nc\,$ even, $c$ odd $\,\Rightarrow\, n$ even, so $\,(n/2)\, 2c = 2k$

Remark $ $ Alternatively it follows immediately from basic GCD properties (assuming they are known).

By the GCD Universal Property $\ \ d\mid n,k\iff d\mid\gcd(n,k),\ $ Put $\, d = 2.\ \ $

By the GCD Distributive Law $\ \gcd(2a,2b) = 2\gcd(a,b)\,$ is even.

By the GCD Bezout Identity $\ \ \ \gcd(2a,2b) = j(2a)+k(2b) = 2(ja+kb)$

The Bezout-based proof is less general than the prior two proofs since it need not hold in domains where gcds exist, e.g. in polynomial rings such as $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y].$


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.