Let $a$ and $b$ be two relatively prime positive integers, and consider the arithmetic progression $a$, $a+b$, $a+2b$, $a+3b$, . . .
-
(G. Polya) Prove that there are infinitely many terms in the arithmetic progression that have the same prime divisors.
-
Prove that there are infinitely many pairwise relatively prime terms in the arithmetic progression.
I was able to solve the first part by showing that the sequence {$ap$, $ap^2$, $ap^3$, . . .} has infinite intersection with the sequence {$a$, $a+b$, $a+2b$, . . .} by considering a prime $p$ $\equiv$ $1$ (mod $b)$ whose existence is guaranteed by Dirichlet.
For the second part, I assumed $k$ terms of the sequence which are pairwise relatively prime and then attempted to show that another pairwise relatively prime term can be generated from the previous $k$ terms by using a construction similar to that of Euclid's. However I wasn't able to get anything meaningful. Does this approach yield the desired result? If so how exactly can we achieve the result?
Best Answer
I think we can solve the second part of the question inductively, without using Dirichlet's Theorem.
Let's assume $a+n_1b, a+n_2b, \ ... , a+n_m b $ are some elements of the sequence which are pairwise relatively prime. Since $a$ and $b$ are relatively prime, by Euler's theorem, we have $b \mid a^{\varphi (b)+1} -a,$ where $φ(b)$ denotes Euler's totient function.
Now, consider: $$X=(a+n_1b)^{x_1}(a+n_2b)^{x_2} ... (a+n_m b)^{x_m}+b,$$
such that $x_1, x_2, ...,x_m\geq1$ and $x_1+x_2+...+x_m=(\varphi (b)+1)^k$ for some $k \in \mathbb N. $ It's very easy to verify that $X$ is also a member of the sequence; in other words, $X$ can be written as $a+nb$ for some $n \in \mathbb N$.
Additionally, if $d\mid a+n_ib$ and $d \mid X$, where $1 \leq i \leq m$, then we must have $d \mid b$. So, we must also have $d \mid a$, which implies $d=1$. Hence, $$a+n_1b, a+n_2b, \ ... , a+n_m b, X=a+nb $$ are pairwise relatively prime.
Doing the same with the new sets infinitely many times yields the claim. To start, note that $a+b$ and $a+2b$ are coprime.
We are done.