Difference between revisions of "2008 IMO Problems/Problem 3"
(31 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | + | == Problem == | |
+ | Prove that there are infinitely many positive integers <math>n</math> such that <math>n^{2} + 1</math> has a prime divisor greater than <math>2n + \sqrt {2n}</math>. | ||
− | + | == Solutions == | |
− | 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. If <math>a=1</math> | + | '''Solution 1''' |
+ | |||
+ | 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> such that <math>p</math> divides <math>n^2+1</math> and <math>p>2n+\sqrt{2n}</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 hypothesis. | ||
+ | |||
+ | 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 what we are looking for, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Assume from now on that <math>b>a>1</math>. | ||
+ | |||
+ | 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. \quad(1)</cmath> | ||
+ | In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm ma</math> and <math>d\mp mb</math> work as well for any integer <math>m</math>, 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 why this is a good choice. For starters, notice that <math>(a^2+b^2)(c^2+d^2)=n^2+1</math>. | ||
+ | |||
+ | If <math>c=\pm\frac{a}{2}</math>, from (1) we see that <math>a</math> must divide <math>2</math> and hence <math>a=2</math>. This implies, <math>d=-\frac{b-1}{2}</math> and <math>n=\frac{b(b-1)}{2}-2</math>. Therefore, | ||
+ | <math>\left(b-\frac{1}{2}\right)^2 = 1/4 + 2(n+2) > 2n</math>, so <math>b > \sqrt{2n}+\frac{1}{2}</math>. Finally, <math>p=b^2+2^2 > 2n+\sqrt{2n}</math> and the case <math>c=\pm\frac{a}{2}</math> is cleared. | ||
+ | |||
+ | We can safely assume now that | ||
+ | <cmath>|c| \le \frac{a-1}{2}.</cmath> | ||
+ | As <math>b>a>1</math> implies <math>b>2</math>, we have | ||
+ | <cmath>|d| = \left|\frac{1-bc}{a}\right| \le \frac{b(a-1)+2}{2a} < \frac{ba}{2a} = \frac{b}{2},</cmath> | ||
+ | so | ||
+ | <cmath>|d| \le \frac{b-1}{2}.</cmath> | ||
+ | |||
+ | Therefore, | ||
+ | <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). \quad (2)</cmath> | ||
+ | |||
+ | Before we proceed, we would like to show first 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 is not hard to show for ''large enough'' <math>p</math>. | ||
+ | |||
+ | Now armed with <math>a+b-1>\sqrt{p}</math> and (2), we get | ||
+ | <cmath>4(n^2+1)\le p( a^2+b^2 - 2(a+b-1) )< p( p-2\sqrt{p} )< u^2(u-1)^2,</cmath> | ||
+ | where <math>u=\sqrt{p}.</math> | ||
+ | |||
+ | Finally, | ||
+ | <cmath>u^2(u-1)^2 > 4n^2+4 > 4n^2\Rightarrow | ||
+ | u(u-1) > 2n \Rightarrow | ||
+ | (u-\frac{1}{2})^2 > 2n+\frac{1}{4} > 2n \Rightarrow | ||
+ | u > \sqrt{2n} + \frac{1}{2} \Rightarrow | ||
+ | p = u^2 > 2n + \sqrt{2n}.</cmath> | ||
+ | The proof is complete. | ||
+ | |||
+ | '''Solution 2''' | ||
+ | |||
+ | We begin with a lemma. | ||
+ | |||
+ | Lemma: For every prime <math>p \equiv 1 \mod{4}</math>, there exists a positive integer <math>n \le \dfrac{p - \sqrt{p-4}}{2}</math> such that <math>p\mid n^2 + 1</math>. | ||
+ | |||
+ | Proof: | ||
+ | We know that there must be a solution <math>x</math> to the equation | ||
+ | <cmath>x^2+1 \equiv 0 \mod{p}</cmath> | ||
+ | with <math>1 \le x \le p-1</math>. However, if <math>x</math> is a solution then so is <math>p-x</math>, so there must be a solution <math>x \le p-1</math>. Let <math>n</math> denote this solution and suppose that <math>n = \frac{p-k}{2}</math>. Then, we have | ||
+ | <cmath>\left(\dfrac{p-k}{2}\right)^2 \equiv -1 \mod{p}</cmath> | ||
+ | <cmath>k^2 \equiv -4 \mod{p}.</cmath> | ||
+ | Since <math>k</math> is a positive integer, it follows that <math>k^2 \ge p-4</math>, so we have | ||
+ | <cmath>n \le \dfrac{p - \sqrt{p-4}}{2},</cmath> | ||
+ | as desired. The lemma is proven. | ||
+ | |||
+ | |||
+ | |||
+ | Suppose for sake of contradiction that there are only finitely many integers <math>n_1,n_2,\dots,n_k</math> that work. Let <math>p \equiv 1 \mod{4}</math> be a prime with <math>p>20</math> and such that <math>p</math> is relatively prime to <math>n_i^2+1</math> for all <math>i</math> (the existence of <math>p</math> is guaranteed by the existence of infinitely many primes of the form <math>4k+1</math>). Then, we know that there exists an <math>N</math> such that <math>N\le \dfrac{p - \sqrt{p-4}}{2}</math> and <math>p | N^2 + 1</math> (this last condition shows that <math>N</math> is not among <math>n_1,n_2,\dots,n_k</math>. We want to show that | ||
+ | <cmath>p > 2N + \sqrt{2N}</cmath> | ||
+ | <cmath>p - 2N > \sqrt{2N}.</cmath> | ||
+ | But, we know that <math>p-2N \ge \sqrt{p-4}</math>, so it suffices to show that | ||
+ | <cmath>p-4 > 2N</cmath> | ||
+ | <cmath>p - 2N > 4.</cmath> | ||
+ | Once again, it suffices to show that | ||
+ | <cmath>\sqrt{p-4} > 4,</cmath> | ||
+ | which follows from <math>p>20</math>. | ||
+ | |||
+ | Thus, <math>N</math> satisfies the required condition and it follows that there exist infinitely many values of <math>n</math> that satisfy the given condition, as desired. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2008|num-b=2|num-a=4}} |
Latest revision as of 01:09, 19 November 2023
Problem
Prove that there are infinitely many positive integers such that
has a prime divisor greater than
.
Solutions
Solution 1
The main idea is to take a gaussian prime and multiply it by a "twice as small"
to get
. The rest is just making up the little details.
For each sufficiently large prime of the form
, we shall find a corresponding
such that
divides
and
. Since there exist infinitely many such primes and, for each of them,
, we will have found infinitely many distinct
satisfying the hypothesis.
Take a prime of the form
and consider its "sum-of-two squares" representation
, which we know to exist for all such primes. As
, assume without loss of generality that
. If
, then
is what we are looking for, and
as long as
(and hence
) is large enough. Assume from now on that
.
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 for any integer
, so we can assume that
.
Define and let's see why this is a good choice. For starters, notice that
.
If , from (1) we see that
must divide
and hence
. This implies,
and
. Therefore,
, so
. Finally,
and the case
is cleared.
We can safely assume now that
As
implies
, we have
so
Therefore,
Before we proceed, we would like to show first that . Observe that the function
over
reaches its minima on the ends, so
given
is minimized for
, where it equals
. So we want to show that
which is not hard to show for large enough
.
Now armed with and (2), we get
where
Finally,
The proof is complete.
Solution 2
We begin with a lemma.
Lemma: For every prime , there exists a positive integer
such that
.
Proof:
We know that there must be a solution to the equation
with
. However, if
is a solution then so is
, so there must be a solution
. Let
denote this solution and suppose that
. Then, we have
Since
is a positive integer, it follows that
, so we have
as desired. The lemma is proven.
Suppose for sake of contradiction that there are only finitely many integers that work. Let
be a prime with
and such that
is relatively prime to
for all
(the existence of
is guaranteed by the existence of infinitely many primes of the form
). Then, we know that there exists an
such that
and
(this last condition shows that
is not among
. We want to show that
But, we know that
, so it suffices to show that
Once again, it suffices to show that
which follows from
.
Thus, satisfies the required condition and it follows that there exist infinitely many values of
that satisfy the given condition, as desired.
See Also
2008 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |