2008 IMO Problems/Problem 3

(still editing...)

For each sufficiently large prime $p$ of the form $4k+1$ , we shall find a corresponding $n$ satisfying the required condition with the prime number in question being $p$ . Since there exist infinitely many such primes and, for each of them, $n \ge \sqrt{p-1}$ , we will have found infinitely many distinct $n$ satisfying the problem.

Take a prime $p$ of the form $4k+1$ and consider its "sum-of-two squares" representation $p=a^2+b^2$ , which we know to exist for all such primes. If $a=1$ or $b=1$ , then $n=b$ or $n=a$ is our guy, and $p=n^2+1 > 2n+\sqrt{2n}$ as long as $p$ (and hence $n$ ) is large enough. Let's see what happens when both $a>1$ and $b>1$ .

Since $a$ and $b$ are apparently co-prime, there must exist integers $c$ and $d$ such that $ad+bc=1.$ In fact, if $c$ and $d$ are such numbers, then $c\pm a$ and $d\mp b$ work as well, so we can assume that $c \in \left(\frac{-a}{2}, \frac{a}{2}$ (Error compiling LaTeX. Unknown error_msg).

Define $n=|ac-bd|$ and let's see what happens.

Page

Toolbox

Search

2008 IMO Problems/Problem 3