# Difference between revisions of "2008 IMO Problems/Problem 3"

(→Solution: added a second solution) |
|||

Line 3: | Line 3: | ||

== Solution == | == Solution == | ||

+ | |||

+ | '''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. | 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. | ||

Line 46: | Line 49: | ||

p = u^2 > 2n + \sqrt{2n}.</cmath> | p = u^2 > 2n + \sqrt{2n}.</cmath> | ||

The proof is complete.--[[User:Vbarzov|Vbarzov]] 03:02, 5 September 2008 (UTC) | The proof is complete.--[[User:Vbarzov|Vbarzov]] 03:02, 5 September 2008 (UTC) | ||

+ | |||

+ | '''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 | 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{4}</cmath> | ||

+ | <cmath>k^2 \equiv -4 \mod{4}.</cmath> | ||

+ | Since <math>k</math> is a positive integer, it follows that <math>k \ge p-4</math>, so we have | ||

+ | <cmath>n \le \dfrac{p - \sqrt{p-4}}{2},</cmath> | ||

+ | as desired. | ||

+ | |||

+ | 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. |

## Revision as of 20:22, 30 May 2011

## Problem

Prove that there are infinitely many positive integers such that has a prime divisor greater than .

## Solution

**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

\[4(n^2+1) & \le p( a^2+b^2 - 2(a+b-1) ) \\ & < p( p-2\sqrt{p} ) \\ & < u^2(u-1)^2,\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)

where

Finally, The proof is complete.--Vbarzov 03:02, 5 September 2008 (UTC)

**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.

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.