Prove that there exists a sequence of unbounded positive integers $a_1\leq a_2\leq a_3\leq\cdots$, such that there exists a positive integer $M$ with the following property: for any integer $n\geq M$, if $n+1$ is not prime, then any prime divisor of $n!+1$ is greater than $n+a_n$.
Problem
Source:
Tags: number theory, prime numbers, factorial
28.10.2011 08:05
Using the following lemma will immediately kill the problem. Lemma : for any positive integer $p$ there exists a positive integer $N_p$ such that for any integer $n\geq N_p$,$n+1$ is not prime, any prime divisor of $n!+1$ is greater than $n+p$. In addition to prove the lemma, Wilson's theorem would be just fine.
08.04.2013 15:17
Let $p|n! + 1$ and let $p = n + k$ then by Wilson's we get $n(n+1)...(n+k-1) \equiv 1 \pmod {n+k}$ and so we get $(1)(2)...(k) \equiv (-1)^k \pmod {n+k}$ $\implies k! \geq n+k-1 \geq n$ as we cannot have it equal to $1$ since $n+1$ is not prime. Taking $a_n$ as the maximal integer $k$ such that $k! \leq n$ we are done since $a_n$ is clearly non-decreasing and unbounded.
14.06.2015 20:20
My solution: assume for a sake of a contradiction that for a natural number $k$ there is a sufficiently large $n\ge k!$ such that there Is a prime $p=n+k$ that $p\mid n!+1\longrightarrow n!\equiv -1\pmod{p}$ from willson's theorem $(p-1)!\equiv -1\pmod{p}\longrightarrow (p-1)!\equiv (p-1)(p-2)\cdots (p-k+1)n!\equiv (-1)^{k-1}(k-1)!n!\equiv (-1)^k(k-1)!\equiv -1\pmod{p}\longrightarrow p\mid (-1)^k(k-1)!+1\longrightarrow k!+k\le n+k=p\le (k-1)!+1$ contradiction. DONE
25.08.2021 08:05
Suppose that $N$ is one of those extremely large integers which satisfy this property. Suppose that $N! \equiv -1 \pmod p $ for some prime $p$ which is minimal. $N$ must be less than $p$ or else this would be impossible. By the generalization of the Wilson's Theorem,$N!(p-N-1)! \equiv (-1)^N \pmod p$ By size issues,$p-N \ge 3$. So choose $a_n=\max(m)$ such that $m! \le n+1$ then $p \ge a_N+N$ and so we are done.
31.12.2022 12:56
For the sake of contradiction, assume that it doesn't works for some $a_{k}$, choose a $n \geq a_{k}!$, Let p be the smallest prime divisor of $n! + 1$, we clearly know that $p \geq n$, by wilson's, we get that \[(p-1)! \equiv n! \pmod p\], by further cancellation, we get \[(-1)^{p-n}(p-n)! \equiv -1 \pmod p\], which is a contradiction since $a_{k}! \geq (p-n)!$ and $a_{k}! \leq n$, hence a contradiction.
14.04.2023 01:53
It suffices to show that $\text{min}_{p \mid n! + 1} p - n$ is unbounded. Pick some $p \mid n!+1$. Then $$(p-n-1)!n! \equiv (-1)^{n-1} \pmod p,$$hence $(p-n-1)! \equiv (-1)^n \pmod p$ by Wilson's. As $p-n-1 \neq 1$, we must have $(p-n-1)! \geq p-1 \geq n$. This is enough, as the sequence $\{a_n\}$ of integers defined by $a_n$ to be the minimal integer such that $a_n! \geq n$ is unbounded.