Another Number Theory Problem

This is the second post dedicated to the problems set posted on "Math, Math Education, Math Culture" LinkedIn group. Here is the original LinkedId discussion, again... if you happen to have a LinkedIn account. Here is the problem:

Prove that the sequence a₁=1, a₂=11, a₃=111, a₄=1111,... contains an infinite sub-sequence whose terms are pairwise relatively prime.

Few observations first of all, without proving them as it should be fairly trivial, e.g. using induction:

From the above:

So if \(a_{n}\) is divisible by \(t\in \mathbb{N}\), \(t>1\) then \(a_{m\cdot n}\) is also divisible by \(t\) (1).

Now, let's consider the sub-sequence:

where \(p_{k}\)- k-th prime. I state that this sub-sequence satisfies the condition of the problem. Let's prove it by contradiction.

I.e. let's assume there \(\exists k \neq m\) such that \(\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1\). Because \(\gcd\left ( p_{m}, p_{k}\right )= 1\) (i.e. both are prime numbers), then, by applying Bezout's theorem (or lemma), there \(\exists r,s\in \mathbb{Z}\) such that:

.

Both \(r,s\) can't be negative and positive at the same time, so we can rewrite it this way:

assuming both \(r\) and \(s\) are positive this time.

Because we assumed \(\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1\), then \(d\) should also divide both \(a_{r\cdot p_{m}}, a_{s\cdot p_{k}}\) (using \((1)\) proved above). But

which means \(d>1\) also divides \(a_{1}=1\). Contradiction.

As a result, \(\forall k \neq m\)