In a sequence of $34$ odd integers $a_1,a_2, \cdots , a_{34}$ between $1$ and $100$ there exist $i \neq j$ such that $a_i\mid a_j$.

Question

In a sequence of $34$ odd integers $a_1,a_2, \cdots , a_{34}$ between $1$ and $100$ there exist $i \neq j$ such that $a_i \mid a_j$.

My attempt $:$

If one of the $34$ odd integers be $1$ we are clearly done with the proof. Otherwise $a_i \geq 3$ for all $i=1,2, \cdots , 34$. By division algorithm $a_i=3m_i + r_i$ for $0 \leq r_i \leq 2$. Since $3 \leq a_i \leq 100$ it is clear that $1 \leq m_i \leq 33$. Since we have $34$ integers by Pigeonhole principle there exist $i < j$ such that $m_i = m_j= k$ (say). Then $a_i = 3k + r_i$ and $a_j = 3k + r_j$. If $k$ is even then both of $r_i$ and $r_j$ should be odd since both of $a_i$ and $a_j$ are odd. Since $0 \leq r_i \leq 2$ and $0 \leq r_j \leq 2$. So we have $r_i=r_j=1$ in this case. Which implies $a_i=a_j$ and hence clearly $a_i \mid a_j$ which proves the claim. But I find difficulty when $k$ is odd.

How do I tackle this case? Please help me in this regard.

Thank you very much.

Answer 1

Consider the prime factorization of $a_i$ as $$a_i=3^{k_i}.r_i,\ \mathrm {for}\ i=1,2, \cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i \neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i \leq k_j$. Then clearly $a_i \mid a_j$ and we are done with the proof.

Answer 2

WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^{k_i}r_i$ where $3^{k_i}||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form $$r_i=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$$ Where $p_i$s are primes less than $100$ but more than $3$ and $\alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?

Answer 3

There are $50$ odd numbers $n$ in the range $1\le n\le100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $b\mid a$, by the Pigeonhole Principle.