# Relatively prime elements forming an arithmetic progression

Let $n\in\mathbb{N}$. Consider $S$ to be the set of all numbers less than $n$ which are relatively prime to $n$. Is it true that $n=2^{k},p,6$,(where $p$ is a prime) are the only numbers for which the elements of $S$ form an arithmetic sequence?

Attempts: Clearly $1,n-1\in S$. If $p$ denotes the least prime not dividing $n$ then it's very clear that $1+d=p$ which says $d=p-1$. So basically our $S$ will be of the type $\{1,p,2p-1,3p-2,...,n-1\}$. Not sure how to go on from here. Any hints?

Clearly if $n$ is prime, then $S=\{1,2,3,\ldots,p-1\}$ which is a arithmetic sequence with $d=1$. If $d=2$, then it's clear that $n=2^{k}$, and if $n=6$, then $S=\{1,5\}$ which is an Arithmetic sequence with $d=4$.

• It seems you mean to say $S$ is the set of relatively prime numbers between $0$ and $n$, not all relatively prime numbers. – aschepler Nov 4 '17 at 9:31
• @aschepler Thanks! Edited :) – crskhr Nov 4 '17 at 16:29

Suppose $n \neq 6,p,2^n$ for $n \geq 1$. Let $D = \{k \leq n, (k,n) = 1\}$. Suppose that $D = (1 , 1 + d,..., k_0 + rd)$ for some $r,d$.

Clearly, $1+d$ is the smallest non-prime factor of $n$. It follows that if $d = 2$ then $n$ has to be a power of two. Similarly, $d=1$ would imply that $n$ has to be a prime. For the number $6$, we see that there are only two terms, so there is not really an arithmetic progression.

Now, we have $d = p-1$ where $p$ is the smallest prime non-factor of $n$. Let $q$ be the largest prime smaller than $p$. This means that $q$ divides $n$. Let us look at the sequence $1,p,2p-1,...,n-1$. How many terms does it contain? If $n -1 = rd+1$, then the sequence has $r+1$ terms, so we conclude it has $\frac{n-2}{p-1} + 1$ terms.

Claim : If $\frac{n-2}{p-1} + 1 > q$, then we are done.

Why is this true? Well, note that $1 , 1 + d , ..., n-1$ is a set of integers, whose size is greater than $q$. Let us make the size exactly $q$, by choosing only the numbers $1, 1 + d, ..., 1 + (q-1)d$.

I claim that each of these leave different remainders when divided by $q$, since if say $1 + fd$ and $1+gd$ leave the same remainder(where $0 \leq f,g < q$), then $q | (f-g)d$, but then $q | d$ or $q | f-g$. $q | f-g$ is not possible, since $|f-g| < q$.

The fact that $q|p-1$ is not possible stems from the fact that $q$ is the biggest prime smaller than $p$, and by Bertrand's postulate we see that $q > \frac {p-1}2$, since there is a prime strictly between $\frac{p-1}{2}$ and $p-1$, and $q$ must be greater than that prime, so cannot possibly divide $p-1$.

Therefore, by the pigeonhole principle, one of the $1+md$ is a multiple of $q$ (leaves the remainder $0$), a contradiction as then it wouldd have non-trivial gcd with $n$ (both are multiples of $q$), but is a member of $D$.

Claim : Indeed, $\frac{n-2}{p-1} + 1 > q$.

Proof : We will rearrange this, to get $n > (p-1)(q-1) + 2$. However, note that $n$ is a multiple of every prime number until $p$, so $n \geq \prod_{p' < p} p'$, where $p'$ are prime. Furthermore, note that $(p-1)(q-1) + 2 < pq$, so this really reduces to the wonderful result : $\prod_{p' < q} p' > p$.

We can see this by induction, roughly, since each time the right hand side can be multiplied by atmost $2$ (Bertrand's postulate!) while the right hand side is multiplied by a prime, which is larger than or equal to $2$, each time.

This proves the second claim. Therefore, for large enough $d = p-1$, indeed no number exists whose set of relatively prime numbers are in arithmetic progression. I think the proof above (the induction, Bertrand's postulate etc.) starts working for small enough $d$ (I think $p=7$ would do). $p=3,5$ can be checked individually (it is actually quite clear: I leave it as an exercise).

Therefore, the only numbers with the stated property are prime, powers of two, and six.

EDIT : I would then continue to think as follows : if not geometric progression, then what more regularity can we demand from the co-prime set? I was thinking, possibly this condition : there exist a pair of consecutive numbers in this set i.e. for some $k$, both $k,k+1 \in D$. Can we assert , that for non-prime $n$, and non-powers of $2$, this would happen?