CAT 2025

Slot 2

QA

Question & Solution

1. Concept Used

• Topic: Number Systems — Divisors and Modular Arithmetic
• Formula: $$\text{Any divisor of } 2^6 \cdot 3^5 \cdot 5^3 \cdot 7^2 \text{ has the form } 2^a \cdot 3^b \cdot 5^c \cdot 7^d, \text{ where } 0 \le a \le 6,\ 0 \le b \le 5,\ 0 \le c \le 3,\ 0 \le d \le 2$$

---

2. Calculation

We need divisors of the form $3r + 1$, i.e., divisors that are $\equiv 1 \pmod{3}$.

Step 1: Eliminate multiples of 3.

A divisor $2^a \cdot 3^b \cdot 5^c \cdot 7^d$ is divisible by 3 whenever $b \ge 1$. But a number $\equiv 1 \pmod{3}$ cannot be divisible by 3. Hence we must have $b = 0$. This fixes $b$ to exactly 1 choice.

Step 2: Analyze residues modulo 3.

With $b = 0$, the divisor reduces to $2^a \cdot 5^c \cdot 7^d$. Now we compute each base modulo 3:

$$2 \equiv 2 \pmod{3}, \quad 5 \equiv 2 \pmod{3}, \quad 7 \equiv 1 \pmod{3}$$

Therefore:

$$2^a \cdot 5^c \cdot 7^d \equiv 2^a \cdot 2^c \cdot 1^d \equiv 2^{a+c} \pmod{3}$$

Step 3: Determine when $2^{a+c} \equiv 1 \pmod{3}$.

Note that $2^1 \equiv 2$, $2^2 \equiv 1$, $2^3 \equiv 2$, $2^4 \equiv 1$, ... The pattern repeats with period 2:

$$2^k \equiv 1 \pmod{3} \iff k \text{ is even}$$

So we need $a + c$ to be even.

Step 4: Count valid pairs $(a, c)$ where $a + c$ is even.

For $a \in {0, 1, 2, 3, 4, 5, 6}$: even values are ${0, 2, 4, 6}$ → 4 even, odd values are ${1, 3, 5}$ → 3 odd.

For $c \in {0, 1, 2, 3}$: even values are ${0, 2}$ → 2 even, odd values are ${1, 3}$ → 2 odd.

For $a + c$ to be even, both must be even OR both must be odd:

$$\text{(both even)} + \text{(both odd)} = (4 \times 2) + (3 \times 2) = 8 + 6 = 14 \text{ pairs}$$

Step 5: Count choices for $d$.

Since $7^d \equiv 1^d \equiv 1 \pmod{3}$ for any $d$, the value of $d$ does not affect the residue. So $d$ can be $0, 1,$ or $2$ — giving 3 choices.

Step 6: Compute total count.

$$\text{Total} = 14 \times 3 = 42$$

---

3. Solution

Answer = Option 4 ✅

The total number of divisors of $2^6 \cdot 3^5 \cdot 5^3 \cdot 7^2$ that are of the form $3r + 1$ is 42.