For any positive integer $d$, prove there are infinitely many positive integers $n$ such that $d(n!)-1$ is a composite number.
Problem
Source: China TST 2011 - Quiz 2 - D1 - P3
Tags: number theory, IMO Shortlist, number theory unsolved
24.03.2011 13:09
Suppose the result is wrong, then there exists a positive integer $M$ such that $d\cdot n!-1$ is prime for any $n>M$. First we prove that, for $x>{\color{red} 2d}$, the number $x!-d$ has a prime divisor greater than $x$. Suppose the contrary, then each prime divisor of $x!-d$ divides $x$ and hence also divides $d$. Since $x>2d$, for any prime divisor $p$ of $x!-d$ we have $\nu_p(x!)>\nu_p(d)$, so $\nu_p(x!-d)=\nu_p(d)$. Therefore $x!-d\le d$, which is not true. Therefore our claim is true. Let $m=(M+d)!+1$. The number $(2m-1)!-d$ has a prime divisor $q$ greater than $2m$. So (all congruences are in modulo $q$) $d\equiv(2m-1)!\equiv(q-2)\ldots(q-2m+1)\equiv\frac{(q-2)!}{(q-2m)!}$. From Wilson's theorem, we have $-1\equiv(q-1)!\equiv(q-1)(q-2)!\equiv-(q-2)!$, hence $(q-2)!\equiv1$. Therefore $d(q-2m)!\equiv(q-2)!\equiv1$. So $d(q-2m)!-1$ is divisible by $q$, and hence is composite. Therefore $q-2m\le M$, or $q=2m+k$ for some $k\le M$. But $2m+k=2(M+d)!+2+k$ is divisible by $k+2$, and hence is not a prime. We get a contradiction. Our proof is done.
24.03.2011 16:20
$x>d+1$ maybe $x>2d$, if not ${v_p}(x!)$ can be equal to ${v_p}(d)$. Another question: Can $d(q - 2m)! - 1 = q$ ? Than $d(q - 2m)! - 1$ is not composite.
24.03.2011 17:51
I thought that was trivial. Now it looks a bit problematic. So let's assume that $d(q-2m)!-1=q$. Apply the same argument with $m\rightarrow m+1$, we get another prime $r$ such that $d(r-2m-2)!-1=r$. So we get $\frac{q+1}{(q-2m)!}=\frac{r+1}{(r-2m-2)!}$. For simplicity, we write $q-2m=a,r-2m-2=b,2m+1=x$, then $\frac{a+x}{a!}=\frac{b+x+2}{b!}$, or $ab!+xb!=ba!+xa!+2a!$. So we get $x(b!-a!)=ba!-ab!+2a!$. Clearly $a\ne b$. If $a>b$, then $LHS<0<RHS$, a contradiction. Assume $a<b$, so LHS is positive, and so is RHS. We get $ab!<(b+2)a!$, $\frac{b!}{b+2}<(a-1)!\le(b-2)!$. Therefore $b(b-1)<b+2$. Since $b=r-2m-2$ is odd, we get $b=1$. Now we have $\frac{a+x}{a!}=x+3$, which is clearly impossible.
24.03.2011 18:01
Very nice, thank you!
21.05.2011 03:30
This problem is a weaker version of an IMO shortlist 2005 problem.
10.06.2011 05:57
agzqu wrote: This problem is a weaker version of an IMO shortlist 2005 problem. In the IMO shortlist 2005 problem the $degP>1$. http://www.artofproblemsolving.com/Forum/viewtopic.php?p=789443&sid=2569fbf8fc8646498a0c74303a74528a#p789443
10.06.2011 06:03
It's also true for $deg(P)=1$.
20.09.2012 15:10
What about $d(n!) +1$ ? does there exist many Integers $n$ such that $d(n!)+1$ is a composite number?
30.03.2015 05:52
Let's take a big $N$ and a big even $ \ell > 2d+N$ such that there are no primes near $ \ell $ (which we can do by CRT). (By near, i mean at distance $<N$). Now take any prime divisor $q | 1+\frac{\ell !}{d}$. Clearly $q>\ell$ and so $q>\ell+N$. Since $q | d+ \ell !$ we have $d \equiv -\ell ! (\bmod q)$ and so since $\ell$ is even, $d = -(-1)...(-\ell)=-(q-1)...(q-\ell)$ so by Wilson Theorem, $\displaystyle\frac{d(q-1)!}{(q-1)...(q-\ell)} = 1 (\bmod q)$ which means $q | d(q-\ell -1)! -1$. Also, notice that the equality $q=d(q-\ell -1)!-1$ can be true only if $\ell=dx!-2-x$ for some integer $x$. Since these values are very spread-out in the integers, we can assume $\ell$ is not of that form. And so $q$ is a proper divisor of $d(q-\ell -1)!-1$. If only finitely many $n$ worked, then notice that the number of pairs $(p,n)$ such that $p$ is a proper prime divisor of $dn!-1$ is finite, and therefore the number of values $m$ where $m=p-n$ is finite, but we know that infinitely many big $\ell$ can satisfy $m=\ell+1$ and so there are infinitely many $n$ work.
26.07.2015 08:59
My solution: Lemma: let $p$ be a prime number and $k<p$ be a positive integer then $(k-1)!(p-k)!\equiv (-1)^k\pmod{p}$. Solution to lemma: From wilson's theorem we have $(p-1)!\equiv -1\pmod{p}\Longrightarrow (p-1)(p-2)\dots (p-(k-1))(p-k)!\equiv -1\pmod{p}\Longrightarrow (-1)^{k-1}(k-1)!(p-k)!\equiv -1\pmod{p}\Longrightarrow (k-1)!(p-k)!\equiv (-1)^k\pmod{p}$. Consider a large even integer $k=m!,m=q-1$ for some big prime $q$ and take a prime $p$ such that $p\mid (k-1)!-d$(1) it's obvious that $p\ge k+m+1$ (because $k=m!,k+1=m!+1\equiv 0\pmod{p},k+2=m!+2,\dots k+m=m!+m$ are composite integers) thus $p=k+m+1+s$ (***)for some nonnegative integer $s$ from the lemma we deduce that $(k-1)!(p-k)!\equiv 1\pmod{p}$ so from (1) we get $p\mid d(p-k)!-1\longrightarrow d(p-k)!-1=pt$ if $t>1$ we are done so assume that $t=1$ and $p=d(p-k)!-1$(2) from (***),(2) we have $k+m+1+s=d(m+s+1)!-1$ but with easy induction on $s$ we can easily prove that $d(m+s+1)!-1>k+m+s+1$(assume that it is true for $s$ then $d(m+s+2)!-1>d(m+s+1)!>k+m+s+2$ so done). Hence we get a contradiction and $t>1$. DONE
25.07.2022 22:30
I'll provide some motivation for the solution, indeed it nicely ties to IMO Shortlist 2005, N7 to almost prove the result for all polynomials $P(x) \in \mathbb{Z}[x]$ (there are some linears that are still missed, specifically those such as $P(X) = 2X-3$, but such polynomials can be dealt with the same methods that solve this problem). I will present a pretty motivated solution without many difficult parts, it is in some ways similar to those above. The case $d=1$ seems relatively simple and indeed is, so let us establish the result for the case first.
Now, assume for the sake of contradiction that there exists some $N \in \mathbb{N}$ such that for all $n \in \mathbb{N}, n \geq N$ $d \cdot n!-1$ is prime; we will now define the seemingly random function $f: \mathbb{N} \setminus [d] \to \mathbb{N}$ as follows $$f(m) = (d-1)! \cdot (d+1)(d+2) \cdots (m-1) \cdot m+(-1)^m$$ Now, let $p_m$ be the smallest prime divisor of $f(m)$ which exists as $f(m) \in \mathbb{Z}_{\geq 2}$ for all $m \geq d+1$. Take $m \geq 2d$ and notice that $p_m > m$ for all such $d \in \mathbb{N}$ because $gcd(m!,f(m)-1) \mid d$ but $d \mid f(m)$ means that $gcd(f(m)-1,d) = 1$. Then, notice that $p_m \mid f(m)+(-1)^m$ meaning that $0 \equiv d(f(m)+(-1)^m) \equiv m!+d(-1)^m \pmod{p_m}$. Now, using Wilson's Theorem, in $\mathbb{F}_{p_m}$ $$(p_m-m-1)! = \frac{(p_m-1)!}{(p_m-1)(p_m-2)\cdots (p_m-m)} = \frac{-1}{(-1)^m \cdot m!} = \frac{-1}{(-1)^m (-(-1)^m) \cdot d} = \frac{1}{d}$$ Then, $$p_m \mid d(p_m-m-1)!-1$$we know that $d(p_m-m-1)!-1 \geq d-1 > 0$ meaning that if we define $k_m = p_m-m > 0$, we have that each $k_m \in \mathbb{N}$ can appear finitely many times because otherwise there would some $k \in \mathbb{N}$ such that $k = k_i$ for some infinite sequence $a_1 < a_2 < \cdots$ in which case $(k-1)!-1 > 0$ would have infinitely many prime divisors because $p_m > m$ means that $(p_m)_{m>d}^{\infty}$ is unbounded. Then, as $k_m \geq C$ for all sufficiently large $m \in \mathbb{N}$ for any $C \in \mathbb{N}$, and we know that $d \cdot n!-1$ is prime for all $n \geq N$, taking $k_m \geq N+1$ we have $d \cdot (p_m-m-1)!-1$ is prime and $p_m \mid d \cdot d \cdot (p_m-m-1)!-1$. Upshot: For all sufficiently large $m \in \mathbb{N}$, $m \in \mathbb{N}$, $p_m = d \cdot (p_m-m-1)!-1$. Main Claim: For all sufficiently large $m \in \mathbb{N}$, $p_m > p_{m+1}$.
Now, notice that $p_m > p_{m+1}$ for all sufficiently large $m \in \mathbb{N}$ but then there exists some $m \in \mathbb{N}$ such that $m \geq p_m > m$ which is a contradiction. $\blacksquare$ $\blacksquare$
09.07.2023 12:31
It suffices to prove that for any positive integer $N$, there exists a prime number $p>N$ and a positive integer $n$, such that $p\mid d\cdot n!-1$, and $p\neq d\cdot n!-1$. There are obviously infinitely many positive integers $x$ such that $[2x,4x+2]\cap K_d=\emptyset$, where $K_d:=\{d\cdot n!\mid n\in \mathbb{Z}_{\geq0}\}$. Take such $x$ satisfying $x>\text{max}(N,d)$, and we consider prime divisors of $A:=(2x)!+d$. Note that $\frac{A}{d}=\prod\limits_{1\leq j\leq 2x, j\neq d}j+1$ an positive integer coprime to $(2x)!$, thus there exists a prime number $p>2x>N$ that divides $A$. Notice that $(p-1)!+1$ is divisible by $p$, thus we conclude that $p$ divides $d\cdot (p-2x-1)!-1$. If $p>4x+2$, then $$p\leq (2x)!+d<(2x+1)!-1<d\cdot (p-2x-1)!-1$$We are done in this case. If $2x<p\leq4x+2$, from earlier we know that $p\notin K_d$, indicating $p\neq d\cdot (p-2x-1)!-1$, and we are done as well.