Let $n\ge2$ be an integer. Prove that if $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le\sqrt{n\over3}$, then $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le n-2$.(IMO Problem 6) Original Formulation Let $f(x) = x^2 + x + p$, $p \in \mathbb N.$ Prove that if the numbers $f(0), f(1), \cdots , f(\sqrt{p\over 3} )$ are primes, then all the numbers $f(0), f(1), \cdots , f(p - 2)$ are primes. Proposed by Soviet Union.
Problem
Source:
Tags: number theory, polynomial, prime numbers, quadratics, IMO Shortlist, IMO, IMO 1987
Rust
19.08.2010 22:48
Let $f(k)=k^2+k+n$. If $p|f(k)$, then $p|f(p-k-1)=p (p-2k-1)+f(k)$. Let $p$ is minimal prime divisor $f(k),k<n-1$. If $f(k$ is not prime, then we can take $k\le \frac{p-1}{2}$ and $p^2\le f(k)$. It equavalent to $p\le\sqrt{\frac{4n-1}{3}}\to k<\sqrt{\frac{n}{3}}$ - contradiction. Therefore ,minimal prime divisor of $f(k) is $n$ and $f(k)$ are prime for $k<n-1$, $f(n-1)=n^2$ - first not prime mean.
mathmdmb
21.08.2010 10:10
Will you please edit this,a misplaced dollar sign.
Amir Hossein
21.08.2010 10:24
Rust wrote: Let $f(k)=k^2+k+n$. If $p|f(k)$, then $p|f(p-k-1)=p (p-2k-1)+f(k)$. Let $p$ is minimal prime divisor $f(k),k<n-1$. If $f(k$ is not prime, then we can take $k\le \frac{p-1}{2}$ and $p^2\le f(k)$. It equavalent to $p\le\sqrt{\frac{4n-1}{3}}\to k<\sqrt{\frac{n}{3}}$ - contradiction. Therefore ,minimal prime divisor of $f(k)$ is $n$ and $f(k)$ are prime for $k<n-1$, $f(n-1)=n^2$ - first not prime mean.
Zhero
31.08.2010 21:03
Posted before here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366550&sid=7dcc538170006d22135bb1e761a3c1a7#p366550