4
$\begingroup$

Take $n = 12$

$12$'s prime factorization is $2^1\times2^1\times3^1$

So then, the number of factors by UFT is $(1+1)(1+1)(1+1) = 8$

But there's only $1,2,3,4,6,12 = 6$ factors!!

Where are the other two?

$\endgroup$
  • 12
    $\begingroup$ No, it's $2^2\cdot 3^1$ so you get $(2+1)\cdot(1+1)$. $\endgroup$ – Adam Hughes Dec 21 '14 at 3:00
  • $\begingroup$ @AdamHughes Why not post that as an answer? $\endgroup$ – Chantry Cargill Dec 21 '14 at 3:05
  • $\begingroup$ I'll accept this as an answer: "if the number $p = q$ with $p^{\alpha}, q^{\beta}$ then necessarily $r^{\alpha + \beta}, r = p = q$ with an explanation of why we can't just take alpha and beta separately. $\endgroup$ – Don Larynx Dec 21 '14 at 3:07
  • $\begingroup$ @ChantryCargill it seems too simple an observation to merit putting in the answer slot. However, I suppose if Don wants a bit more I can do that. I'll type it up. $\endgroup$ – Adam Hughes Dec 21 '14 at 3:09
  • $\begingroup$ @DonLarynx There you go, a full explanation. $\endgroup$ – Adam Hughes Dec 21 '14 at 3:13
14
$\begingroup$

The formula you've written assumes that all factors in the product are distinct. The reason for the product of $(e+1)$ over each factor $p^e$ is because we are multiplying $p^k$ for all $0\le k\le e$, for each factor $p^e$ in the product. Thus, the decomposition $2^12^13^1$ as you've given gives the following $8$ factors:

\begin{align} 2^02^03^0&=1\\ 2^12^03^0&=2\\ 2^02^13^0&=2\\ 2^12^13^0&=4\\ 2^02^03^1&=3\\ 2^12^03^1&=6\\ 2^02^13^1&=6\\ 2^12^13^1&=12 \end{align}

And now you can see that the double-counted factors come from the fact that $2^12^0=2^02^1$. As long as the prime bases are different, this can't happen, which is why we demand that the decomposition use distinct prime factors in the factorization that yields that formula.

$\endgroup$
6
$\begingroup$

In your example you get $2^2\cdot 3$ so the exponents are $2$ and $1$, not three $1$s. This gives $(2+1)\cdot (1+1)=6$, the correct answer.

The way the theorem is proven is by noting that you can choose exactly how many of a specific prime to include. That is, if

$$n=p_1^{e_1}\cdot\ldots\cdot p_r^{e_r}$$

then there are $e_i+1$ choices for how many factors of $p_i$ are in there. $0,1,2,3,4\ldots, e_i$. That's where the factor comes from. If you tried to do, as you do in this instance $2^1\cdot 2^1\cdot 3^1$, then you are saying by putting in the first two $(1+1)$ factors (the ones that go with the $2$s) that you can take $4$ cases: no $2$s at all, $0$ of the first two and $1$ of the second, $1$ of the first two and $0$ of the second, or $1$ of each $2$. Notice that you count the case of having a single $2$ twice! It doesn't matter which factor of $2$ you grab, it still produces the same factor of $12$. If you are allowed to break up the number, you will always double count something, so you must keep all of the same primes together.

$\endgroup$

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.