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 "1975 IMO Problems/Problem 2"

(Created page with "==Problem== Let <math>a_1, a_2, a_3, \cdots</math> be an infinite increasing sequence of positive integers. Prove that for every <math>p \geq 1</math> there are infinitely man...")
 
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
If we can find <math>p\ne q</math> such that <math>(a_p,a_q)=1</math>, we're done: every sufficiently large positive integer <math>n</math> can be written in the form <math>xa_p+ya_q,\ x,y\in\mathbb N</math>. We can thus assume there are no two such <math>p\ne q</math>. We now prove the assertion by induction on the first term of the sequence, <math>a_1</math>. The base step is basically proven, since if <math>a_1=1</math> we can take <math>p=1</math> and any <math>q>1</math> we want. There must be a prime divisor <math>u|a_1</math> which divides infinitely many terms of the sequence, which form some subsequence <math>(a_{k_n})_{n\ge 1},\ k_1=1</math>. Now apply the induction hypothesis to the sequence <math>\left(\frac{a_{k_n}}u\right)_{n\ge 1}</math>.
 +
 +
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p367494]
 +
 +
== See Also == {{IMO box|year=1975|num-b=1|num-a=3}}

Latest revision as of 15:10, 29 January 2021

Problem

Let $a_1, a_2, a_3, \cdots$ be an infinite increasing sequence of positive integers. Prove that for every $p \geq 1$ there are infinitely many $a_m$ which can be written in the form\[a_m = xa_p + ya_q\]with $x, y$ positive integers and $q > p$.

Solution

If we can find $p\ne q$ such that $(a_p,a_q)=1$, we're done: every sufficiently large positive integer $n$ can be written in the form $xa_p+ya_q,\ x,y\in\mathbb N$. We can thus assume there are no two such $p\ne q$. We now prove the assertion by induction on the first term of the sequence, $a_1$. The base step is basically proven, since if $a_1=1$ we can take $p=1$ and any $q>1$ we want. There must be a prime divisor $u|a_1$ which divides infinitely many terms of the sequence, which form some subsequence $(a_{k_n})_{n\ge 1},\ k_1=1$. Now apply the induction hypothesis to the sequence $\left(\frac{a_{k_n}}u\right)_{n\ge 1}$.

The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

See Also

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