Difference between revisions of "1975 IMO Problems/Problem 2"

Latest revision as of 08:52, 13 January 2025

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]

This is flawed. At Least it is not clearly shown how a sequence with infinite number of terms that are coprime to a(p) is achieved by simply repeating the procedure as described. Following proof would be much more convincing. For every p>=1 we calculate the remainder of each term of the sequence modulo a(p) and we will have a(p) types of remainders: 1~a(p). There are infinitely many terms and limited types of remainders therefore, there must be one remainder which belongs to infinitely many terms. Let it be r, 1<=r<=a(p), the first term of such remainder be a(q) and the subsequent terms be a(m), m towards infinity. Obviously a(m)>a(q)>=a(p)+1, and m>q>p. Pick any a(m)>a(q), we now prove that it can always be written in the form a(m)=xa(p)+ya(q). Let a(q)=k1•a(p)+r, a(m)=k2•a(p)+r, k2>k1. Then a(m)-a(q)=(k2-k1)a(p), a(m)=(k2-k1)a(p)+1•a(q). Let x=k2-k1, y=1, and obviously both are positive integers so we have achieved the target form. As there are infinitely many a(m), for every p>=1, we will always have infinitely many a(m) which can be written in the target form. Done.

1975 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "1975 IMO Problems/Problem 2"

Latest revision as of 08:52, 13 January 2025

Problem

Solution

See Also

@@ Line 8: / Line 8: @@
 == See Also == {{IMO box|year=1975|num-b=1|num-a=3}}
+This is flawed. At Least it is not clearly shown how a sequence with infinite number of terms that are coprime to a(p) is achieved by simply repeating the procedure as described. Following proof would be much more convincing.
+For every p>=1 we calculate the remainder of each term of the sequence modulo a(p) and we will have a(p) types of remainders: 1~a(p). There are infinitely many terms and limited types of remainders therefore, there must be one remainder which belongs to infinitely many terms. Let it be r, 1<=r<=a(p), the first term of such remainder be a(q) and the subsequent terms be a(m), m towards infinity. Obviously a(m)>a(q)>=a(p)+1, and m>q>p. Pick any a(m)>a(q), we now prove that it can always be written in the form a(m)=xa(p)+ya(q). Let a(q)=k1•a(p)+r, a(m)=k2•a(p)+r, k2>k1. Then a(m)-a(q)=(k2-k1)a(p), a(m)=(k2-k1)a(p)+1•a(q). Let x=k2-k1, y=1, and obviously both are positive integers so we have achieved the target form. As there are infinitely many a(m), for every p>=1, we will always have infinitely many a(m) which can be written in the target form. Done.