Contradiction on prime decomposition

Question

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?

Answer 1

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.

Answer 2

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.