CATSprint

CAT 2025Slot 2QAQues & Sol

Number SystemsMedium

Question

The number of divisors of $(2^{6}\times 3^{5}\times 5^{3}\times 7^{2})$, which are of the form $(3r+1)$, where r is a non-negative integer, is

Options

Solution

1. Concept Used

  • Topic: Number Systems — Divisors and Modular Arithmetic
  • Formula: Every divisor takes the form $$2^a \cdot 3^b \cdot 5^c \cdot 7^d \equiv 1 \pmod{3}$$ where $0 \le a \le 6$, $0 \le b \le 5$, $0 \le c \le 3$, $0 \le d \le 2$.

2. Calculation

Every divisor of $$2^6 \cdot 3^5 \cdot 5^3 \cdot 7^2$$ takes the form $2^a \cdot 3^b \cdot 5^c \cdot 7^d$ where $0 \le a \le 6$, $0 \le b \le 5$, $0 \le c \le 3$, $0 \le d \le 2$. We need to count only those divisors that satisfy $$2^a \cdot 3^b \cdot 5^c \cdot 7^d \equiv 1 \pmod{3}.$$

A number that is $\equiv 1 \pmod{3}$ cannot be divisible by 3. Since $3^b$ introduces a factor of 3 whenever $b \ge 1$, we must fix $b = 0$. This gives exactly 1 choice for $b$.

With $b = 0$, the divisor reduces to $2^a \cdot 5^c \cdot 7^d$. Now observe the residues of 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}.$$

Since powers of 2 cycle modulo 3 as $$2^1 \equiv 2,\ 2^2 \equiv 1,\ 2^3 \equiv 2,\ 2^4 \equiv 1, \ldots$$ we have $2^k \equiv 1 \pmod{3}$ if and only if $k$ is even. So the condition becomes: $$a + c \equiv 0 \pmod{2}, \text{ i.e., } a + c \text{ must be even.}$$

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

For $a + c$ to be even, either both $a$ and $c$ are even, or both are odd: $$\text{(both even)} + \text{(both odd)} = (4 \times 2) + (3 \times 2) = 8 + 6 = 14 \text{ valid pairs.}$$

Since $7^d \equiv 1^d \equiv 1 \pmod{3}$ for any value of $d$, the exponent $d$ does not affect the residue condition at all. So $d$ can freely range over ${0, 1, 2}$, giving 3 choices.

The total count of valid divisors is therefore: $$\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.