I'll use Bertrand's Postulate: for $u\ge 2$ is a positive integer, there is a prime in the interval $(u,2u)$. Clearly, $a_2$ must be equal to the smallest prime $p$ which does not divide $n$. If $p=2$, then $n$ is a prime since the common difference $a_{i+1}-a_i$ is equal to $1$, i.e. all positive integers less than $n$ are coprime to $n$. If, on the other hand, $p=3$, we find $n$ to be a power of $2$: the positive integers less than $n$ and coprime to it are precisely the odd ones. We may thus assume that $p\ge 5$. Furthermore, since $n>6$, the positive integers less than $n$ and coprime to it cannot be $a_1,a_2$ alone, i.e. $k=\varphi(n)\ge 3$. By Bertrand's Postulate, the largest prime less than $p$ is strictly larger than $\frac{p-1}2$, so it cannot divide $p-1$. We will denote this prime by $q$. We know that $q|n$. It's easy to check that for $p\le 31$ there is a prime $r$ strictly between $a_2=p,\ a_3=2p-1$. $rq|n$, so, in particular, $pq<rq\le n$. On the other hand, if $p>32$, the two largest primes $r_1<r_2$ which are smaller than $q$ satisfy $r_2\ge\frac p4,\ r_1\ge\frac{r_2}2\ge\frac p8$ (again, Bertrand's Postulate), so $pq<\frac{p^2}{32}q\le r_1r_2q\le n$ so, once again, we have $pq<n$ (this is what I wanted to prove here). Now, $q\not|p-1$, and all the numbers $1,1+p-1,\ldots,1+(q-1)(p-1)$ are smaller than $n$ (they are smaller than $pq$, which is smaller than $n$, according to the paragraph above). One of these numbers, however, must be divisible by $q|n$. Since our hypothesis tells us that all of them must be coprime to $n$, we have a contradiction.

There is simple solution without using Bertrand's Postulate... We have a[1]=1, a[2]=p, where p is the least prime, which is not a divisor of n; a[k]=n-1, r=p-1 is the difference of the progression a. If n is odd, then a[2]=2 1, 2, ..., n-1 is our progression n is a prime. If i is even, then p>2. 1. If p=3, then 1, 3, ..., n-1 is our progression n is a power of 2. 2. If p>3, then n is divisible by 3. we have n-1=a[k]=1+(p-1)(k-1) p-1 is divisor of n-2. Let q be a random prime divisor of p-1. q | p-1 | n-2, but q|n, because q<p q|2 and q=2. It means p-1=2^i p=2^i + 1. So as p is prime >3, i is even. But a[3]=2p-1=2^(i+1) + 1 is divisible by 3, but n is divisible by 3 too gcd(n, a[3])>1. This contradiction ends our proof.

The sequence is $ a_i = 1 + (p - 1)(i - 1), 1 \le 1 \le \phi(n), a_{\phi(n)} = 1 + (p - 1)(\phi(n) - 1) = n - 1$, where $ p$ is the smallest prime not dividing $ n$. If $ p = 2$, then $ \phi(n) = n - 1$ so $ n$ is a prime. If $ p = 3$, then $ n$ is coprime to all odd primes $ \le n$, so $ n$ is a power of $ 2$. Otherwise, $ p \ge 5$. It implies that $ 6 | n$ and that if you take 4 (=5-1) consecutive integers ($ \le n$) then at most one of them is coprime to $ n$. Let $ t = \frac {n}{6}$. Consider $ 3t - 1, 3t, 3t + 1$. At most one of $ 3t - 1$ and $ 3t + 1$ should be coprime to $ n$. But they have the same gcd with $ n$, so $ 3t \pm 1$ are not coprime with $ n$, which implies that $ t$ is odd, because $ (3t - 1, n) = (3t - 1,6t) = (3t - 1,2)$. It implies that $ (3t - 2,6t) = (3t - 4,6t) = 1$:2 number with distance 2 that are coprime to $ n$, a contradiction. (note: we need $ n > 6$ for $ 3t - 4 \ge 1$, because $ n = 6$ also satisfies the requirements)

here is my solution of this problem Let, $ a_2 - a_1 = a_3 - a_2 = ... = a_k - a_{k + 1} = s$ and $ a_k > a_{k - 1} > ... > a_2 > a_1 = 1$ Case:1: $ s > 2$ if $ a_2$ is not a prime number it means that there exist a divisor $ d$ of $ a_2$ such that $ 1 < d < a_2$. Hence $ \gcd(d,n) > 1\Rightarrow\gcd(a_{2},n) > 1$ which is a contradiction !! Now let's suppose that $ a_i$ is not a prime for some $ i$. Hence there exist a prime divisor $ l$ of $ a_i$ such that $ 1 < l < a_i$ if $ l\neq a_j$ $ \forall j \le i$ then $ \gcd(l,n) > 1 \Rightarrow \gcd(a_i,n) > 1$ which is a contradiction !! and so there exist $ j > 1$ such that $ \forall i$ we have $ a_i = a_j^c$ and $ j < i$ By the last argument we have $ a_i = a_j^c = a_{j_2}^{c_2} = a_{j_3}^{c_3}... = a_2^d$ Usin our condition we get $ a_2^d - a_2^{d'} = a_2 - 1$ which is not true !! we conclude that $ \forall i , a_i$ is a prime number . if $ a_2^2 < n$.Since $ a_i$ is a prime number it means that $ 2a_2 - 1$ is prime and $ 3a_3 - 2$ is prime and $ 4a_4 - 3$ is prime...$ (a_2 + 1)a_2 - a_2$ is prime $ \Leftrightarrow$ $ a_2^2$ is prime which is not true. Hence $ a_2 > \sqrt {n}$and it means that $ \forall k < \sqrt {n}$ we have $ \gcd(n,k) > 1$which implies that $ \gcd(k,n - k) > 1$,$ \forall k < \sqrt {n}$ . On the other hand there exist a $ l$ such that $ n - k = a_l$ and so $ \gcd(n,a_l) > 1$ which is not true !! So the hypothesis of the case 1 is not true !! Let's go now to the case $ s = 2$ we have $ \gcd(n,1) = 1 \Rightarrow \gcd(n,3) = 1 \Rightarrow \gcd(n,5) = 1 ...\Rightarrow \gcd(n,2k + 1) = 1$ and so the power of two are a solution. When $ s = 1$ we get easily the fact that n is prime and we have done !!

