Given any integer n≥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, ……, n⋅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 cn=a+nb!. Then cn and cm are coprime for n,m<b, because if p was a common prime divisor, then p|cn−cm=(n−m)b⟹p|b!, but p|a+nb!⟹p|a, contradiction by definition of a. Now, for any positive integer N, just take b>N great enough to have a sequence (cn). We now have to deal with the composite condition. Take N distinct primes p1,…,pN 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.