Let $ A$ be a subset of the set $ \{1, 2,\ldots,2006\}$, consisting of $ 1004$ elements. Prove that there exist $ 3$ distinct numbers $ a,b,c\in A$ such that $ gcd(a,b)$: a) divides $ c$ b) doesn't divide $ c$
Problem
Source: JBMO Shortlist 2006
Tags: number theory, greatest common divisor, algorithm, modular arithmetic, number theory proposed
limes123
10.11.2008 22:05
a) We can always find two coprome integers b) assume theese two coprime integers are n,n+1. We can write them in the form $ 2^m\cdot l$. We see that one of them is odd and one is even. Hence if we find another even integer, their gcd will be also even, and theese two integers will be pair (a,b) and c - odd integer. Second case is when we choose all odd integers and one even. If even integer has odd divisor >1, then we take this odd integer and it's odd divisor as (a,b) and c=1. If this even number is $ 2^m$ for natural n, then we take for example (a,b)=(9,3) and $ c=2^m$. I hope there are no mistakes in my proof...
Bugi
10.11.2008 22:06
coprome=coprime? If so, should then a and b be coprime?
limes123
11.11.2008 14:25
Typo ;P coprome=corprime, we take (a,b) coprime => gcd(a,b)=1, and obviously 1|c.
Binomial-theorem
30.04.2012 22:46
a)
I will prove that there exists at least two elements $a$ and $b$ such that $\gcd(a,b)=1$ in set $A$. If I prove this, since there are $1002$ other elements, and $1$ divides all positive integers, we can choose any of the other $1002$ elements to be $c$, and we would have $\gcd(a,b)=1|c$.
Assume on the contrary that we have a subset with all pairs of numbers $a,b$ such that $\gcd(a,b)>1$. Assume $d$ is the minimal element in set $A$. Then since $\gcd(d, d-1)=1$ and $\gcd(d,d+1)=1$ by Euclid’s algorithm, we have to have the next element that can have a gcd of $1$ with $d$ being at least $d+2$. We must have a minimal last term being when we have a difference of $2$ among the terms giving us $\{d, d+2, \cdots, d+(1004-1)*2\}$ or $\{d, d+2, \cdots, d+2006\}$. Therefore $d\le 0$, but we have $d\ge 1$ from $d\in A$ so an obvious contradiction.
Therefore it is impossible for all numbers to have a gcd greater than $1$ therefore at least two have a gcd of $1$ giving us $1|c$ and our proof is complete.
b)
First off remark that we can’t have $A$ containing all even numbers or all odd numbers. If we did, then $A$ would have to have at most $1003$ elements (from the set $\{1, 3, 5, \cdots, 2005\}$ and $\{2, 4, \cdots , 2006\}$ having $1003$ elements) implying that we must have at least one element that is the opposite parity of the rest. We have three cases:
Case 1: 1003 odds, 1 even
Since there are $1003$ odd numbers, we have all the numbers $\{1, 3, 5, 7, 9, 11, \cdots 2005\}$ being a part of $A$. Let $a=3, b=9$ and $c=5$ giving us an obvious contradiction since $3$ does not divide $5$.
Case 2: At least two evens and odds
Let $a$ and $b$ both be even and let $c$ be odd. Therefore letting $\gcd(a,b)=2a'$ and $c=2c'+1$, we must have $2a'|(2c'+1)$. However, $(2c'+1)\equiv 1\pmod 2$ giving us an obvious contradiction since we can’t have $\gcd(a,b)$ dividing $c$.
Case 3: 1 odd, 1003 evens
Again, let $c$ be the odd number and $a$ and $b$ be two even numbers. The proof of this is the same as the proof for case 2, since an even number can’t divide an odd number.
--
Since we have accounted for all cases, our proof is complete $\blacksquare$.