1

For example, I have to find all positive divisors of $372$. The prime factorization of $372$ is $2^2 \cdot 3 \cdot 31$

Now, I wonder if there is a fast method to find all positive divisors of $372$.

Dando18
  • 5,368
Always learning
  • 633
  • 2
    Well, any divisor must have the form $2^a3^b31^c$ for $a\in {0,1,2}$ and $b,c\in {0,1}$. – lulu Jul 17 '17 at 14:18

1 Answers1

5

Once you have the prime factorization of a number, say $$n=p_1^{n_1}\cdot p_2^{n_2}\cdots p_{r}^{n_r},$$ then any positive divisors $d$ of $n$ can be written as $$d=p_1^{x_1}\cdot p_2^{x_2}\cdots p_{r}^{x_r}$$ where each exponent $x_i$ is a non-negative integer less or equal to $n_i$. The number of such divisors is equal to the product $(n_1+1)\cdot (n_2+1)\cdots (n_r+1)$.

In your example $n=372=2^2 \cdot 3^1 \cdot 31^1$ and therefore the divisors are $3\cdot 2\cdot 2=12$ and they are $$2^0 \cdot 3^0 \cdot 31^0$$ $$2^0 \cdot 3^0 \cdot 31^1$$ $$2^0 \cdot 3^1 \cdot 31^0$$ $$2^0 \cdot 3^1 \cdot 31^1$$ $$2^1 \cdot 3^0 \cdot 31^0$$ $$2^1 \cdot 3^0 \cdot 31^1$$ $$2^1 \cdot 3^1 \cdot 31^0$$ $$2^1 \cdot 3^1 \cdot 31^1$$ $$2^2 \cdot 3^0 \cdot 31^0$$ $$2^2 \cdot 3^0 \cdot 31^1$$ $$2^2 \cdot 3^1 \cdot 31^0$$ $$2^2 \cdot 3^1 \cdot 31^1$$

Robert Z
  • 145,942
  • @RobertZ , thank you, but, my fault (of course), I have always had problems in understanding mathematical language. I wonder if there is an easier way to explain it. Let's say, less formal. – Always learning Jul 17 '17 at 14:29
  • @Always learning Is it clear now? – Robert Z Jul 17 '17 at 14:41
  • Thank you so much for helping me! I am sorry...but I am very dumb in math. How do I know that "...therefore the divisors are 3⋅2⋅2=12..." ? – Always learning Jul 17 '17 at 14:44
  • Because the exponent of $2$ can be $0,1,2$ (3 choices) , the exponent of $3$ can be $0,1$ (2 choices), the exponent of $31$ can be $0,1$ (2 choices). All these choices are independent and therefore the total number of combinations is the product $3\cdot 2\cdot 2=12$. – Robert Z Jul 17 '17 at 14:51
  • Now it is clear, thanks! So, is this the fasted method to find the positive divisors? – Always learning Jul 17 '17 at 14:54
  • Once you have the factorization (the hard part if $n$ is big) then I don't see any other way to do it. – Robert Z Jul 17 '17 at 14:59
  • Thanks! I wait a while, but I will not forget then to mark this as a solution to my inquiry, in case. – Always learning Jul 17 '17 at 15:30
  • @Always learning You are welcome! – Robert Z Jul 17 '17 at 15:32
  • 1
    @Always this may well be fastest manual method. But suppose that it isn't. In that case it wouldn't be surprising (to me at least) that the fastest method was considerably more complicated. In other words there is often a trade off between fastest and most straightforward. Factoring numbers is good example. Factoring by trial division (using 2 and odd numbers) up to the square root is easy to understand and perform. But there are more complicated methods (trial division by primes) that are quicker and there are far more complicated methods (general number field sieve) that are quicker still. – Χpẘ Jul 17 '17 at 16:10