Given any integer $n \ge 2$, show that there exists a set of $n$ pairwise coprime composite integers in arithmetic progression.
Problem
Source: Danube 2014 p3
Tags: coprime, Arithmetic Progression, number theory, arithmetic sequence
22.07.2019 12:10
Let $M=(n+1)!$, and let $N=M!$. Take $n!+N+1$, $~2n!+N+1$, $~3n!+N+1$, $~4n!+N+1$, $~\ldots\ldots$, $~n\cdot n!+N+1$ as the arithmetic progression.
22.07.2019 12:13
@above how are these numbers in an AP?
24.07.2019 14:02
They are since the difference between any two consecutive is $n!$. It's not sure they're composite though.
10.11.2024 20:19
Let $a,b$ be positive integers such that $(a,b!)=1$. Define $c_n = a + nb!$. Then $c_n$ and $c_m$ are coprime for $n,m < b$, because if $p$ was a common prime divisor, then $p| c_n-c_m = (n-m)b \implies p|b!$, but $p | a + nb! \implies p | a$, contradiction by definition of $a$. Now, for any positive integer $N$, just take $b > N$ great enough to have a sequence $(c_n)$. We now have to deal with the composite condition. Take $N $ distinct primes $p_1, \ldots, p_N$ coprime to $b!$. We wish to find $a$ such that the equations $ a \equiv -kb! \pmod p_k$ are satisfied. From CRT, this is possible and we can take $a$ as big as we want so that they're not the prime itself, finishing the problem.