Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1987 IMO Problems/Problem 6"

(creation)
 
m (http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln876.html)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
First observe that if <math>m</math> is relatively prime to <math>b+1</math>, <math>b+2</math>, <math>\cdots</math>, <math>2b</math>, then <math>m</math> is relatively prime to any number less than <math>2b</math>. Since if <math>c\leq b</math>, then we can choose some <math>i</math> to make <math>2^ic</math> lies in range <math>b+1,b+2,\cdots,2b</math>, so <math>2^ic</math> is relatively prime to <math>m</math>. Hence <math>c</math> is also. If we also have <math>(2b+1)^2>m</math>, then we can conclude that <math>m</math> is a prime. Since there must be a factor of <math>m</math> less than <math>\sqrt{m}</math>.
 +
 
 +
Let <math>n=3r^2+h</math> where <math>0\leq h<6r+3</math>, so <math>r</math> is the greatest integer less than or equal to <math>\sqrt{n/3}</math>.(to see this, just let <math>r=\lfloor\sqrt{n/3}\rfloor</math>, then we can write <math>n=3(r+\epsilon)^2(0\leq\epsilon< 1)</math>, so <math>h=6r\epsilon+3\epsilon^2\leq 6r+3</math>).
 +
 
 +
Assume that <math>n+k(k+1)</math> is prime for <math>k=1,2,3\cdots,r</math>. We show that <math>N=n+(r+s)(r+s+1)</math> is prime for <math>s=0,1,2,\cdots,n-r-2</math>. By our observation above, it is sufficient to show that <math>(2s+2r+t)^2>N</math> and <math>N</math> is relatively prime to all of <math>r+s+1,r+s+2,\cdots,2r+2s</math>. We have <math>(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1</math>. Since <math>s,t\ge1</math>, we have <math>4s+1>s+2</math>, <math>4s^2>s^2</math> and <math>6rs>3r</math>. Hence <cmath>(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N</cmath>.
 +
Now if <math>N</math> has a factor which divides <math>2r-i</math> int the range <math>-2s</math> to <math>r-s-1</math>, then so does <math>N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)</math> which have the form <math>n+s'(s'+1)</math> with <math>s'</math> in range <math>0</math> to <math>r</math>.
  
 
{{IMO box|num-b=5|after=Last question|year=1987}}
 
{{IMO box|num-b=5|after=Last question|year=1987}}
−
 
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 10:36, 15 November 2013

Problem

Let $n$ be an integer greater than or equal to 2. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq \sqrt{n/3}$, then $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq n - 2$.

Solution

First observe that if $m$ is relatively prime to $b+1$, $b+2$, $\cdots$, $2b$, then $m$ is relatively prime to any number less than $2b$. Since if $c\leq b$, then we can choose some $i$ to make $2^ic$ lies in range $b+1,b+2,\cdots,2b$, so $2^ic$ is relatively prime to $m$. Hence $c$ is also. If we also have $(2b+1)^2>m$, then we can conclude that $m$ is a prime. Since there must be a factor of $m$ less than $\sqrt{m}$.

Let $n=3r^2+h$ where $0\leq h<6r+3$, so $r$ is the greatest integer less than or equal to $\sqrt{n/3}$.(to see this, just let $r=\lfloor\sqrt{n/3}\rfloor$, then we can write $n=3(r+\epsilon)^2(0\leq\epsilon< 1)$, so $h=6r\epsilon+3\epsilon^2\leq 6r+3$).

Assume that $n+k(k+1)$ is prime for $k=1,2,3\cdots,r$. We show that $N=n+(r+s)(r+s+1)$ is prime for $s=0,1,2,\cdots,n-r-2$. By our observation above, it is sufficient to show that $(2s+2r+t)^2>N$ and $N$ is relatively prime to all of $r+s+1,r+s+2,\cdots,2r+2s$. We have $(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1$. Since $s,t\ge1$, we have $4s+1>s+2$, $4s^2>s^2$ and $6rs>3r$. Hence \[(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N\]. Now if $N$ has a factor which divides $2r-i$ int the range $-2s$ to $r-s-1$, then so does $N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)$ which have the form $n+s'(s'+1)$ with $s'$ in range $0$ to $r$.

1987 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_IMO_Problems/Problem_6&oldid=57694"