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 1: Line 1:
 
(still editing...)
 
(still editing...)
 +
 +
The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "smaller" <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 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.
Line 6: Line 8:
  
 
Since <math>a</math> and <math>b</math> are apparently co-prime, there must exist integers <math>c</math> and <math>d</math> such that
 
Since <math>a</math> and <math>b</math> are apparently co-prime, there must exist integers <math>c</math> and <math>d</math> such that
−
<cmath>ad+bc=1.</cmath>
+
<cmath>ad+bc=1 \eqno{"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}</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}\left)</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>.
  
−
Define <math>n=|ac-bd|</math> and let's see what happens.
+
If <math>c=\pm\frac{a}{2}</math>, then

Revision as of 21:50, 3 September 2008

(still editing...)

The main idea is to take a gaussian prime $a+bi$ and multiply it by a "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 apparently co-prime, there must exist integers $c$ and $d$ such that \[ad+bc=1 \eqno{"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}\left)$ (Error compiling LaTeX. Unknown error_msg).

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_IMO_Problems/Problem_3&oldid=27730"