So if $n$ is prime, then all integers less than $n$ are coprime to $n$, with the consistent difference of $1$, thus forming an arithmetic progression.

If $n$ is composite, then we would have two cases, either even or odd.

If $n$ is even, then it is not coprime with every even integer less than $n$, but how would I show if the sequence forms an arithmetic progression or not? My thinking is that if $n$ does not have an odd divisor, i.e. $2^m$ for some integer $m$, thus is coprime to all odd integers less than itself, the sequence would form an arithmetic progression. But if $n$ does have an odd factor $x$, then it is not coprime to any multiples of $x$, thus as long as I show that there exist two consecutive odd integers coprime to $n$ exists, then an arithmetic progression would not exist in the sequence as the different between $x-2$ and $x+2$ would be four which the others would be two.

If n is odd, a similar case to the above would unfold, so not sure how to progress there as well :(


1 Answer 1


If $(n,2)=1$ and $(n,3)=1$ then $ 1,2,3,\cdots$ are coprime to $n$ and so $n$ must be prime.

If $(n,2)=2$ and $(n,3)=1$ then $1,3, \cdots$ are coprime to $n$, the diff between $3$ and $1$ is $2$ so the next are $5,7,9,\cdots$ if there is a.p. and we have all the odds less than $n$ so $n$ must be a power of $2$.

If $(n,2)=1$ and $(n,3)=3$ then $1,2,4 \cdots$ but this does not form a.p. since $2-1=1$ but $4-2=2$ so in this case we have contradiction.

If $2|n$ and $3|n$ then $5$ might be the first coprime but then the diff is $4$ and so $5+4= 9$ and $(n,9)>1$ so contradiction.

If $7$ is the first coprime then $1,7,13,19,25$ but $(n,25) > 1$ so contradiction and $7$ cannot be the first coprime.

Now assume that $p_{k+1}$ is the first coprime to $n$, this would imply that $p_1,p_2 , \cdots p_k | n$ which means that $n \geq p_1 p_2 \cdots p_k$ , if $p_{k+1}$ is the first coprime then the diff is $p_{k+1}-1$, let $p_j$ be the first prime such that $gcd(p_{k+1}-1,p_j)=1$,such prime always exists less than $p_{k+1}-1$ because in order to not exist $p_{k+1}-1 < p _{k+1} $ must be bigger that $p_1 p_2 \cdots p_k = e^{\theta(p_k)}\approx e^{p_k}$ which is false, and so since $ (p_{k+1}-1,p_j)=1$ then by the pigeonhole principle $p_j$ must divide one of the numbers $p_{k+1}+ (p_{k+1}-1) , p_{k+1}+ 2(p_{k+1}-1 ),\cdots p_{k+1}+ p_j(p_{k+1}-1 ) $ and so a contradiction to the a.p. ,, what left is to show that $p_{k+1} + p_j p_{k+1} \leq p_{k+1}+ p_{k+1}^2<< p_1 p_2 p_3 \cdots p_{k} $ which is very easy to prove, with checking smaller cases one conclude that if the coprimes to a number $n$ produce an a.p. then $n$ is prime or a power of $2$ or $n=6$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .