8
$\begingroup$

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.

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

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.

$\endgroup$
7
  • $\begingroup$ Why are there $\dfrac{4 \cdot 4 \cdot 6}{2}$ ways? $\endgroup$ – Henry Durham Jul 26 '15 at 15:22
  • 2
    $\begingroup$ @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$. $\endgroup$ – Jack D'Aurizio Jul 26 '15 at 15:25
  • $\begingroup$ @Jack how do you get the intution that $a+c$ should be even?please tell.. $\endgroup$ – Upstart Mar 23 '16 at 13:04
  • $\begingroup$ @Upstart: $3\equiv 7\equiv (-1)\pmod{4}$, hence $3^a\cdot 7^b\equiv (-1)^{a+c}\pmod{4}$. $\endgroup$ – Jack D'Aurizio Mar 23 '16 at 13:19
  • $\begingroup$ Thnx jack for explaining $\endgroup$ – Upstart Mar 23 '16 at 13:32
2
$\begingroup$

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$.

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

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}$$

$\endgroup$
1
  • $\begingroup$ This site uses MathJax. Formatting tips here. $\endgroup$ – choco_addicted Mar 23 '16 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.