if n is odd then the problem is trivial. if not then n must be square free because if n=(2^k)((p_1)^ a_1)...((p_t)^a_t) (we suppose that n#2^m) then this two number are relatively prime to n: 2(p_1)...(p_t) + 1 and 2(p_1)...(p_t) - 1 if this two number are less than n then the problem woud be trivial. so n must be on this form n=2(p_1)...(p_t) but u can easily see that in this case (n/2)+2 and (n/2)-2 are relatively prime to n. the rest is trivial(u can find that 3|n but (9,n)=1!!!!)

davicoelhoamorim wrote: a_k>a_(k-1)>...>a_2>a_1 => k=phi(n), a_k=n-1 and a_1=1 because a_2-a_1=a_3-a_2=...=a_k-a_(k-1)=r, we have that a_i=a_(i-1) + r => a_k=a_1 + (k-1).r => n-1=1 + (phi(n)-1).r => [n-2]/[phi(n)-1]=r => phi(n)-1|n-2 if phi(n)-1=n-2 => phi(n)=n-1 => n is a prime if no, 2[phi(n)-1]=<n-2 => n/2>=phi(n) => n=2^k $a_k=n-1<=>n $be prime???

No. For any $n\geq 2$ we have $\gcd(n-1,n)=1$, so $a_k = n-1$. It is only when, as said, $\phi(n) = n-1$, that the conclusion $n$ prime was reached.

Nice problem. Really liked it. Sorry that I don´t know LaTex yet! Ok, my solution is really simple: First, solve the equalities two - by - two. Ater that, you get a general formula, from now on called G(n): 2a_i = a_i+1 + a_i-1 Hence: 1) 2a_2 = a_3 + a_1 2) 2a_3 = a_4 + a_2 . . . k-2) 2a_k-1 = a_k + a _k-2 Now, by definition, we know that 1 is relatively prime to every natural number > 1. Therefore, a_i = 1 , i element of euler´s function of n (sorry, don´t know how to use latex). Then, since 2a_2 = a_3 + a_1, a_3 + a_1 = 0 (mod 2). Now, since a_1 = 1, which is uneven, a_3 must be uneven. Then, since 2a_4 = a_5 + a_3, a_5 + a_3 = 0 (mod 2). Since we already established a_3 is uneven, so is a_5. This process goes on, and we arrive to the conclusion that both terms on the right hand side of the equals are uneven, for the equalities on uneven places, starting with 2a_2 = a_3 + a_1. Then, we see two cases: 1) a_2 Uneven. 2) a_2 Even. Case 1: a_2 Uneven. Using the same analysis as before, since 2a_3 = a_4 + a_2, a_4 + a_2 =0 (mod 4). Now, since a_2 is uneven, a_4 must also be uneven. Then, using the same analysis in the remaining equalities we see that both terms to the right hand side of the equals will be uneven in the equalities on even places (starting in 2a_3 = a_4 + a_2). Earlier, we already established that both terms to the right hand side of the equals on uneven places were both uneven, independent of the parity of a_2. Therefore, all terms are uneven. Therefore, a_i is uneven, for i = 1,2,...,k. Now, that means that n is not relatively prime to even numbers, so n must be even. Now, lets assume n has at least one uneven factor. That means that at least one of the uneven integers from 1 to n won´t be relatively prime to n. Then, assume that p and p+2 are both relatively prime to n. Since both are uneven, that means that a_i = p , a_i+1 = p + 2. Now, assume m-2, m and m+4 are relatively prime to n, but m+2 is not relatively prime to n. That means a_i-1 = m-2 , a_i = m , a_i+1 = m + 4 By G(n):, we get: 2m = m + 4 + m - 2 Therefore 2m = 2m + 2, so 0 = 2, which is obviously false, so this is a condradiction. Therefore, n doesn´t have uneven factors, so n = 2^t. Case 2: a_2 Even. Since 2a_3 = a_4 + a_2, a_4 + a_2 = 0 (mod 2). Since a_2 is even, a_4 is also even. Using the same analysis, we see that both terms to the right side of the equal sign will be even, for the equalities on even places. We already established that both terms to the right hand side of the equals on uneven spaces were both uneven, independent of the parity of a_2. Since this terms are even, that means n is relatively prime to some even numbers, so n is uneven. Therefore, n is relatively prime to 2. Since a_1 = 1, that means a_2=2. Therefore, solving in G(n), a_3= 3. Replacing in the next equality we get a_4 = 4. In general, we get a_i = i , for i = 1,2,3,...,k. Therefore, n is relatively prime to 1,2,3,...,k. That means n is prime, thus finishing the demonstration. Could somebody please check my solution? Thanks!!!

