Difference between revisions of "2008 IMO Problems/Problem 3"

Revision as of 22:20, 3 September 2008

(still editing...)

The main idea is to take a gaussian prime $a+bi$ and multiply it by a "twice smaller" $c+di$ to get $n+i$ . The rest is just making up the little details.

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 (obviously) co-prime, there must exist integers $c$ and $d$ such that $ad+bc=1 \leqno{(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}\right]$ .

Define $n=|ac-bd|$ and let's see what happens. Notice that $(a^2+b^2)(c^2+d^2)=n^2+1$ .

If $c=\pm\frac{a}{2}$ , then from (1), we get $a\2$ (Error compiling LaTeX. Unknown error_msg) and hence $a=2$ . That means that $\ds d=-\frac{b-1}{2}$ (Error compiling LaTeX. Unknown error_msg) and $n=\frac{b(b-1)}{2}-2$ . Therefore, $b^2-b=2n+4>2n$ and so $\left(b-\frac{1}{2}\right)^2>2n$ , from where $\ds b > \sqrt{2n}+\frac{1}{2}$ (Error compiling LaTeX. Unknown error_msg). Finally, $p=b^2+2^2 > 2n+\sqrt{2n}$ and the case $\ds c=\pm\frac{a}{2}$ (Error compiling LaTeX. Unknown error_msg) is cleared.

We can safely assume now that $|c| \le \frac{a-1}{2}.$ Automatically, $d \le \frac{b-1}{2}$ .

@@ Line 9: / Line 9: @@
 Since <math>a</math> and <math>b</math> are (obviously) co-prime, there must exist integers <math>c</math> and <math>d</math> such that
 <cmath>ad+bc=1 \leqno{(1)}</cmath>
-In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm a</math> and <math>d\mp b</math> work as well, so we can assume that <math>c \in \left(\frac{-a}{2}, \frac{a}{2}\right)</math>.
+In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm a</math> and <math>d\mp b</math> work as well, so we can assume that <math>c \in \left[-\frac{a}{2}, \frac{a}{2}\right]</math>.
 Define <math>n=|ac-bd|</math> and let's see what happens. Notice that <math>(a^2+b^2)(c^2+d^2)=n^2+1</math>.
-If <math>c=\pm\frac{a}{2}</math>, then from (1), we get <math>a/2</math> and hence <math>a=2</math>. That means that <math>d=-\frac{b-1}{2}</math> and <math>n=\frac{b(b-1)}{2}-2</math>. Therefore, <math>b^2-b=2n+4>2n</math> and so <math>\left(b-\frac{1}{2}\right)>2n</math>, from where <math>b > \sqrt{2n}+\frac{1}{2}</math>. Finally, <math>p=b^2+2^2 > 2n+\sqrt{2n}</math> and the case <math>a=2</math> is cleared.
+If <math>c=\pm\frac{a}{2}</math>, then from (1), we get <math>a\2</math> and hence <math>a=2</math>. That means that <math>\ds d=-\frac{b-1}{2}</math> and <math>n=\frac{b(b-1)}{2}-2</math>. Therefore, <math>b^2-b=2n+4>2n</math> and so <math>\left(b-\frac{1}{2}\right)^2>2n</math>, from where <math>\ds b > \sqrt{2n}+\frac{1}{2}</math>. Finally, <math>p=b^2+2^2 > 2n+\sqrt{2n}</math> and the case <math>\ds c=\pm\frac{a}{2}</math> is cleared.
+We can safely assume now that
+<cmath>|c| \le \frac{a-1}{2}.</cmath>
+Automatically, <math>d \le \frac{b-1}{2}</math>.

Page

Toolbox

Search

Difference between revisions of "2008 IMO Problems/Problem 3"

Revision as of 22:20, 3 September 2008