There are at least two primes with power 1 in $k!$ for $k>11$

Question

My question is: need to prove that $\forall \ k \geq 11, \exists$ at least 2 prime numbers with power of 1, in k! factorization. I know I missed something, and that is why I'm looking for a hint. Thanks for help!

*** I can use that $\forall \ k > 5$ there exist at least $2$ prime numbers in the next interval: $(k,2k)$.

Answer 1

For a fixed $k$, consider the prime numbers in the interval $(\lceil \frac{k}{2} \rceil, 2 \lceil \frac{k}{2} \rceil)$ (observe that $k/2 > 5$). According to the result you said you are allowed to assume, there are at least two such prime numbers.

Note that if $p$ is in that interval, then $2p > n$ so $p$ is the only multiple of $p$ in the interval $[1,k]$. Then, $p$ appears only once in the factorization of $k!$. This is because to count the power of $p$ in $k!$ we only need to look at multiples of $p$ (since $p$ is prime, those are the only ones that contribute a power of $p$ to $k!$). But the only multiple is $p$, so the power of $p$ is $1$ in the factorization.

Since this is true for at least two different prime numbers, you get your result.

EDIT: You don't need to distinguish between $k$ even or odd. $\lceil \frac{k}{2} \rceil$ is the integer $\geq k$ that is closest to it, so you have $\lceil \frac{k}{2} \rceil > \frac{k}{2}$. Hence, $k+1 \geq 2 \lceil \frac{k}{2} \rceil > k$ and you can apply the reasoning above regardless of the parity of $k$.

Answer 2

I can suggest using Legendre's formula $$\nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}$$ Now, let's consider the primes $p_1,p_2$ s.t. $$\frac{n}{2} < p_1<p_2 < n \tag{1}$$ Then $$n=p_1 q_1 +r_1, 0\leq r < p_1-1$$ $$n=p_2 q_2 +r_2, 0\leq r < p_2-1$$ Both $q_1=q_2=1$ (otherwise, from $(1)$, $n>2p_1+r_1>n$ and similarly $n>2p_2+r_1>n$) and $r_1>0$, $r_2>0$. As a result $$s_{p_1}(n)=q_1+r_1\geq 2$$ $$s_{p_2}(n)=q_2+r_2\geq 2$$ And finally $$\nu _{p_1}(n!)={\frac {n-s_{p_1}(n)}{p_1-1}} < {\frac {2p_1-2}{p_1-1}}=2$$ $$\nu _{p_2}(n!)={\frac {n-s_{p_2}(n)}{p_2-1}} < {\frac {2p_2-2}{p_2-1}}=2$$

---

Of course $(1)$ works ideally for even $n$'s. What about odd $n$'s? In this case, we consider $$\frac{n+1}{2} < p_1<p_2 < n+1$$ since $n+1$ is even and can not be prime. However we may have $p_2=n$, but then $$\nu _{p_2}(n!)={\frac {n-s_{p_2}(n)}{p_2-1}}={\frac {p_2-1}{p_2-1}}=1$$

Answer 3

It is easily verified that the property is valid for $k\le5$.

For $k\gt5$, Ramanujan showed in 1919 that between $k$ and $2k$ there are at least two distinct primes (a refinement of Bertand's postulate). Then taking $$\left\lfloor\frac k2\right \rfloor\lt p\lt q\lt k\lt p^2\lt q^2$$ we have $p$ and $q$ as examples showing the property. In fact: $$k!=1\cdot2\cdot3\cdots p\cdots q\cdots k$$ where all factor to the right of $p$ is coprime with $p$ and so is with $q$.