I found a really simple solution. Let $d=a_{i+1}-a_i$. Then we have $a_i=1_1+d(i-1)=1+d(i-1)$. Since $\gcd(n-1,n)=1$, so $n-1$ is the largest positive integer smaller than $n$ and co-prime to $n$. Thus, $a_k=n-1$ and $1+d(k-1)=n-1$ which shows $d(k-1)=n-2$ and so $d$ divides $n-2$. We make two cases. Case 1: $n$ is odd. Then $\gcd(n-2,n)=1$. So, every divisor of $n-2$ is co-prime to $n$ too, so is $d$. Thus, there is a $j$ such that $d=a_j=1+d(j-1)$ which implies $d|1$. Therefore, in this case, $d=1$ and we easily find that all numbers less than $n$ are co-prime to $n$, so $n$ must be a prime. Case 2: $n$ is even. But then $\gcd(n-2,n)=2$ and also $d=1$ is ruled out. So $d>1$. Say, $n=2l$. Then, $d$divides $2(l-1)$. If $d$ is odd, $d|l$ and $d|l-1$ forcing $d|1$, contradiction! So, $d=2s$ with $s|l-1$. If $l=2r+1$ for some $r$, then $\gcd(r,n)=1$. So, again $r=1+d(j-1$ for a $j$. If $s$ is odd, then $s|r$ and thus, $s|1$. Similarly, we find that actually $d|2$ must occur. We finally have, $d=2$. But then all odd numbers less than $n$ are co-prime to $n$. So, $n$ does not have any odd factor i.e. $n=2^k$ for some $k\in\mathbb N$. And learning $\text{\LaTeX}{}$ is really easy. You just need to learn some symbols and put your formulas between two dollar signs. For more, you can see here: http://www.artofproblemsolving.com/Wiki/index.php/LaTeX:About

Here is another solution. If $n$ is odd, then $a_{2}=2$, and the conclusion follows. ($n$ has no common divisor with all integers less than it). Now assume $n$ is even. $i)$ $a_{2}=3$ , in this case n is pairwisely coprime with all odd integers less than itself, so that it should be a power of $2$. $ii)$ $a_{2} > 3$. Observe that $3|n$. In this case, let $p$ be the smallest prime number not dividing $n$. We claim that $p \equiv1\; (mod\; 3)$. Because if $p \equiv2\; (mod\; 3)$, then $a_{3}=2p-1$ will be divisible by $3$, contradicting with the fact that $3|n$. Now, we have an arithmetic sequence with common difference $p-1$. So, $(k-1)(p-1)=n-2$. But if we check both sides of this equation in $mod 3$, we see that $3|(k-1)(p-1)$; however, $3 \nmid n-2$, contradiction. Hence the problem is done.

grupyorum wrote: AFdrolf wrote: grupyorum wrote: Here is another solution. If $n$ is odd, then $a_{2}=2$, and the conclusion follows. ($n$ has no common divisor with all integers less than it). Now assume $n$ is even. $i)$ $a_{2}=3$ , in this case n is pairwisely coprime with all odd integers less than itself, so that it should be a power of $2$. The fact that a_2 = 3 doesn´t imply that it is comprime with all odd integers less than itself... Take 20 for example: a_2=3, but it is not coprime with 5 Actually, if $a_{2}=3$, then $a_{3}=5$, $a_{4}=7$, .. $a_{k}=n-1$ (remember $n$ is even). So, n is pairwisely coprime with all odd integers less than itself By the way, $20$ does not satisfy the conditions of the problem, so that it's wrong Oh, sorry about that, I thought you meant that if ANY integer n is coprime with 3, n was coprime with all pairwise integers less than itslef.. I actually used a similar approach as you in my solution. Well thought solution that of yours!

Let $p$ be the smallest prime number such that $p$ doesn't divide $n$.It is trivial that $a_1=1$ , $a_2=p$ , $a_k=n-1$ so all the equalities are equal to $p-1$.Now for cases $p=2$ and $p=3$ we trivialy obtain that prime $n$ and every $n=2^k$ are solutions.Now we consider the case $p>3$.By summing the equalities we get $(p-1)(k-1)=n-2$. Now because $p>3$ we have $3|n$ so $3$ doesn't divide $n-2$ so we obtain $p \equiv 2 $ modulo $3$.That means $p-1 \equiv 1$ which immediately implies $3|a_3$ which is a contradiction so we are finished.

