We say an integer number $n \ge 1$ is conservative, if the smallest prime divisor of $(n!)^n+1$ is at most $n+2015$. Decide if the number of conservative numbers is infinite or not.
Problem
Source: Olimpiada Rioplatense 2015-Level 3-Problem 3
Tags: number theory, factorial
02.07.2016 05:20
Consider a conservative integer $n \ge 1$ then there exists $p \mid (n!)^n+1$ such that $n+1 \le p \le n+2015$. This means we can let $n=p+k$ with $1 \le k \le 2015$. This follows $(n!)^n+1= ((p-k)!)^{p-k}+1$ and note that $$((p-k)!)^{k-1} \left[ ((p-k)!)^{p-k}+1 \right] \equiv 1+((p-k)!)^{k-1} \pmod{p}.$$This means $p \mid (n!)^n+1$ if and only if $p \mid ((p-k)!)^{k-1}+1$. We also have $(p-k)!(k-1)! \equiv (-1)^{k-1} \pmod{p}$ so $$((k-1)!)^{k-1} \left[ ((p-k)!)^{k-1}+1 \right] \equiv ((k-1)!)^{k-1}+(-1)^{(k-1)^2} \pmod{p}.$$Hence, $p \mid (n!)^n+1$ if and only if $p \mid ((k-1)!)^{k-1}+(-1)^{(k-1)^2}$. Since there are finite number of $k$ ($1 \le k \le 2015$) so there are finite number of $p$ satisfying $p \mid (n!)^n+1$ for $p \le n+2015$. Therefore, there are finite number of conservative number $n$.
22.09.2019 22:00
Not much differen't from above but posting it anyway.We claim that number of conservative numbers is finite.First we prove a well-known generalization of Wilson's Theorem: 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}$. Now assume that the result is wrong then there exists a number $1 \le i \le 2015$ so that $n+i|(n!)^n+1$ we can consider large enough $n$'s so that $n+i$ must be a prime(Since $(n!)^n+1$ has no prime factors less than $n$).Then by the above lemma we have: $n+i|(n!)^n+1 \Rightarrow n+i|(n!)^n(n+i-n)^n+(n+i-n)^n \Rightarrow n+i|1+i^n \Rightarrow n+i|i^{2n}-1$ Also by Fermat's little Theorem we have $n+i|i^{n+i-1}|i^{2n+2i-2}$ So by a well-known lemma we have $n+i|i^{\gcd (2n+2i-2,2n) } -1=i^{\gcd (2i-2,2n) } -1$ If $i \neq 1$ then $i^{\gcd (2i-2,2n) } -1$ is nonzero and at most $i^{2i-2}$ but $n$ can be large enough contradiction.If $i=1$ then by Wilson's theorem $(n!)^n+1 \equiv (-1)^n+1 \equiv 2 \pmod {n+1}$ again a contradiction for large $n$ and we will be done.