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:

• A. \(42\)
• B. \(36\)
• C. \(56\)
• D. \(24\)

Hint:

When counting divisors with a condition like “of the form $3r+1$”, work modulo 3: \begin{itemize} \item Express each prime factor modulo 3. \item Eliminate exponents that force the divisor to be 0 mod 3. \item Use parity or congruence conditions on exponents to match the required remainder. \end{itemize}

Answer 1

The Correct Option is A

Let \[ N = 2^6 \times 3^5 \times 5^3 \times 7^2. \] Any divisor \(D\) of \(N\) can be written as \[ D = 2^a \cdot 3^b \cdot 5^c \cdot 7^d, \] where \[ 0 \le a \le 6,\quad 0 \le b \le 5,\quad 0 \le c \le 3,\quad 0 \le d \le 2. \] We are required to count those divisors for which \[ D \equiv 1 \pmod{3}. \] Step 1: Reduce prime bases modulo \(3\). Evaluating each prime factor modulo \(3\), \[ 2 \equiv -1 \pmod{3}, \quad 3 \equiv 0 \pmod{3}, \quad 5 \equiv -1 \pmod{3}, \quad 7 \equiv 1 \pmod{3}. \] Hence, \[ D \equiv (-1)^a \cdot 0^b \cdot (-1)^c \cdot 1^d \pmod{3}. \] Step 2: Restrict the exponent of \(3\). If \(b \ge 1\), then \(3^b \equiv 0 \pmod{3}\), which gives \[ D \equiv 0 \pmod{3}, \] and such a divisor cannot be congruent to \(1 \pmod{3}\). Therefore, \[ b = 0. \] With \(b = 0\), the congruence becomes \[ D \equiv (-1)^{a+c} \pmod{3}. \] For this to be congruent to \(1 \pmod{3}\), the exponent \(a+c\) must be even. Step 3: Count valid combinations of \(a\) and \(c\). For \(a\) in the range \(0 \le a \le 6\): \[ \text{even values: } 0,2,4,6 \Rightarrow 4 \text{ choices}, \quad \text{odd values: } 1,3,5 \Rightarrow 3 \text{ choices}. \] For \(c\) in the range \(0 \le c \le 3\): \[ \text{even values: } 0,2 \Rightarrow 2 \text{ choices}, \quad \text{odd values: } 1,3 \Rightarrow 2 \text{ choices}. \] The condition \(a+c\) even requires both exponents to have the same parity. \[ \text{Both even: } 4 \times 2 = 8 \text{ ways}, \] \[ \text{Both odd: } 3 \times 2 = 6 \text{ ways}. \] Thus, the total number of valid \((a,c)\) pairs is \[ 8 + 6 = 14. \] Step 4: Count choices for \(d\). Since \(7 \equiv 1 \pmod{3}\), we have \[ 7^d \equiv 1 \pmod{3} \] for all allowed values of \(d\). Hence, \[ d = 0,1,2 \Rightarrow 3 \text{ choices}. \] Step 5: Compute the total number of required divisors. Combining all valid choices, \[ \text{Total} = (1 \text{ choice for } b) \times (14 \text{ choices for } a,c) \times (3 \text{ choices for } d). \] Therefore, the number of divisors of \(N\) of the form \(3r + 1\) is \[ 1 \times 14 \times 3 = 42. \] Hence, the required number of such divisors is \[ 42. \]

Answer 2

Let \[ N = 2^6 \times 3^5 \times 5^3 \times 7^2. \] Any divisor \(D\) of \(N\) is of the form \[ D = 2^a \cdot 3^b \cdot 5^c \cdot 7^d, \] where \[ 0 \le a \le 6,\quad 0 \le b \le 5,\quad 0 \le c \le 3,\quad 0 \le d \le 2. \] We want divisors of the form \(3r+1\), i.e. \[ D \equiv 1 \pmod{3}. \]
Step 1: Reduce each prime factor modulo 3. \[ 2 \equiv -1 \pmod{3},\quad 3 \equiv 0 \pmod{3},\quad 5 \equiv 2 \equiv -1 \pmod{3},\quad 7 \equiv 1 \pmod{3}. \] Thus, \[ D \equiv (-1)^a \cdot 0^b \cdot (-1)^c \cdot 1^d \pmod{3}. \] 
Step 2: Condition on exponent \(b\). If \(b \ge 1\), then \(3^b \equiv 0 \pmod{3}\), so \[ D \equiv 0 \pmod{3}, \] which cannot be congruent to 1 modulo 3. Hence we must have \[ b = 0 \quad \text{(only 1 choice)}. \] With \(b=0\), the modulus simplifies to \[ D \equiv (-1)^a \cdot (-1)^c \cdot 1^d = (-1)^{a+c} \pmod{3}. \] We need \[ (-1)^{a+c} \equiv 1 \pmod{3}, \] which means \(a+c\) must be even. 
Step 3: Count possibilities for \(a\) and \(c\). For \(a\) (\(0 \le a \le 6\)): - Even: \(0,2,4,6\) \(\Rightarrow 4\) values - Odd: \(1,3,5\) \(\Rightarrow 3\) values For \(c\) (\(0 \le c \le 3\)):
- Even: \(0,2\) \(\Rightarrow 2\) values
- Odd: \(1,3\) \(\Rightarrow 2\) values We need \(a\) and \(c\) to have the same parity.
Case 1: Both even. Number of ways: \[ 4 \times 2 = 8. \] \underline{Case 2: Both odd.} Number of ways: \[ 3 \times 2 = 6. \] Total valid \((a,c)\) pairs: \[ 8 + 6 = 14. \] 
Step 4: Count possibilities for \(d\). Since \(7 \equiv 1 \pmod{3}\), we have \(7^d \equiv 1^d \equiv 1 \pmod{3}\) for any \(d\), so any allowed value of \(d\) works: \[ d = 0,1,2 \Rightarrow 3 \text{ choices}. \] 
Step 5: Total number of valid divisors. \[ \text{Choices for } b = 1,\quad \text{choices for } d = 3,\quad \text{valid } (a,c) \text{ pairs} = 14. \] Thus total divisors of the form \(3r + 1\) are: \[ 1 \times 3 \times 14 = 42. \] Therefore, the required number of divisors is \(42\).