The number of divisors of $2^4 \times 3^5 \times 5^3 \times 7^2$ that are of the form $4r + 1$, where $r$ is a non-negative integer, is:
Answer and solution
Correct answer: A
Solution
Need divisors of $2^4\times3^5\times5^3\times7^2$ of form $4r+1\equiv1\pmod4$.
Power of 2 must be 0 (else divisor is even). So consider $3^b\times5^c\times7^d$.
Since $3\equiv3,\ 5\equiv1,\ 7\equiv3\pmod4$: product $\equiv3^b\times7^d\pmod4$.
Need $3^b\times7^d\equiv1\pmod4$, which requires $b+d$ even.
Cases: (i) both even — $b\in\{0,2,4\}$ (3 choices), $d\in\{0,2\}$ (2 choices) → $3\times2=6$; (ii) both odd — $b\in\{1,3,5\}$ (3 choices), $d\in\{1\}$ (1 choice) → $3\times1=3$.
Total $(b,d)$ pairs = 9. Power of 5: $c\in\{0,1,2,3\}$ = 4 choices (all give $\equiv1$).
Total = $9\times4=36$.
Power of 2 must be 0 (else divisor is even). So consider $3^b\times5^c\times7^d$.
Since $3\equiv3,\ 5\equiv1,\ 7\equiv3\pmod4$: product $\equiv3^b\times7^d\pmod4$.
Need $3^b\times7^d\equiv1\pmod4$, which requires $b+d$ even.
Cases: (i) both even — $b\in\{0,2,4\}$ (3 choices), $d\in\{0,2\}$ (2 choices) → $3\times2=6$; (ii) both odd — $b\in\{1,3,5\}$ (3 choices), $d\in\{1\}$ (1 choice) → $3\times1=3$.
Total $(b,d)$ pairs = 9. Power of 5: $c\in\{0,1,2,3\}$ = 4 choices (all give $\equiv1$).
Total = $9\times4=36$.