1987 IMO Problems/Problem 6

Problem

Let $n$ be an integer greater than or equal to 2. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq \sqrt{n/3}$ , then $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq n - 2$ .

Solution

First observe that if $m$ is relatively prime to $b+1$ , $b+2$ , $\cdots$ , $2b$ , then $m$ is relatively prime to any number less than $2b$ . Since if $c\leq b$ , then we can choose some $i$ to make $2^ic$ lies in range $b+1,b+2,\cdots,2b$ , so $2^ic$ is relatively prime to $m$ . Hence $c$ is also. If we also have $(2b+1)^2>m$ , then we can conclude that $m$ is a prime. Since there must be a factor of $m$ less than $\sqrt{m}$ .

Let $n=3r^2+h$ where $0\leq h<6r+3$ , so $r$ is the greatest integer less than or equal to $\sqrt{n/3}$ .(to see this, just let $r=\lfloor\sqrt{n/3}\rfloor$ , then we can write $n=3(r+\epsilon)^2(0\leq\epsilon< 1)$ , so $h=6r\epsilon+3\epsilon^2\leq 6r+3$ ).

Assume that $n+k(k+1)$ is prime for $k=1,2,3\cdots,r$ . We show that $N=n+(r+s)(r+s+1)$ is prime for $s=0,1,2,\cdots,n-r-2$ . By our observation above, it is sufficient to show that $(2s+2r+t)^2>N$ and $N$ is relatively prime to all of $r+s+1,r+s+2,\cdots,2r+2s$ . We have $(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1$ . Since $s,t\ge1$ , we have $4s+1>s+2$ , $4s^2>s^2$ and $6rs>3r$ . Hence $(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N$ Now if $N$ has a factor which divides $2r-i$ in the range $-2s$ to $r-s-1$ , then so does $N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)$ which have the form $n+s'(s'+1)$ with $s'$ in range $0$ to $r$ .

1987 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last question
All IMO Problems and Solutions

Page

Toolbox

Search

1987 IMO Problems/Problem 6

Problem

Solution