How many factors does a million have?

**Natasha1** · May 8th 2006, 01:10 PM

How many factors does a million have?

1 000 000

**ThePerfectHacker** · May 8th 2006, 01:52 PM

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$

**srulikbd** · May 23rd 2006, 08:08 AM

what is the proof?

**CaptainBlack** · May 23rd 2006, 09:10 AM

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

**srulikbd** · May 23rd 2006, 10:31 AM

easy indeed

**ThePerfectHacker** · May 23rd 2006, 01:25 PM

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.

Thread: How many factors does a million have?

LinkBack

Thread Tools

Display

How many factors does a million have?

ns formula!

tnx a lot

Similar Math Help Forum Discussions

How many different ways can you arrange 1 million beans in 3 different bowls

Is there a relation between prime factors and total factors?

1 in 14 million?

how many absolute euler pseudoprimes less than a million

Numbers less than a million containing the digit 2.

Search Tags