4
$\begingroup$

I'm in number theory and I've been assigned these problems for homework. I've searched throughout the relevant section of the book but I can't seem to find anything that relates to solving these problems.

  1. Describe $n\in \mathbb{N}$ when the number of positive divisors of $n$ is 105.

  2. Which positive integers $n<100$ have the greatest number of positive divisors?

Any help at all is appreciated, thanks.

Edit: Solved #1:

Note that if $n=\prod^{k}_{i=1}p_i^{c_i}$, then $\prod^{k}_{i=1}(1+c_i)$ is the number of positive divisors of $n$, since any $p_i$ can occur up to $c_i$ times, or not at all.

If $n$ has 105 positive divisors, then $105=\prod^k_{i=1}(1+c_i)$.

Note that $105=3\cdot 5\cdot 7$.

So, $105=(1+2)(1+4)(1+6)\implies n=p_1^2\cdot p_2^4\cdot p_3^6$.

$\endgroup$
2
$\begingroup$

You should have seen a formula for the number of positive divisors of a number. If $n= \prod_{i=1}^k p_i^{v_i}$ with distinct primes $p_i$ and positive integers $v_i$ then the number of divisors is $\prod_{i=1}^k (1+ v_i)$.

For the first question note that $105 = 3 \times 5 \times 7 $. This restricts the $k$ and $v_i$ that can appear in the prime factorization of such a number. Be careful though it is not true that $k = 3$, it is only true that $k \le 3$.

For the second question, based on the above formula you can play around a bit to find the solution. Note that small prime divisors are better then large ones.

$\endgroup$
2
  • $\begingroup$ Thank you very much. I was able to solve #1 using those formulas, but I'm still a bit confused as to how solve #2 using the formulas above. $\endgroup$ Sep 25 '15 at 1:15
  • $\begingroup$ You are welcome. For 1 note that there are other possibilities, as I hinted at with the $k \le 3$ not necessarily $k=3$. For example $p^{104}$ also has $105$ divisors. So does $p^{14}q^6$ and a few others. For 2, you could say since $2 \cdot 3 \cdot 5 \cdot 7 >100$ you have $k\le 3$. Now try which combination of exponents for $2$, $3$, $5$ gives you most divisors (note again that one of them might not appear). Then check if you can get the same with other primes, like $7$ instead of $5$. $\endgroup$
    – quid
    Sep 25 '15 at 8:41

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.