If $n$ is odd then $a_1 = 1, a_2 = 2 \rightarrow a_k = k$ for all $k$, so if $n$ is not prime then $n = pq$ for some $p, q > 1$, which means $p$ should not be the value of $a_i$; but it is, contradiction. Suppose $n$ is even. If $n$ is not divisible by $3$ but has an odd factor greater than 1, then $a_1 = 1, a_2 = 3 \rightarrow a_k = 2k - 1$ and we are done in a similar manner to above. Thus assume $n$ is divisible by $3$. Because $n > 6$, it is clear that $\phi(n) > 2$ (by considering the prime factorization of the largest odd factor of $n$), so there exists $p \neq 1, n-1$ relatively prime to $n$. Thus $a_2 \neq n-1$. Because if $p$ is relatively prime to $n$ then $n - p$ is also, we have $a_2 < \frac{n}{2}$. Now, because $1$ and $n-1$ are values of some $a_k$, the common difference, $p-1$, must divide $(n-1) - 1 = n-2$, so since $3 | n$, we have $3$ relatively prime to $n-2$ and thus $p-1$. Therefore, $a_1, a_2, a_3$ form a complete set of residues modulo $3$, which means one of these numbers is not relatively prime to $3$ and thus $n$, contradiction. Thus $n$ is a power of $2$ if $n$ is even, completing the proof.

I'll use Bonse's Inequality: $p_{m+1}^2 < p_1p_2\cdots p_m$, for all $m \ge 4$, $p_1 = 2$. Let $p$ denote the smallest prime which does not divide $n$. Case 1) $p = 2$. This implies $n$ is a prime. Case 2) $p = 3$. This implies $n = 2^k$ for some $k \in \mathbb{N}$. Case 3) $p = 5$. Since $n > 6$, we have that $n > 9$. Therefore $a_3 = 9$, but $\gcd (n, 9) > 1$. Case 4) $p \ge 7$. Write $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We have $(p - 2)^2 < p_1p_2\cdots p_k \le n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. Hence $(p-2)^2 = a_i$, a contradiction since $\gcd(p-2, n) > 1$.

I think I have carefully avoided advanced NT, so here is my solution: Clearly, $a_1 = 1$. Now let $p$ be the smallest prime number which is not a divisor of $n$. Hence, $a_2 = p$, and the common difference $d = p-1$. Observe that since $a_k = n-1$, we have that \[ d \mid a_k - a_1 \], or \[ p - 1 \mid a_k - a_1 = n-2 \]. This means that all prime factors of $p-1$ are prime factors of $n-2$. However, due to the minimality of $p$, all primes factors of $p-1$ are prime factors of $n$. By the Euclidean algorithm, the only prime factors of $p-1$ are $2$, so $p = 2^{2^k} + 1$ or $p = 2$, by the theory of Fermat primes. We will now do casework on $p$. Case 1: $p = 2$ This case is relatively easy. $a_2 = 2$, so all numbers less than $n$ must be relatively prime to $n$. However, if $n = pq$, where $p > 1$ and $q > 1$, observe that $p$ is not relatively prime to $n$, so $n$ must be prime for this case to work. Case 2: $k = 0$ and $p = 3$. This case is somewhat tricky. Observe that $n$ is even. Since $a_2 = 3$, we have that all numbers less than $n$ which are odd are relatively prime to $n$. However, if $n$ has a odd divisor $p > 1$, clearly $p$ is not relatively prime to $n$, so $n$ must be a power of two. Case 3: $k \ge 1$. Note that $3$ must be a divisor of $n$, so $a_k$ cannot be a multiple of $3$ for any $k$. I will contradict this statement. First, I claim that $k = \phi(n) > 2$ for all integers $n > 6$. $\phi{n} = 1$ is trivial, so let me show that $\phi(n) = 2$ has only solutions less than or equal to $6$. Since $\phi$ is a multiplicative function, observe that $n$ cannot be a multiple of a prime greater than $3$, because for such primes $p$ we have that $\phi(p^k) = (p-1)p^{k-1} \ge p-1 > 2$, which is contradiction. Hence, $n$ is just composed of factors of $2$ and $3$. If it divides both, and is of the form $2^m 3^n$ for $m$ and $n$ positive, we get that we need $2^{m} 3^{n-1} = 2$, so $n = 1$ and $m = 1$ in this case. If it is of the form $n = 2^k$, we get $k = 2$. And if it is of the form $3^k$, we get $k = 1$. $3$, $4$, and $6$ are all less than or equal to $6$, so $\phi(n) > 2$. Now we're almost done. Since $k > 2$, the number $a_3 = 2p-1$ must be in this sequence. However, $a_3 = 2p-1$ is of the form $2^{2^n+1} + 1$, which is a multiple of $3$, and we have contradiction, so we are done.

