2

I'm trying to prove the following statement regarding the fundamental facts of prime numbers, but I don't really understand the relationship between $a$ and $b$.

In order to find all the divisors of any number $a$ we need only decompose $a$ into a product

$$ a=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdots p^{\alpha_r}_{r}$$

where the $p$'s are distinct primes, each raised to a certain power. All the divisors of $a$ are the numbers

$$ b=p^{\beta_1}_{1} \cdot p^{\beta_2}_{2} \cdots p^{\beta_r}_{r}$$

where the $\beta$'s are any integers satisfying the inequalities

$$ 0 \le\beta_1\le\alpha_1, 0 \le\beta_2\le\alpha_2, \cdots, 0 \le\beta_r\le\alpha_r $$

Prove this statement. As a consequence, show that the number of different divisors of $a$ (including the divisors $a$ and $1$) is given by the product

$$ (\alpha_1 + 1)(\alpha_2+1)\cdots(\alpha_r+1) $$

I know that a composite number can be factored into a product of primes in only one way; and that if a prime $p$ is a factor of $ab$, it must be a factor of either $a$ or $b$ - but I don't see how they relate to the above. What are the first steps or realizations I need to make?

hohner
  • 1,049

3 Answers3

1

If $b$ divides $a$, then certainly any prime dividing $b$ must also divide $a$. In addition, though, if (say) $p^k$ divides $b$, then also $p^k$ must divide $a$. So the power of $p$ that appears in the factorization of $a$ must be at least $k$.

Translating this into the language in your post, we have $\beta_1 = k$, and $\alpha_1 \ge k$, so that $0\le\beta_1 \le \alpha_1$.

As for proving the consequence, the $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)$ formula, consider what each possible $b$ looks like. We can choose any power of $p_1$ from $0$ to $\alpha_1$ ($\alpha_1+1$ possibilities), any power of $p_2$ from $0$ to $\alpha_2$ ($\alpha_2+1$ possibilities) and so forth. These choices are all independent, and each different choice produces a different product by unique factorization, so in total there are $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)$ possible divisors.

rogerl
  • 22,399
1

Hint 1: How do exponents work? If $a > b > 0$ and $c \neq 0$ are all integers, then is it true that $c^b$ divides $c^a$?

Hint 2: Start with small cases and specific examples to get the gears going. Let's say our number is $a = 5*2^4$. What are some divisors of $a$? $5$ is one. But so is $5*2$. And also, $5*2^2$. Do you see where I am going with this?

Race Bannon
  • 1,829
  • I can see the pattern of $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)$ but is there an algebraic proof? – hohner Jul 29 '15 at 18:10
  • Yes, I suppose you could use the divisor function. But all that does is demonstrate algebraically what we've put into words. – Race Bannon Jul 29 '15 at 18:14
0

Is it clear that any $b$ in the form $p^{\beta_1}_{1} \cdot p^{\beta_2}_{2} \cdots p^{\beta_r}_{r}$ will divide $a=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdots p^{\alpha_r}_{r}$ (with the constraints on all the $\beta_i$)? If so, we know that some divisors will have the form of some $b$.

To show that all divisors have the form of $b$, we have to use the fact that every divisor of $a$ that is divisible by some prime $p$ must also divide $a$. The same also holds for $p^k$ if a divisor is divisible by $p^k$, and any $p^j$ with $1\le j \le k$.

The step from $$0 \le\beta_1\le\alpha_1, 0 \le\beta_2\le\alpha_2, \cdots, 0 \le\beta_r\le\alpha_r$$

to

$$(\alpha_1 + 1)(\alpha_2+1)\cdots(\alpha_r+1)$$

should be easy enough then.

Kenneth Goodenough
  • 574
  • 5
  • 17