TheCATExam
Sign in

CAT 2023 Slot 2 — QA Question 1

DivisibilityEasy

For any natural numbers m, n and k, such that k divides both m + 2n and 3m + 4n, k must be a common divisor of

Answer & solution

  • A

    m and n

  • m and 2n

  • C

    2m and 3n

  • D

    2m and n

Solution

Easy

If kk divides two expressions, it divides every integer combination of them. Take clean combinations of m+2nm+2n and 3m+4n3m+4n to isolate mm and a multiple of nn — whatever survives, kk must divide.

1

Write the two divisibility facts using integer multiples a,ba,b:

k∣(m+2n) ⇒ m+2n=akk∣(3m+4n) ⇒ 3m+4n=bk\begin{aligned} &k\mid (m+2n)\ \Rightarrow\ m+2n=ak\\ &k\mid (3m+4n)\ \Rightarrow\ 3m+4n=bk \end{aligned}
2

Combine to isolate nn: compute 3×(first)−(second)3\times(\text{first})-(\text{second}):

3(m+2n)−(3m+4n)=3ak−bk⇒ 2n=(3a−b)k⇒ k∣2n\begin{aligned} &3(m+2n)-(3m+4n)=3ak-bk\\ &\Rightarrow\ 2n=(3a-b)k\\ &\Rightarrow\ k\mid 2n \end{aligned}
3

Combine to isolate mm: compute (second)−2×(first)(\text{second})-2\times(\text{first}):

(3m+4n)−2(m+2n)=bk−2ak⇒ m=(b−2a)k⇒ k∣m\begin{aligned} &(3m+4n)-2(m+2n)=bk-2ak\\ &\Rightarrow\ m=(b-2a)k\\ &\Rightarrow\ k\mid m \end{aligned}
4

So kk is guaranteed to divide both mm and 2n2n. (It need not divide nn alone — only 2n2n.)

mm and 2n2n — option (b).

Eliminate by plugging numbers: m=1,n=1m=1,n=1 gives m+2n=3m+2n=3, 3m+4n=73m+4n=7, so k=1k=1 — useless. Try m=2,n=2m=2,n=2: m+2n=6m+2n=6, 3m+4n=143m+4n=14, gcd⁡=2=k\gcd=2=k. Here k=2k=2 divides m=2m=2 and 2n=42n=4 but not n=1n=1 in the first try — so any option containing a bare nn fails, leaving (b).

CAT 2023 Slot 2 QA Q1: For any natural numbers m, n and k, such that k divides both m + 2n and 3m + 4n, k must be a common divisor of — Solution | TheCATExam