Here is my solution. Clearly that $a_1=1$. Let $a_{i+1}-a_i = d \; (1 \le i \le \varphi(n)-1)$ then $$a_{i}=(i-1)d+1 \; \; (1 \le i \le \varphi(n)). \qquad (1)$$We can see that if $n$ is a prime then $n$ satisfies the condition. We consider the case when $n$ is a composite number. Let $p$ be the smallest prime divisor of $n$ then $p \le \sqrt{n}$. Note that $\varphi (n) > \sqrt{n} \ge p$ for all prime $n>6$ since $p_i^{k_i}-p_i^{k_i-1} \ge p_i^{k_i/2}$ for all $p \ge 3$. Therefore, if $p \nmid d$ then there will exists $1 \le i \le \varphi(n)$ such that $(i-1)d \equiv -1 \pmod{p}$ or $p \mid a_i$, a contradiction since $\gcd (a_i,n)=1$. Thus, $p \mid d$. We consider two cases: If $d \ge 2p$ then $p+1 \ne a_i \; (1 \le i \le \varphi(n))$. Hence, $\gcd (p+1,n)>1$. This means there exists a prime $q>p \ge 2$ such that $q \mid p+1$. Since $q>p$ so we get $q=p+1$ or $p=2,q=3$, a contradiction since $n>6$. Thus, $d <2p$ or $d=p$. If $p=d=2$ then all odd numbers $a_i \le n$ are relatively prime to $n$. This can only happen when $n=2^x \; (x \in \mathbb{N})$. If $p=d >3$ then $p+3 \ne a_i \; \forall 1 \le i \le \varphi(n)$ since $a_i \equiv 1 \pmod{p} \; \forall 1 \le i \le \varphi(n)$. Thus, $\gcd (p+3,n)>1$ or there exist a prime $q>p>3$ such that $q \mid p+3$. Note that $2 \mid p+3$ so $q \le \tfrac{p+3}{2}<p$, a contradiction. Thus, $n$ must be either a prime number or a power of $2$. $\blacksquare$

China Mathematical Olympiad 2017 Q5

Let $ \,n > 6\,$ be an integer and $ \,a_{1},a_{2},\cdots ,a_{k}\,$ $(k\geq5)$ be all the natural numbers less than $ n$ and relatively prime to $ n$ . If $k$ is even ,and $a_{2} - a_{1} = a_{4} - a_{3} =a_{6} - a_{5} \cdots = a_{k} - a_{k - 1} ,$ find all such positive integers $n$.

sqing wrote: China Mathematical Olympiad 2017 Q5 Hi sqing, what is your reason behind linking this topic to Q5 China MO 2017 ? I don't see any connection between these two problems.

Rewritten Problem Statement wrote: Let $n\in\mathbb Z_{\geq 2}$ be an integer and $ \,a_{1},a_{2},\cdots ,a_{k}\,$ be all the natural numbers less than $ n$ and relatively prime to $ n$. If \[ a_{2} - 1 = a_{3} - a_{2} = \cdots = \left(n-1\right) - a_{\varphi(n) - 1}=\Delta> 0, \]prove that $ \,n\,$ must be either a prime number or a power of $ \,2$. It is clear that we have $\Delta\mid n-2$. Hence $\gcd(n,\Delta)\in\{1,2\}$. Let $n=2^{\alpha}p^{\beta}\prod q_i^{\gamma_i}$ where $p$ is the lowest odd prime divisor of $n$. If $p$ does not exist then we necessarily have $n=2^{\alpha}$, a case that is easily checked to give $\Delta=1$. If $n\not \in\left\{p,2p\right\}$ then we have $\varphi(n)\geq p$, meaning that our arithmetic sequence contains a multiple of $p$, a clear contradiction, since $p\nmid \Delta$. The case $n=p$ is also easily checked, giving $\Delta=2$. For $n=2p$, if $p\geq 5$ we have $\Delta=2$ by considering $a_1=1,a_2=3$, but then $p$ is on the arithmetic sequence which is ludicrous. Note that $n=6$ also works. We conclude that the solutions are $\boxed{n\in\left\{p,6,2^{\alpha}\right\}}$

shinichiman wrote: sqing wrote: China Mathematical Olympiad 2017 Q5 Hi sqing, what is your reason behind linking this topic to Q5 China MO 2017 ? I don't see any connection between these two problems. I judged wrong . Sorry .

Let $p$ be the smallest prime that does not divide $n$. Let $p \ge 5$ (the other cases were treated in the other solutions). $a_{1}=1$, $a_{2}=p$, so $a_{k}-a_{k-1}=p-1$. We easily get by induction that $a_{i}=(i-1)p - i + 2$, so $a_{p-2}=p(p-3) - p+ 4=(p-2)^2$, so $(n,p-2)=1$. This contradicts the minimality of $p$.

pavel kozlov wrote: There is simple solution without using Bertrand's Postulate... We have a[1]=1, a[2]=p, where p is the least prime, which is not a divisor of n; a[k]=n-1, r=p-1 is the difference of the progression a. If n is odd, then a[2]=2 1, 2, ..., n-1 is our progression n is a prime. If i is even, then p>2. 1. If p=3, then 1, 3, ..., n-1 is our progression n is a power of 2. 2. If p>3, then n is divisible by 3. we have n-1=a[k]=1+(p-1)(k-1) p-1 is divisor of n-2. Let q be a random prime divisor of p-1. q | p-1 | n-2, but q|n, because q<p q|2 and q=2. It means p-1=2^i p=2^i + 1. So as p is prime >3, i is even. But a[3]=2p-1=2^(i+1) + 1 is divisible by 3, but n is divisible by 3 too gcd(n, a[3])>1. This contradiction ends our proof. This is exactly what I did.

