### miracle_jr's blog

By miracle_jr, history, 5 weeks ago,

Hi, I was reading the editorial of the Half Sequence problem from recent cookoff. One of the statements has been left for readers to prove and I am unable to prove it. The statement is as follows.

"Observe that any single number less then 1e9 can be made up of atmost 9 distinct prime numbers. This means that if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist atleast one subset of length at most 9 whose elements have GCD=1. (Proof left as an exercise)"

I have trouble understanding the last line. Why must there exist that subset?

• +13

 » 5 weeks ago, # | ← Rev. 2 →   +16 Each single number made up of at most 9 distinct prime numbers does not infer if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist at least one subset of length at most 9 whose elements have GCD = 1. For example, let $a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$, $p = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29$, and for each $i$, $b_i = \frac{p}{a}$. The GCD of $b_1, b_2, \dots, b_{10}$ is $1$, each $b_i$ is a product of $9$ distinct prime numbers, but GCD of any $9$ of $b_i$'s is greater than $1$.It is easy to prove that there must exist at least one subset of length at most 10 whose elements have GCD = 1: starting with any given number, then repeatedly do the following process: choose a number to add to the current subset, such that it can eliminate at least one prime factor of the current GCD. Since this process can be done at most $9$ times, the resulting subset should have a size no larger than $10$.However, the conclusion in your statement is still correct, it is because the given numbers are less than $10^9$. That means, if all subsets of size $9$ have GCD greater than $1$, then each number should have exact $9$ different prime factors. Moreover, since they are coprime, then at least one of them does not have prime factor $2$. This number should be at least $3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 = 3234846615$.
•  » » 5 weeks ago, # ^ |   0 Thank you so much! It makes sense now.