Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 IMO Problems/Problem 3"
Line 3: Line 3:
 
The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "twice as small" <math>c+di</math> to get <math>n+i</math>. The rest is just making up the little details.
 
The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "twice as small" <math>c+di</math> to get <math>n+i</math>. The rest is just making up the little details.
  
−
For each sufficiently large prime <math>p</math> of the form <math>4k+1</math>, we shall find a corresponding <math>n</math> satisfying the required condition with the prime number in question being <math>p</math>. Since there exist infinitely many such primes and, for each of them, <math>n \ge \sqrt{p-1}</math>, we will have found infinitely many distinct <math>n</math> satisfying the problem.
+
For each {\em sufficiently large} prime <math>p</math> of the form <math>4k+1</math>, we shall find a corresponding <math>n</math> satisfying the required condition with the prime number in question being <math>p</math>. Since there exist infinitely many such primes and, for each of them, <math>n \ge \sqrt{p-1}</math>, we will have found infinitely many distinct <math>n</math> satisfying the problem.
  
 
Take a prime <math>p</math> of the form <math>4k+1</math> and consider its "sum-of-two squares" representation <math>p=a^2+b^2</math>, which we know to exist for all such primes. As <math>a\ne b</math>, assume without loss of generality that <math>b>a</math>. If <math>a=1</math>, then <math>n=b</math> is our guy, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Let's see what happens when <math>b>a>1</math>.
 
Take a prime <math>p</math> of the form <math>4k+1</math> and consider its "sum-of-two squares" representation <math>p=a^2+b^2</math>, which we know to exist for all such primes. As <math>a\ne b</math>, assume without loss of generality that <math>b>a</math>. If <math>a=1</math>, then <math>n=b</math> is our guy, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Let's see what happens when <math>b>a>1</math>.
Line 23: Line 23:
 
<cmath>|d| \le \frac{b-1}{2}.</cmath>
 
<cmath>|d| \le \frac{b-1}{2}.</cmath>
  
−
<cmath><cmath>n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right).</cmath> </cmath>
+
<cmath></cmath>n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right).<cmath> </cmath>
  
−
Before we proceed, we would like to show that <math>a+b-1 > \sqrt{p}</math>. Observe that the function <math>x+\sqrt{p-x^2}</math> over <math>x\in(2,\sqrt{p-4})</math> reaches its minima on the ends, so <math>a+b</math> given <math>a^2+b^2=p</math> is minimized for <math>a = 2</math>, where it equals <math>2+\sqrt{p-2^2}</math>. So we want to show that, for big <math>p</math>, <cmath>2+\sqrt{p-4} > \sqrt{p} + 1 \Leftrightarrow\ \sqrt{p-4}>\sqrt{p}-1,</cmath>
+
Before we proceed, we would like to show that <math>a+b-1 > \sqrt{p}</math>. Observe that the function <math>x+\sqrt{p-x^2}</math> over <math>x\in(2,\sqrt{p-4})</math> reaches its minima on the ends, so <math>a+b</math> given <math>a^2+b^2=p</math> is minimized for <math>a = 2</math>, where it equals <math>2+\sqrt{p-2^2}</math>. So we want to show that <cmath>2+\sqrt{p-4} > \sqrt{p} + 1,</cmath>
−
which becomes obvious upon squaring boht sides.
+
which obviously holds for large <math>p</math>.
  
 
Now armed with <math>a+b-1>\sqrt{p}</math> and (2), we get
 
Now armed with <math>a+b-1>\sqrt{p}</math> and (2), we get
−
<cmath>4(n^2+1) \le p( p - 2(a+b-1) ) \le p( p-2\sqrt{p} ) < u^2(u-1)^2,</cmath>
+
<cmath>4(n^2+1) \le p( a^2+b^2 - 2(a+b-1) ) \le p( p-2\sqrt{p} ) < u^2(u-1)^2,</cmath>
 
where <math>u=\sqrt{p}.</math>
 
where <math>u=\sqrt{p}.</math>
 +
 +
Finally,
 +
<cmath>u^2(u-1)^2 > 4n^2+4 > 4n^2\Lefetarrow \
 +
u(u-1) > 2n \Leftarrow u > \sqrt{2n} + \frac{1}{2} \Lefetarrow \
 +
p = u^2 > 2n + \sqrt{2n}.</cmath>

Revision as of 00:05, 4 September 2008

(still editing...)

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

For each {\em 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. As $a\ne b$, assume without loss of generality that $b>a$. If $a=1$, then $n=b$ 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 $b>a>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 ma$ and $d\mp mb$ work as well for any integer $m$, 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 see that $a$ must divide $2$ and hence $a=2$. In turn, $d=-\frac{b-1}{2}$ 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 $b > \sqrt{2n}+\frac{1}{2}$. Finally, $p=b^2+2^2 > 2n+\sqrt{2n}$ and the case $c=\pm\frac{a}{2}$ is cleared.

We can safely assume now that \[|c| \le \frac{a-1}{2}.\] As $b>a>1$ implies $b>2$, we have \[|d| = \left|\frac{1-bc}{a}\right| \le \frac{b(a-1)+2}{2a} < \frac{ba}{2a} = \frac{b}{2},\] so \[|d| \le \frac{b-1}{2}.\]

\[\]n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right).\[\]

Before we proceed, we would like to show that $a+b-1 > \sqrt{p}$. Observe that the function $x+\sqrt{p-x^2}$ over $x\in(2,\sqrt{p-4})$ reaches its minima on the ends, so $a+b$ given $a^2+b^2=p$ is minimized for $a = 2$, where it equals $2+\sqrt{p-2^2}$. So we want to show that \[2+\sqrt{p-4} > \sqrt{p} + 1,\] which obviously holds for large $p$.

Now armed with $a+b-1>\sqrt{p}$ and (2), we get \[4(n^2+1) \le p( a^2+b^2 - 2(a+b-1) ) \le p( p-2\sqrt{p} ) < u^2(u-1)^2,\] where $u=\sqrt{p}.$

Finally, 

\[u^2(u-1)^2 > 4n^2+4 > 4n^2\Lefetarrow \\ 
u(u-1) > 2n \Leftarrow u > \sqrt{2n} + \frac{1}{2} \Lefetarrow \\
p = u^2 > 2n + \sqrt{2n}.\] (Error compiling LaTeX. Unknown error_msg)
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_IMO_Problems/Problem_3&oldid=27741"