# Number of divisors of the form $(4n+1)$

Find the number of divisors of $$2^2\cdot3^3\cdot5^3\cdot7^5$$ which are of the form $(4n+1)$

I know how to find the total number of divisors. But, to find the number of divisors of the form $(4n+1)$, I'm thinking of listing down the divisors and then finding, but that'd be very tedious. Is there any elegant way to do this?

Any help will be appreciated.
Thanks.

• Hint: You may have as many 5's as you want, but an even number of 3's and 7's. – vadim123 Jul 26 '15 at 14:55
• This is relevant. – Ray Bradbury Nov 20 '20 at 17:40

Any positive divisor of $2^2\cdot 3^3\cdot 5^3\cdot 7^5$ of the form $4k+1$ is a number of the form: $$3^a\cdot 5^b\cdot 7^c$$ with $0\leq a\leq 3,0\leq b\leq 3,0\leq c\leq 5$ and $a+c$ being even. There are: $$\frac{4\cdot 4\cdot 6}{2}=\color{red}{48}$$ ways to choose $a,b,c$ that way.

• Why are there $\dfrac{4 \cdot 4 \cdot 6}{2}$ ways? – Henry Durham Jul 26 '15 at 15:22
• @Samurai: we are free to take $b$ as we like in the interval $[0,3]$, but just half the choices of $(a,c)\in[0,3]\times[0,5]$ give an even value of $a+c$. – Jack D'Aurizio Jul 26 '15 at 15:25
• @Jack how do you get the intution that $a+c$ should be even?please tell.. – Upstart Mar 23 '16 at 13:04
• @Upstart: $3\equiv 7\equiv (-1)\pmod{4}$, hence $3^a\cdot 7^b\equiv (-1)^{a+c}\pmod{4}$. – Jack D'Aurizio Mar 23 '16 at 13:19
• Thnx jack for explaining – Upstart Mar 23 '16 at 13:32

Hint:

$(4n+3)(4k+3)=4(4nk+3(n+k)+2)+1$, applicable to $3, \; 7$; and

$(4n+1)^2=4(4n^2+2n)+1$, applicable to $5$.

• ... and so?$\phantom{}$ – Jack D'Aurizio Jul 26 '15 at 21:00
• @JackD'Aurizio And that is the underlying algebra of your and vadim123's statement. – James Pak Jul 27 '15 at 4:38

Number of divisors of $$N= 2^2\times3^3\times5^3\times7^5,$$which are of the form $4n+1$ exculuding \begin{align}1 &=\{ \text{number of terms in product}\}\\ &=(1+3^2)(1+5+5^2+5^3)(1+7^2+7^4)+\{\text{number of terms in product}\}\\ &= ( 3+3^3)(7+7^3+7^5)(1+5+5^2+5^3)-1\\ &= 2\times4\times3+2\times3\times4-1\\ &= 47 \end{align}

• This site uses MathJax. Formatting tips here. – choco_addicted Mar 23 '16 at 12:59