Let the smallest prime not dividing $n$ be $p$. Then the sequence has to be $1, p, 2p-1, 3p-2, 4p-3, \dots, n-1$. Since the common difference in this arithmetic sequence is $p-1$, we have that $p-1$ must divide $(n-1)-1=n-2$. But by the assumption of $p$ being the smallest prime, we also have that $p-1$ divides $n$. Therefore, $p-1$ divides $n-(n-2)=2$. So $p$ is either $2$ or $3$. If $p$ is $2$, then the sequence is $1, 2, 3, \dots. n-1$, so $n$ is prime. If $p$ is $3$, then the sequence is $1,3,5,\dots n-1$ so $n$ is relatively prime to all odd numbers less than it and must be a power of $2$.

I solved the problem with the condition that $n\in \mathbb{N}.$ Obviously $n=1$ is a solution$,$ as well as $n=2, 3, 4,$ so assume that $n\geq 5.$ Let the common difference be $d.$ The condition implies $$a_{\varphi(n)}=a_1+d(\varphi(n)-1)\iff n-2=(\varphi(n)-1)d\hspace{1cm}(*)$$as it's easy to notice that $a_{\varphi(n)}=n-1.$ If $d=1,$ we get that $n$ is prime$,$ which is easily seen to work$.$ If $d=2,$ we get that $n$ is a power of $2,$ as $$2=\frac{n}{\varphi(n)}=\prod_{p\mid n}\bigg(\frac{p}{p-1}\bigg)\geq 2$$with equality only when $\text{rad}(n)=2.$ It is again not that hard to verify that all such $n$ work$.$ Suppose $d\geq 3$ and notice that $\varphi(n)$ is even for $n>2,$ so if $d$ is odd$,$ by equation $(*)$ we obtain $n$ must also be odd$,$ but then $\gcd(2, n)=1,$ meaning $a_2=2$ and $d=1,$ contradiction$.$ Therefore $d\geq 4$ and $n$ is even$.$ Let $p$ be the smallest prime not dividing $n.$ Now all the numbers $2, \cdots , p-1$ are not relatively prime to $n$ and so $a_2=p \Rightarrow d=p-1.$ Suppose that $r$ is a prime factor of $p-1.$ Because $p$ is minimal$,$ $r$ must divide $n.$ By equation $(*)$ we see that $r\mid 2,$ therefore $p-1=2^k$ for some $k\geq 2$ (recall that $4\leq d=p-1$)$.$ But since $p$ is a prime$,$ $k$ cannot have any odd factor$,$ from which we get $k=2^t$ and $p=1+2^{2^t}.$ Finally$,$ suppose $\varphi(n)\geq 3$ so that $a_3=2p-1$ exists$.$ Note that $p\equiv 2\pmod 3 ,$ meaning $a_3\equiv 0\pmod 3$ and as $p>3,$ we see that $3$ also divides $n,$ a clear contradiction$.$ This means that $\varphi(n)\leq 2$ and the only possibility is $n=6,$ which is also easily verified$.$

Firstly $n \text{ odd} \iff n \text{ prime }$: $2 \nmid n \implies a_2=2 \implies a_i \text{ are } 1, 2, 3, \ldots \implies n \text{ prime}$ So, let $n$ even: Let $p$ be the smallest prime with $p \nmid n$ Case 1: $p=3$ $\implies a_i \text{ are } 1, 3, 5, \ldots \implies n \text{ is a power of 2 }$ Case 2: $p>3 \implies 3 \mid n$ $\implies$ none of $m \in \{ 2, 3, \ldots, p-1 \}$ can be an $a_i$ else: $\gcd(m, n) = 1 \implies$ for any prime $q \mid m \text{ we must have } q \nmid n \text{ but } q \leq m <p$ which is a contradiction. So, $a_2=p \implies a_r=1+(p-1)(r-1) \implies p \equiv 1 \pmod{3} ( \text{ else, } p \equiv 2 \pmod{3} \implies 3 \mid a_{r \equiv 0 \pmod{3}} ) \implies p-1 \equiv 0 \pmod{3}$ which is a contradiction. $\blacksquare$ Q.E.D

No idea if this is correct :clown: First note that the problem obviously works for primes. So henceforth assume $n$ is composite. Case 1. $2 \nmid n$ Let $n=p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}, p_i \ne 2 \forall i \in \{1,2, \dots, k\}$. Note that $\frac{p_1p_2 \dots p_k-1}{2}, \frac{p_1p_2 \dots p_k+1}{2}$ are two consecutive naturals, less than $n$ and coprime to each $p_i$, hence coprime to $n$. Therefore we deduce that if this were a part of an AP, all $p_i$s sure to occur in the sequence, but they not coprime to $n$. This is a contradiction. Case 2. $2 \mid n$ Let $n= 2^{a_0}p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}, p_i \ne 2 \forall i \in \{1,2, \dots, k\}, a_0 \geq 1$. Note that $p_1p_2\dots p_k+2, p_1p_2\dots p_k+4$ are two odd natural numbers, which are coprime to each of $p_1,p_2,\dots p_k$, hence coprime to $n$. Also, note that $n \geq 2p_1p_2\dots p_k \geq p_1p_2\dots p_k+4 \iff p_1p_2 \dots p_k \geq 4$ which is true since $n>6$. (The only case where it is violated is where $p_1=3$ so $n = 6$). Therefore the common difference of the AP at maximum is $2$, so it would cover all odd primes in the factorisation, a contradiction. The only case where it does not, is when there is no odd prime in the prime factorisation ! This means that $n$ is a power of $2$ which is easily seen to work $\blacksquare$

