Number Theory – Infinitely Many Pairwise Relatively Prime Terms in an Arithmetic Progression

elementary-number-theorymodular arithmetic

Let $a$ and $b$ be two relatively prime positive integers, and consider the arithmetic progression $a$, $a+b$, $a+2b$, $a+3b$, . . .

  1. (G. Polya) Prove that there are infinitely many terms in the arithmetic progression that have the same prime divisors.

  2. 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.

Related Question