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>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>. | ||
− | + | 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 and multiply it by a "smaller"
to get
. The rest is just making up the little details.
For each sufficiently large prime of the form
, we shall find a corresponding
satisfying the required condition with the prime number in question being
. Since there exist infinitely many such primes and, for each of them,
, we will have found infinitely many distinct
satisfying the problem.
Take a prime of the form
and consider its "sum-of-two squares" representation
, which we know to exist for all such primes. If
or
, then
or
is our guy, and
as long as
(and hence
) is large enough. Let's see what happens when both
and
.
Since and
are apparently co-prime, there must exist integers
and
such that
In fact, if
and
are such numbers, then
and
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 and let's see what happens. Notice that
.
If , then