Does this work? The condition says that the positive integers less than and relatively prime to $n$ form an arithmetic sequence. Case 1: $n$ is odd. Then $1$ and $2$ are relatively prime to $n$, so the common difference of the arithmetic sequence is $1$. But since $n-1$ is in the sequence, this means all of the positive integers less than $n$ are relatively prime to $n$, implying $n$ is prime. Case 2: $4 | n$. Then $\frac{n}{2}-1$ and $\frac{n}{2}+1$ are relatively prime to $n$, so the common difference of the arithmetic sequence is $2$. But since $n-1$ is in the sequence, this means all the odd positive integers less than $n$ are relatively prime to $n$, so since $n$ is even $n$ must be a power of $2$. Case 3: $2 || n$. Then $\frac{n}{2}-2$ and $\frac{n}{2}+2$ are relatively prime to $n$, so the common difference of the arithmetic sequence is $4$. Since the sequence contains $1$ and $n-1$, it contains all the positive integers less $n$ which are $1$ mod $4$. In particular, $3 | n$. But if $n = 9$, $7$ is not in the sequence but relatively prime to $n$, a contradiction. If $n > 9$, $9$ is in the sequence but not relatively prime, also a contradiction.

My soln not seen above solutions yet when n is a prime it is trivial, now let n be prime power then it's easy to see n is power of 2, So now let n be non prime power composite number , then let it,s smallest divisor greater than 1 be p , then 1,2...p-1 are co prime to n so common difference would be 1,we can easily check p =2 gives the previous soln Claim 1: : No such n is there Proof : $2-1...= a_p-(p-1) $ But this mean a_p is p and is coprime to n CONTRADICTION!!! Hence the claim and result.

It is easy to check that primes and powers of $2$ satisfy the condition. Also, the condition readily gives $a_1<a_2<\ldots<a_k$. Assume that $n$ is not prime and odd. Hence, $a_2=2$ and $a_2-a_1=2-1=1$. As $n>6$, $n-1=a_k\neq a_2=2$, and to keep the condition satisfied we must have $\gcd(n,k)=1$ for all $1\le k<n$, implying that $n$ is prime, violating our assumption. Now assume that $n$ is not prime even, and not a power of $2$. Let $p$ be the smallest prime not dividing $n$. Now we must have $a_2=p$, because if there was otherwise another number $q>1$ coprime to $n$ smaller then $p$ then $q$ would have a prime factor $r$ smaller than $p$, which must in turn be also relatively prime to $n$, which is non-sense. Hence, in order for the condition to be fulfilled, we must have $$a_1=1,a_2=p,a_3=2p-1,a_4=3p-2,\ldots,a_k=n-1$$Hence, $p-1|(n-1)-1$. But clearly $p-1|n$, so $p-1|2$, i.e. $p=2$ or $p=3$. In these cases, we get that $n$ must be prime or a power of $2$, respectively, so we are done.

Really good problem! We do casework on $a_2$. If $a_2=2,3$, we can easily obtain $n$ is a prime or a power of two, respectively. Now let $a_2=p>3$, so that we obtain $a_3=2p-1$ (the difference is apparently $p-1$). Note that by summing, $(k-1)(p-1)=n-2$. Now we finish by modulo $3$: if $p \equiv 2 \pmod 3$, then $3|2p-1$, but $3|n$, absurd; otherwise $3|n-2$, but we have again $3|n$ due to the fact that $a_2>3$, contradiction.

Note that there are $\phi(n)$ terms, with the first term being $1$ and the last term being $n-1$, so the common difference is $$d=\frac{n-2}{\phi(n)-1}.$$Now, consider any prime $p$ dividing $n$. If $p>2$, then $d$ is relatively prime to $p$ since $p$ does not divide $n-2$ if it divides $n$. However, if $d$ is relatively prime to $p$, there exists some $0\leq s\leq p-1$ for which $$1+ds\equiv 0\pmod{p}.$$However, since we need the entire arithmetic progression to be relatively prime to $n$ (and thus to $p$), we must have $$\phi(n)-1\leq p-2\rightarrow \phi(n)\leq p-1.$$Since $\phi(p)$ is already $p-1$, and $\phi$ is multiplicative, we also have $\phi(n)\geq p-1$, with equality at $n=p$ and $n=2p.$ We can rule out $n=2p$ since then $$d=\frac{2p-2}{p-2}=2+\frac{2}{p-2},$$which is only an integer for $p=3$ but we require $n>6$, so this case is resolved. Otherwise, there is no prime $p>2$ dividing $n$, so $n$ is a power of 2 and we are done.

