Difference between revisions of "2008 IMO Problems/Problem 3"
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 | 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> | <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 | + | 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>. | 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 | + | 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>. |
Revision as of 21:20, 3 September 2008
(still editing...)
The main idea is to take a gaussian prime and multiply it by a "twice 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 (obviously) 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 .
Define and let's see what happens. Notice that .
If , then from (1), we get $a\2$ (Error compiling LaTeX. Unknown error_msg) and hence . That means that $\ds d=-\frac{b-1}{2}$ (Error compiling LaTeX. Unknown error_msg) and . Therefore, and so , from where $\ds b > \sqrt{2n}+\frac{1}{2}$ (Error compiling LaTeX. Unknown error_msg). Finally, and the case $\ds c=\pm\frac{a}{2}$ (Error compiling LaTeX. Unknown error_msg) is cleared.
We can safely assume now that Automatically, .