Given $n$ is a positive integer less than $k$, how many values can $n$ take if $(n \pm x)$ is a factor of $n!$ where $x,k$ are also positive integers?

Question

I came across a similar type of question which was

Given $n$ is a positive integer less than $31$, how many values can $n$ take if $(n + 1)$ is a factor of $n!$?

and I solved it by putting through some values of $n$ and then you know by trial and error I came to the answer that there are $18$ values that $n$ can take for this problem.
But this led me to think how to approach a general form of this question which I have put up in the title of this problem. Is there any method or way to for the general problem statement? Or the only way to find the solution for these types of problem is by trial and error or by finding some patterns by putting in the values.

Thanks in advance !

Answer 1

For your original question, there is a better way to solve than using trial and error. We use the below claim:

Claim: For positive integer $n$, $(n+1) \nmid n!$ if and only if $n+1$ is prime or $4$.

Proof : It is clear that $4 \nmid 3!$. Moreover, if $n+1$ is prime, then $\gcd(n+1,x)=1$ for $1 \leqslant x \leqslant n$, which implies that $\gcd(n+1,n!)=1$, and hence, $(n+1) \nmid n!$. Now, assume that $n+1 \neq 4$ and $n+1$ is composite. Then, let $a$ be the smallest prime factor of $n+1$. We then have $n+1=ab$ where $1<a \leqslant b < n+1$ with $a=b$ if and only if $n=a^2$, i.e., $n$ is the square of an odd prime. If $a \neq b$, then since $a$ and $b$ are distinct elements of $\{1,2,\ldots,n\}$, we clearly have $(n+1) \mid n!$. If $n=a^2$, since $a$ and $2a$ are distinct elements of $\{1,2,\ldots,n\}$, we are done. (Note that $n+1 \neq 2a$ because $n+1 \neq 4$).

---

Now, the number of positive integers $n$ less than $k$ such that $(n+1) \mid n!$ must thus be the number of non-prime elements excluding $4$ that are in the set $\{2,3,\ldots,k\}$ (these are the values $n+1$ takes). It is clear that the number of solutions is hence $(k-\pi(k)-2)$ solutions, where $\pi(x)$ is the number of primes $\leqslant x$.

Now, when replacing $n+1$ with $n+x$, the general idea is the same for large $n$. However, for small $n$, the value of $n+x$ can be significantly larger than $n$, and thus, we must be careful about counting the solutions of $n \in \mathcal{O}(x)$. For $n-x$, the answer is simply $k$, since $(n-x) \in \{1,2,\ldots,n\}$ and hence, $(n-x) \mid n!$.

Answer 2

We claim that $n+1$ doesn't divide $n!$ if and only if $n+1$ is a prime or $n+1=4$. Clearly if $n+1$ is a prime or $n+1 = 4$, then $n!$ isn't divisible by $n+1$.

If $n+1 = p^k$, where $k \ge 2$ if $p$ is odd or $k \ge 3$ if $p$ is even we have that both $p$ and $2p^{k-1}$, which are distinct integers are factors of $n!$. Therefore $n+1 = p^k \mid n!$.

Now suppose that $n+1 = p_1^{e_1} \cdots p_k^{e_k}$ with $k \ge 2$. We going to look at each of the prime factors again. As $k \ge 2$ note that $p_i^{e_i} \le \frac{n+1}{2} < n$. Therefore $p_i^{e_i}$ is a factor of $n!$. As this holds for all the prime divisors we deduce that $n+1 \mid n!$.