Lemma:If m<(2b+1)^2 and m in relatively prime to b+1...2b then m is prime We have n+k^2+k is prime for k=1->r;r=[\sqrt{n\3}] and need to show n+k^2+k is prime for k=r+1->n-2.Applying the lemma for m=n+(r+s)^2+r+s;b=r+s(s=1->n-s-r)The computation is simple

I have not still yet checked ur solution,but perhaps,my one is quite similar. Call y is miniamal number st p(y) is composite,p is minimal prime divisor of p(y).We need to show that: y>n-2. Supposing that y≤n-2.We will show that:p≥2y+1 ,then p(y)=y²+y+n≥p²> 4y²+4y+1->n>3y²->y<√(n/3).It's absurd! Indeed suppoing that p<2y+1.Consider p(y)-p(x)=(y-x)(y+x+1) when x in {1,2,..y} then (y-x) and y+x+1 will run over all values of set{1,2,...,2y+1} then there exists x in that set such that p(y)-p(x) is divisible by p ->p(x) is too. Accoring definition of y we deduce that p(x)=p.But : y-x<y+x+1<(n-2)+x+1<x²+x+n=p->A contradiction!!And we are done!

Consider the least prime $ q$ dividing a composite value $ k^2 + k + n$ with $ \sqrt {n/3} < k\leq n - 2$. Clearly $ q < n$ so every residue class modulo q is represented between 0 and n-2. Thus both roots of $ k^2 + k + n = k^2 - (q - 1)k + n = 0$ mod q are in the desired range, so we may some root $ k < = \frac {q - 1}{2}$. $ k > \sqrt {n/3}$ implies $ q > 2\sqrt {n/3} + 1$ $ q$ being minimal implies $ q^2 \leq k^2 + k + n \leq \frac {q^2 - 1}{4} + n$, so \[ q^2 \leq \frac {4n - 1}{3} < (2\sqrt {n/3} + 1)^2 < q^2 \] . So no such $ q$ exists.

q<n ? How come?

$ q^2 \leq k^2+k+n < n^2$ (certainly for n not trivially small)

ok sorry, i get it now

Don't worry. I actually wrote this up and it took a whole page of A4, so the above argument is very much a sketch.

Yeah, I wondered why I still dont understand why get why every residue between 0 and n-2 is represented (in mod q). This is embarassing

Well, since q<n, so q<=n-1, so 0,1,2,....,n-2 must contain 0,1,...,q-1 as a subset. I attach a more detailed account of my solution.

Yes, thank you ever so much! I would never have been able to carry out that kind of argument!

You probably could have. The basic intuitive idea was that if there are going to be composite numbers, there are going to be some fairly small primes involved, but that equally such primes would not be able to be too small, or else the first few numbers of our sequence would be divisible by them. It then remained to do a bit of work to try to put as much pressure as possible on q from each side until it broke.

Yes, but I've never thought of working with the factorisation of polynomials in modular arithmetic before. Thanks. Besides, I need some IMO training anyway. You'll be at Trinity, I guess?

Ah I see. Yes, indeed. Who are you?

My name is Henry Husband. I just need to get a few IMO questions under my belt, thats all.

