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,
$\tau (n)$. It is defined as the number of distinct divisors of $n$. For example,
$\tau (3)=2$ cuz 3 only got 2 factors 1 and 3.

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

Thus, since,
$1,000,000=10^6=(2\cdot 5)^6=2^6\cdot 5^6$
Thus, $(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

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

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

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

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

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

Hence the number of factors is:

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

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