Art of Problem Solving
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

2016 IMO Problems/Problem 4: Difference between revisions

← Older edit
Apple jack2005 (talk | contribs)
editor
1 edit
Quacksaysduck (talk | contribs)
editor
9 edits
 
Line 4: Line 4:


==Solution==
==Solution==
{{solution}}
Consider <math>P(x)</math> and <math>P(x+y)</math>. We note that in order to <math>p \mid P(x)</math> and <math>p \mid P(x+y)-P(x)</math> we must have <math>p \mid x^2+x+1</math> and <math>p \mid y(2x+y+1)</math>. It is obvious that <math>p \equiv 1 \pmod{6}</math> since <math>p \mid n^2+n+1 \mid (2n+1)^2+3</math> or <math>\left( \tfrac{-3}{p} \right)=1</math>.
Consider <math>P(x)</math> and <math>P(x+y)</math>. We note that in order to <math>p \mid P(x)</math> and <math>p \mid P(x+y)-P(x)</math> we must have <math>p \mid x^2+x+1</math> and <math>p \mid y(2x+y+1)</math>. It is obvious that <math>p \equiv 1 \pmod{6}</math> since <math>p \mid n^2+n+1 \mid (2n+1)^2+3</math> or <math>\left( \tfrac{-3}{p} \right)=1</math>.


Latest revision as of 03:18, 26 March 2024

Problem

A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible positive integer value of $b$ such that there exists a non-negative integer $a$ for which the set $\{P(a+1),P(a+2),\ldots,P(a+b)\}$ is fragrant?

Solution

Consider $P(x)$ and $P(x+y)$. We note that in order to $p \mid P(x)$ and $p \mid P(x+y)-P(x)$ we must have $p \mid x^2+x+1$ and $p \mid y(2x+y+1)$. It is obvious that $p \equiv 1 \pmod{6}$ since $p \mid n^2+n+1 \mid (2n+1)^2+3$ or $\left( \tfrac{-3}{p} \right)=1$.

If $y=1$ then $p \mid 2x+2$ implies $p \mid x+1$. WLOG, we can let $x=p-1$ and see that $p \nmid x^2+x+1$. So there doesn't exists $x$ so that $\gcd \left( P(x),P(x+1) \right)>1$.

If $y=2$, we find $p \mid 2x+3$ and we let $x=\tfrac{p-3}{2}$. Hence, from $p \mid x^2+x+1$ we get $p=7$. So there is one prime $p=7$ such that $\gcd \left( P(x),P(x+2) \right)>1$.

If $y=3$, it is obvious that $p=3$ satisfy and is the only answer.

If $y=4$, we do the similar thing and get $p \mid 2x+5$ and $p \mid x^2+x+1$ so $p=19$. ___________________________ Now, back to the problem, since there doesn't exists any prime $p$ for $y=1$ so $b \ge 3$. The only prime for $y=2$ is $p=7$ so if we choose $7 \mid P(x+1), 7 \mid P(x+3)$ then there will be a number $7 \nmid P(x+2)$ remains. This means $b \ge 5$ since we need a prime $p \mid P(x+2)$ and $p \mid P(x+y)$ but $y \ge 5$ since $p \ne 7$.

If $b=5$, we consider two cases, where there are two numbers that are divisible by $19$ (which means $19 \mid P(x+1), 19 \mid P(x+5)$), the middle-three numbers $P(x+2),P(x+3),P(x+4)$ we can't find a way make each two of them have common prime factor. If no two are divisible by $19$ then they can only be divisible by $7,3$, but it can't cover all $5$ "consecutive" numbers.

If $b=6$ then we can pick $19 \mid P(x+2),P(x+6), 3 \mid P(x+1), P(x+4), 7 \mid P(x+3), 7 \mid P(x+5)$.

So the final answer is $b=6$.

See Also

2016 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2016_IMO_Problems/Problem_4&oldid=217429"