How to find all prime divisors of $60!$?, where $60!$ denotes the factorial of $60$, the product all integers from $1$ to $60$.
Is there any solution to solve this? Thank you.
4 Answers
Since $60!$ is just the product of first $60$ natural numbers so the only prime numbers which would divide $60!$ are those which are smaller than $60$.
Proof of statements used.
$1$. Only prime numbers which divide $60! $ are smaller than $60$, no prime greater than $60$ can divide $60!$.
Let's say that a prime ($p$) which is greater than $60$ divides $60!$. Now $60!$ is product of first $60$ consecutive natural numbers as $1.2.3.4.5......60$ and what we are saying is that $p|1.2.3.4.5......60$. Now a prime number can only divide itself and its multiple and since our prime $p$ is greater than $60$ so there is nothing in $1.2.3.4.5......60$ which $p$ can divide. A contradiction.
$2$. All the prime numbers smaller than $ 60$ divide $60!$.
It is quite easy to prove, as $60!=1.2.3.4.5......60$, so every prime smaller than $60$ come in $1.2.3.4.5......60$ and hence every prime smaller than $60$ divide $60!=1.2.3.4.5......60$
:) :)
Remember: if $n$ is a positive integer, then $n!$ is divisible by all the positive primes less than $n$. In this case, that means $2, 3, 5, 7, \ldots, 59$.
Now, do you need to find just the distinct prime divisors? If so, you're done. If you also need to count up how often each prime divisor occurs, you've got a bit of work to do. It's tedious but not difficult. Observe:
- $2! = 2$
- $3! = 2 \times 3$
- $4! = 2 \times 3 \times 4 = 2^3 \times 3$. Observe that since $4 = 2^2$, we need to add $2$ to the (previously unwritten) exponent $1$ that $2$ had.
- $5! = 2^3 \times 3 \times 5$. Since $5$ is prime, we can just carry over the previous factorization append the "$\times 5$" at the end.
- $6! = 2^4 \times 3^2 \times 5$. Since $6$ is divisible by $2$ and $3$, we need to increment the exponents for both of those primes.
- $7! = 2^4 \times 3^2 \times 5 \times 7$. Since $7$ is prime, we can just carry over the previous factorization append the "$\times 7$" at the end.
- ...
- $60! = 2^{56} \times 3^{28} \times 5^{14} \times 7^{19} \times \ldots \times 47 \times \times 53 \times 59$.
Actually, come to think of it, I think there's a formula that will give you the exponent of each prime without having to go through this "reverse engineering" of the factorial. So yeah, there is a solution to this problem, more than one of them, in fact.
Hint: $60!=1\cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdots 60$.
It is easy to see that 2 is a prime divisor, 3, 5, 7, ... all primes up to 60.
Three simple observations should make this very obvious:
1) If $k < n$ then $n! = 1*2*.....*(k-1)*k*.......n$ so $k|n!$. So all primes less than $60$ will be prime factors of $60$.
2) If $p$ is prime, and $p > k$ then $p \not \mid k$. So if $p > n$ then $p \not \mid k$ for any $k \le n$.
3) $n! = \prod_k^n k = \prod_k^n (\text{unique prime factorization of }k)$ so $n!$ has as prime factors only the same prime factors of the $k \le n$.
.....
Therefore 1) all primes less or equal to $60$ will be factors and 2) no primes greater than $60$ will be factors. The more interesting question is what is the prime factorization of $60!$. You do have enough information to solve that.