$a_2-a_1=a_3-a_2=...a_k-a_{k-1}>0 \implies a_1<a_2.....<a_k \implies (a_2-1)(k-1)+2=n$ For odd $n, (a_2-1)$ has to be odd and since $a_2$ is the least prime the doesnt divide $n$ (trivial),$a_2=2 \implies $ every positive integer less than $n$ is coprime to $n \implies $ $n$ is a odd prime. If $n$ even, write $n=2^{\alpha_1}.{p_2}^{\alpha_2}......{p_j}^{\alpha_j}.$ Now, $(p_c-1)(k-1)+2==2^{\alpha_1}.{p_2}^{\alpha_2}......{p_j}^{\alpha_j}$ where $p_c=a_2$ ; taking $p_c-1=2f$, we get $f(k-1)+1=2^{\alpha_1-1}.{p_2}^{\alpha_2}......{p_j}^{\alpha_j} \cdots (i)$. Note that $a_2=3$ makes $n$ a power of $2$. So suppose $a_2>3$. Now take the least prime $p_i$, from the canonical factorization of $n$, such that $p_i$ and $p_{i+1}$ has at least one prime between them. The least of these 'in-between' primes $=p_c$. (If theres no prime between any $p_i$ and $p_{i+1}$ for $1 \leq i \leq k-1$ then the same argument we give below holds because then there would be no primebetween $p_k$ and $p_c$.)Thus the prime factors of $p_c-1$ will also be the factor of $n$. Now if any prime besides $2$ divides $p_c-1$ we get a contradiction in $(i) \implies p_c-1=2^z$. Now as $z$ has to be odd since otherwise $3|2^z-1=p_c$. But then$3|a_3=2^{z+1}-1$ which is a contradiction since $(3,n)=3$. So we are done. The existence of $a_3$ is assured by the fact that for all $n>6, k \geq4$ by the formula for eulers totient function.

Forgot that I did this problem a year ago already so here is another solution (which I like but which is more complicated): If $n$ is odd then $a_{i+1}-a_i=1$, so in fact $a_i=i$ as $a_1=1$. Thus $n$ is relatively prime to all numbers smaller than $n$, so $n$ is prime. Otherwise $n$ is even. If now assume that $n$ has at least one odd prime divisor, and let $q$ be the smallest. Also, let the smallest odd prime not dividing $n$ be $p$, so that $a_1=1, a_2=p, a_3=2p-1, a_4=3p-2,\ldots$ so that in general, $a_i=(i-1)p-(i-2)\iff a_i=1+(i-1)(p-1)$. The idea is now to seek a contradiction by showing that some $a_i$ is $0\mod q$ at least once. Consider $i-1\in I=\{0,1,\ldots,q-1\}$. We now notice that in total, there are $\phi(n)$ numbers $a_k$ relatively prime to $n$, but as $\phi(n)\ge\sqrt{n}\ge q$ for $n>6$ the, index set $I$ delivers $a_i$ that are all relatively prime to $n$. However note that as $\gcd(p-1,q)=1$, the set $(p-1)I+1$ is still a complete residue system modulo $q$, so there exists one $i\in I$ such that $a_i\equiv 0\mod q$, a contradiction.

It is not hard to see that $6$, primes, and powers of $2$ work where the arithmetic sequence formed by the invertible elements have common differences $4$, $1$, and $2$, respectively. We now show that they are the only possibilities. If $n$ is prime then we are done, so suppose $n$ is composite. Claim. $2 \mid n$. Proof. Suppose the contrary. Then, $2$ is a canonical reduced residue modulo $n$, so the arithmetic sequences must start with $1$,$2$ and have a common difference $2-1=1$. It follows that all residues up to $n-1$ are relatively prime to $n$, which could only happen if $n$ is prime, contradiction. $\blacksquare$ Now, suppose $p$ is the least prime that does not divide $n$. If $p$ is the only prime that does not divide $n$, we must have $\phi(n)=2$, which could only happen if $n=3,4,6$, all of which fall into the aforementioned categories of working solutions. Otherwise, suppose $q$ is the second least prime that does not divide $n$. Claim. $1 < p < q < p^2$, and the arithmetic sequence starts with $1,p,q$. Proof. For the sake of contradiction suppose $p^2<q$, so the sequence starts with $1,p,p^2$. It follows that $p-1 = p^2-p$, or $p^2-2p+1=(p-1)^2=0$, so $p=1$, which is absurd. $\blacksquare$ Thus, $1,p,q$ form an arithmetic sequence, implying that $q=2p-1$. Note that the smallest composite number in the sequence is $p^2$, so we have the sequence $$1,p,2p-1,3p-2, 4p-3, \cdots, p^2, \cdots$$where all terms in the form $kp-(k-1)$ before $p^2$ are either $1$ or prime. Note that the term preceding $p^2$ must be $p^2-(p-1)$, and this term is preceded by the subsequence $$p^2-4p+4, p^2-3p+3,p^2-2p+2.$$However, $p^2-4p+4=(p-2)^2$ cannot be prime, so we must have $$(p-2)^2 = 1$$which implies that $p=3$. The sequence thus becomes $$1,3,5,7,\cdots$$which means every odd number up to $n$ is coprime to $n$, which only happens if and only if $n$ is a power of $2$, so we are done by exhausting all cases. $\blacksquare$