Csdrhrt

If $p>3$ is a prime number and $q$ is the next prime following $p$, is it always true that $p!$ is divisible by all $n<q$?

The answer is that $n$ divides $p!$ if $p<n<q$.

Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
$$r^klefrac n2<frac q2<p$$
and then $r^kmid p!$.

Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.

Now we have
$$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
That is, $k<3$. This implies $k=2$.

So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.

Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.

As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.

So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.

The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.

But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).

So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.

I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.

Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.

Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.