Ah sure. Well, this one was a Q6, and the solution took me in excess of an hour to complete, so... If you're determined to attack IMO questions, it's best to start on Q1,4 of recent IMOs and perhaps try attacking whole papers from before 1983ish when they started getting much harder. I look forward to seeing you at Trinity (I'm guessing...).

Let $m=\lceil\sqrt{s/3}\rceil$, and let $a_n=n(n-1)+s$. We are given that $a_1,\ldots,a_m$ are prime, and we want to show that $a_1,\ldots,a_{s-1}$ are prime. We will proceed by strong induction. In particular, we will show that if $a_1,\ldots,a_{k-1}$ are prime with $\sqrt{s/3}+1\le k\le s-1$, then $a_k$ is prime. Suppose $a_k$ was not prime, so it has a prime factor $p\le\sqrt{a_k}$. Now, if $n\equiv k,1-k\pmod{p}$, then $a_n\equiv a_k\pmod{p}$, so $p\mid a_n$ as well. We now show that there exists such $n$ with $1\le n\le k-1$. In other words, we want to show that there exists $x\in[1,k-1]\cup(p+1-[1,k-1])=[1,k-1]\cup[p+2-k,p]$ such that $x\equiv k\pmod{p}$. It suffices to show that $p+1-k<k$, because then that union of two intervals would contain $[1,p]$, so it would contain all residue classes mod $p$. Note that \begin{align*} 2k-1> \sqrt{a_k}&\iff 4k^2-4k+1> k^2-k+s \\ &\iff 3k^2-3k+1> s \\ &\longleftarrow 3(\sqrt{s/3}+1)^2-3(\sqrt{s/3}+1)+1> s \\ &\iff s+3\sqrt{s/3}+1>s, \end{align*}which is true, so $2k-1> \sqrt{a_k}\ge p$, so $p+1-k<k$, as desired. Therefore, there is some $1\le n\le k-1$ with $p\mid a_n$. But $a_n$ is prime by the inductive hypothesis, so $a_n=p$. Thus, we have $a_n\mid a_k$, so $a_n\mid a_k-a_n=(k-n)(k+n-1)$. Since $a_n$ is prime, either $a_n\mid k-n$, or $a_n\mid k+n-1$. We have that $a_n\ge s>k\ge k-n$, so $a_n>k-n$. Therefore, $a_n\mid k+n-1$. But $2a_n\ge s+s>k+n>k+n-1$, so the only possibility is $a_n=k+n-1$. But then, $n^2-n+s=k+n-1$, or $k=s+(n-1)^2\ge s$, which is a contradiction. Therefore, our assumption that $a_k$ is not prime is wrong, so $a_k$ is prime. Therefore, we finish by induction on $k$.

Let $f(x)=x^2+x+n$ and assume that there exists $\sqrt\frac{n}{3}< k\leq n-2$ such that $f(k)$ is not prime and choose the smallest such $k.$ Let $p$ be a prime divisor of $f(k),$ such that $p\leq \sqrt{f(k)}.$ Note that $$p\leq \sqrt{f(k)}=\sqrt{k^2+k+n}<\sqrt{4k^2+k}<2k+1\Rightarrow p<2k.$$ Let's first look at the case $k<p<2k$ and let's write $p=k+r, 0<r<k.$ We have $$0\equiv f(k)\equiv f(-r)=f(r-1)\pmod p,$$and since $0\leq r-1<k,$ it must be the case that $r+k=p=f(r-1)=r^2-r+n,$ which rewrites as $0<r^2-2r+2=k-n+2\leq 0,$ contradiction$.$ If $p=k,$ then $p\mid n,$ but $f(0)=n$ is prime and therefore $k=p=n>n-2,$ contradiction$.$ Finally, assume $0<p<k.$ Denote $r=k\pmod p.$ We have $0\equiv f(k)\equiv f(r) \pmod p,$ and since $0\leq r<p<k,$ it follows that $p=f(r)=r^2+r+n\geq n>k>p,$ contradiction$. \blacksquare$

Note that in general, we may write $a_n = n^2 - n + s$. Let $t$ be the smallest positive integer for which $a_t$ is not prime; we wish to prove $t \geq s$. Let $p$ be the smallest prime dividing $a_t$. We have\[p \leq \sqrt{a_t} = \sqrt{t^2 - t + s} \leq \sqrt{4t(t - 1)} < 2t - 1\]since clearly $s = 3m^2 \leq 3t(t-1)$ as $t \geq m + 1$. Hence $p \in [0, 2t - 2]$. Next, we observe that \[a_t \equiv 0 \pmod p \implies a_{t-p} \equiv 0 \pmod p.\]So in the case $p \leq t-1$ then we can subtract sufficiently many copies of $p$ from $t$ to obtain an index $t - \ell p = i$ for which $1 \leq i \leq m$ and $a_i \equiv 0 \pmod p$ is prime. Then, $a_i$ must be $p$ and then we have $a_t \geq p^2 = a_i^2 \geq a_1^2 = s^2 = a_s \implies t \geq s$ as desired. In the case that $p \in [t+1, 2t - 2]$, we can let $p = t + r$ where $r \in [1, t-2]$ so that\[a_t \equiv a_{t - p} = a_{-r} = r^2 + r + s \equiv a_{r-1} \equiv 0 \pmod{p}\]and clearly $r - 1 \leq t - 1 \leq m$ so $a_{r-1}$ is prime, so it follows that\[a_t \geq p^2 = a_{r-1}^2 \geq a_1^2 = s^2 = a_s \implies t \geq s\]as desired. Lastly, if $p = t$, then $a_t = a_p = p^2 - p + s$ is disivible by $p$ hence $p \mid s$. However, we have $s = a_1$ is prime so $p = s \implies t = s$ which is what we wanted to prove. We have exhausted all three cases so we are done; indeed, $t \geq s$ always. $\blacksquare$

Let $F(X)=X^2+X+n$ and define $p$ as the smallest prime factor of the numbers $F(0),F(1),.....$ For the sake of contradiction assume the opposite and proceed. Suppose for $X=k<n-2$ is composite,then the smallest factor $q$ of $F(k)$ will satisfy $q^2 \ge f(k)<n^2$,hence $q^2<n^2$ or $q,p<n$(obvious since $p \le q$) Let $s$ be the remainder when $k$ is divided by $p$ and let $r=\min(s,p-s-1)$,and it is clear that $p|f(r)$ so by the fact $2r \le p-1$,$f(r) \le n+\frac{p^2-1}{4}$ Now choose a prime factor of $\frac{f(r)}{p} \in \mathcal{Z}$,and by the minimality of $p \le q$,$p^2 \le F(r) \le \frac{p^2-1}{4}+n$(already established before),so taking square roots we get $p<2 \sqrt{\frac{n}{3}}$ implying $r<\frac{p}{2} \le \sqrt{\frac{n}{3}}$,a contradiction(since this also implies $p \neq q$ and so $f(r)=pqx$(not a prime))$\blacksquare$

Suppose otherwise, and let $A \leq n-2$ be minimal such that $A^2+A+n$ is not a prime. Then for any $k<A$, we have $$\gcd(A^2+A+n,k^2+k+n)=\gcd((A-k)(A+k+1), k^2+k+n).$$As $k^2+k+n$ is prime and we have $$A-k<A+k+1\leq k+n-1<k^2+k+n,$$it follows that $k^2+k+n \nmid (A-k)(A+k+1) \implies \gcd(A^2+A+n,k^2+k+n)=1$. Now, consider the least prime $p \mid A^2+A+n$. If $p \leq A$ then $$p \mid (A-p)^2+(A-p)+n \iff p \mid A^2+A+n,$$which is true. If $A+1\leq p \leq 2A$, then $$p \mid (p-(A+1))^2+(p-(A+1))+n \iff p \mid A^2+A+n,$$which is true as well. In both of these cases there therefore exists some $k<A$ with $p \mid \gcd(A^2+A+n,k^2+k+n)$, which is a contradiction. Therefore, we require $$p>2A \implies A^2+A+n\geq p(p+2)>4A(A+1) \implies n>3A^2+3A,$$but the RHS is at least $3A^2>n$, which is a contradiction. As such no $A$ exist so all the terms are prime. $\blacksquare$

FTSOC, let $\sqrt{n}{3} < m \le n-2 $ denote the smallest integer such that $m^2+m+n$ is a composite number. Then, let $ m^2+m+n = ab$ where $b > a > 1$. Note that: $$(-k-1)^2+(-k-1)+n = k^2+k+n$$is also a prime for $k < m$. Thus, for all $-m-1 < k < m$, we have: $k^2+k+n$ to be a prime. Note that: $3 m^2 > n^2$. Thus: $$m^2+m+n < 4 m^2+m < (2m+1)^2.$$Thus, we have $a < 2m+1$. Notice that: $m > m-a > -m-1$ which implies: $(m-a)^2+(m-a)+n$ is a prime. But notice that: $$(m-a)^2+(m-a)+n = m^2-2am+a^2+m-a+n = (m^2+m+n) + a^2-2am-a = ab+a^2-2am-a = a(b+a-2m-1).$$Since $a>1$ and $(m-a)^2+(m-a)+n$ is a prime, we have: $b+a-2m-1 = 1$ or $a+b = 2m+2$. Since $a+b=2m+2$ and $ab=m^2+m+n$, by AM-GM: $$\frac{a+b}{2} \ge \sqrt{ab}$$$$\implies m+1 > n$$which contradicts that $m \le n-2$. Hence proved.