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 a1=1, a2=11, a3=111, a4=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:
$a_{m+n}=a_{m}\cdot 10^{n}+a_{n}$
From the above:
$a_{m\cdot n} = a_{(m - 1)\cdot n}\cdot 10^{n} + a_{n} = a_{n}\cdot 10^{n\cdot (m-1)} + a_{n}\cdot 10^{n\cdot (m-2)} + ... + a_{n}\cdot 10^{n} + a_{n} $
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:
$\left \{ a_{p_{k}} \right \}_{k=1}^{\infty } \subset \left \{ a_{n} \right \}_{n=1}^{\infty }$
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:
$r\cdot p_{m} + s\cdot p_{k}=1$
.
Both \(r,s\) can't be negative and positive at the same time, so we can rewrite it this way:
$r\cdot p_{m} = s\cdot p_{k} + 1$
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
$a_{r\cdot p_{m}} = a_{s\cdot p_{k}+1} = a_{s\cdot p_{k}} \cdot 10 + a_{1}$
which means \(d>1\) also divides \(a_{1}=1\). Contradiction.
As a result, \(\forall k \neq m\)
$\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= 1$
Submit an article or tip
