# How many factors does a million have?

• May 8th 2006, 01:10 PM
Natasha1
How many factors does a million have?
How many factors does a million have?

1 000 000
• May 8th 2006, 01:52 PM
ThePerfectHacker
Quote:

Originally Posted by Natasha1
How many factors does a million have?

1 000 000

In number theorem there is a number-theoretic function,
$\displaystyle \tau (n)$. It is defined as the number of distinct divisors of $\displaystyle n$. For example,
$\displaystyle \tau (3)=2$ cuz 3 only got 2 factors 1 and 3.

There is a formula, if
$\displaystyle n=p_1^{a_1}p_2^{a_2}....p_k^{a_k}$
is the prime-factorization of $\displaystyle n$
Then,
$\displaystyle \tau (n)=(a_1+1)(a_2+1)...(a_k+1)$

Thus, since,
$\displaystyle 1,000,000=10^6=(2\cdot 5)^6=2^6\cdot 5^6$
Thus, $\displaystyle (6+1)(6+1)=7\cdot 7=49$
• May 23rd 2006, 08:08 AM
srulikbd
ns formula!
:) what is the proof?
• May 23rd 2006, 09:10 AM
CaptainBlack
Quote:

Originally Posted by srulikbd
:) what is the proof?

Let

$\displaystyle n=p_1^{a_1}p_2^{a_2}....p_k^{a_k}$

Then any factor $\displaystyle r$ of $\displaystyle n$ is of the form:

$\displaystyle r=p_1^{b_1}p_2^{b_2}....p_k^{b_k}$

where $\displaystyle b_i \in \{0,\ 1, \ ..,\ a_i\}$, and each number of this
form is a factor of $\displaystyle n$.

So how many $\displaystyle r$'s are there? Well the first exponent can take
any one of $\displaystyle a_1+1$ values the second can ....

Hence the number of factors is:

$\displaystyle \prod_{i=1}^n (a_i+1)$

RonL
• May 23rd 2006, 10:31 AM
srulikbd
tnx a lot
easy indeed ;)
• May 23rd 2006, 01:25 PM
ThePerfectHacker
Quote:

Originally Posted by srulikbd
:) what is the proof?

One more.

This one is more advanced but more elegant ;)

Theorem:
If $\displaystyle f$ is a number theoretic function which is multiplicative. Then, the function $\displaystyle F$ definied as, $\displaystyle F(n)=\sum_{d|n}f(d)$ is also.
---------
Note that,
$\displaystyle \tau (n)=\sum_{d|n}1$
Since, $\displaystyle f(n)=1$ is multiplicative since,
$\displaystyle f(ab)=f(a)f(b)$ whenever $\displaystyle \gcd(a,b)=1$ we have that,
$\displaystyle \tau(n)$ is mulitplicative.

Since,
$\displaystyle \tau(p^n)=n+1$
You have,
$\displaystyle \tau(p_1^{k_1}\cdot ....\cdot p_s^{k_s})=(k_1+1)\cdot ...\cdot (k_s+1)$
because or multiplicativity.