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

  • 2
    $\begingroup$ It seems you mean to say $S$ is the set of relatively prime numbers between $0$ and $n$, not all relatively prime numbers. $\endgroup$ – aschepler Nov 4 '17 at 9:31
  • $\begingroup$ @aschepler Thanks! Edited :) $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.