Problem 1702

Solution:
The answer is all even integers and all powers of $3$. First we show that these work.

- When $N$ is even, all $c_{i}$ are odd, and so $2 \mid \gcd (N, c_{i} + c_{i + 1})$ for every $i$.

- When $N$ is a power of $3$, the $c_{i}$ are exactly the numbers in the range $1, 2, \ldots, N - 1$ that are not divisible by $3$. So, the sequence $c_{1}, \ldots, c_{m}$ alternates between numbers congruent to $1$ (mod $3$) and $2$ (mod $3$). Thus $3 \mid \gcd (N, c_{i} + c_{i + 1})$ for every $i$.

Now we show that no other positive integer works. For the sake of contradiction, consider an odd candidate $N$ that is not a power of $3$, and suppose it satisfies the problem condition. Then, since $c_{1} = 1$ and $c_{2} = 2$, we have $\gcd (N, 1 + 2) \neq 1$, so $3 \mid N$. Thus, we can write $N$ as $3^{k} M$, where $k \geq 1$ and $\gcd (M, 6) = 1$. We have $M \geq 5$ (as $M \neq 1$ by assumption) and $M + 2 < N$.

We now split into two cases based on $M$ modulo $3$.

Case 1. $M \equiv 1$ (mod $3$).
As $3 \mid M - 1$ and $M \mid M$, neither $M - 1$ nor $M$ are in the sequence $\{c_{i}\}$. As $M$ is odd and $M \equiv 1$ (mod $3$), $M - 2$ and $M + 1$ are congruent to $1$ (mod $3$), are coprime to $M$, and are smaller than $N$. Thus, both $M - 2$ and $M + 1$ are in the sequence, and they are consecutive terms. However, this means $\gcd (N, 2M - 1) \neq 1$. This gives a contradiction, as both $3$ and $M$ are coprime to $2M - 1$.

Case 2. $M \equiv 2$ (mod $3$).
This case is similar to Case 1. Neither $M$ nor $M + 1$ are in the sequence, but $M - 1$ and $M + 2$ are. We obtain a similar contradiction from $\gcd (N, 2M + 1) \neq 1$.

Solution:
We give an alternative way to show that any odd $N$ has to be the power of $3$. Suppose for contradiction that $N$ has at least $2$ distinct prime factors. Choose integers $a, b > 1$ such that
$$ab \mid N$$
- $a$ and $b$ are coprime;
- Every prime divisor of $N$ divides $ab$.

We use the Chinese Remainder Theorem, to find an integer $n \in [1, ab]$ such that
$$\left\{ \begin{array}{ll} n \equiv 1 \pmod{a}, \\ n \equiv 2 \pmod{b}. \end{array} \right.$$
We claim that there is an index $i$ such that $c_{i} = n - 3$ and $c_{i + 1} = n$. Indeed, we note the following:

- $n$ is consecutive to a multiple of $a$, so $\gcd(a, n) = 1$. In a similar way we get that $\gcd(b, n - 3) = 1$.
- $n$ is $2$ away from a multiple of $b$, therefore as $2 \nmid b$, $\gcd(b, n) = 1$. In a similar way we get that $\gcd(a, n - 3) = 1$.
- $n \leq ab \leq N$ and $n - 3 \geq (a + 1) - 3 > 0$ as $a > 2$.

This implies that $n$ and $n - 3$ are coprime with $N$, whereas neither $n - 2$ nor $n - 1$ are coprime with $N$, which proves our claim. Finally, we claim that $c_{i} + c_{i + 1} = (n - 3) + n = 2n - 3$ is coprime with $N$. Indeed we have $2n - 3 \equiv -1 \pmod{a}$ and $2n - 3 \equiv 1 \pmod{b}$. This implies that $N$ is a prime power.

When $N$ is odd, since $c_{1} = 1$ and $c_{2} = 2$, we have $\gcd(N, 1 + 2) \neq 1$, so $3 \mid N$, which implies that $N$ is necessarily a power of $3$. This concludes our proof.