TheCATExam
Sign in

CAT 2020 Slot 3 — QA Question 23

IndicesEasy

How many pairs (a, b) of positive integers are there such that a ≤ b and ab = 42017?

Answer & solution

  • A

    2019

  • B

    2017

  • C

    2020

  • 2018

Solution

Easy

Write the product as a power of 22. Every factor of a power of 22 is itself a power of 22, so write a=2x, b=2ya=2^x,\ b=2^y. The condition a≤ba\le b becomes x≤yx\le y, and counting valid exponents counts the pairs.

1

Rewrite the product. Convert 420174^{2017} to base 22.

ab=42017⇒ ab=(22)2017(4=22)⇒ ab=24034\begin{aligned} &ab = 4^{2017}\\ &\Rightarrow\ ab = \left(2^2\right)^{2017} \quad\text{(}4=2^2\text{)}\\ &\Rightarrow\ ab = 2^{4034} \end{aligned}
2

Both factors are powers of 22. Since ab=24034ab=2^{4034} has only the prime 22, each of aa and bb must be a power of 22. Let a=2xa=2^x, b=2yb=2^y with x,yx,y non-negative integers.

2x⋅2y=24034⇒ x+y=4034(equate exponents)\begin{aligned} &2^x\cdot 2^y = 2^{4034}\\ &\Rightarrow\ x+y = 4034 \quad\text{(equate exponents)} \end{aligned}
3

Apply a≤ba\le b. The condition a≤ba\le b is equivalent to x≤yx\le y. Combined with x+y=4034x+y=4034, this bounds xx from above.

x≤y  ⟺  x≤x+y2⇒ x≤40342(from step 2)⇒ x≤2017\begin{aligned} &x\le y \;\Longleftrightarrow\; x\le \tfrac{x+y}{2}\\ &\Rightarrow\ x\le \tfrac{4034}{2} \quad\text{(from step 2)}\\ &\Rightarrow\ x\le 2017 \end{aligned}
4

Count the exponents. Each integer xx in {0,1,2,…,2017}\{0,1,2,\dots,2017\} gives one valid pair (and y=4034−xy=4034-x is then determined and ≥x\ge x).

count=2017−0+1⇒ count=2018\begin{aligned} &\text{count} = 2017 - 0 + 1\\ &\Rightarrow\ \text{count} = 2018 \end{aligned}
2018\boxed{2018}
CAT 2020 Slot 3 QA Q23: How many pairs (a, b) of positive integers are there such that a ≤ b and ab = 4 2017 ? — Solution | TheCATExam