Given an integer $n > 1$, let $1 = a_1 < a_2 < \cdots < a_t = n - 1$ be all positive integers less than $n$ that are coprime to $n$. Find all $n$ such that there is no $i \in \{1, 2, \ldots , t - 1\}$ satisfying $3 | a_i + a_{i+1}$.
Problem
Source: 2024 Brazil Ibero TST P1
Tags: number theory, phi function, coprime
13.10.2024 01:07
I claim all such numbers are $n=4,10$. First, suppose $3\mid n$. Then $a_2\equiv 1\pmod{3}$ and $a_i\not\equiv 0\pmod{3}$. Check that since $a_i+a_{i+1}\in\{1,2\}\pmod{3}$, we must have $a_i\equiv 1\pmod{3}$ for each $i$. This however is a contradiction since $a_t = n-1\equiv 2\pmod{3}$. So, assume $3\nmid n$. Since $a_2\ne 2$, it is evident that $n$ is even. Furthermore, letting $u=t/2$, we have $a_1<a_2<\cdots<a_u<a_{u+1}=n-a_u<\cdots<n-a_2<n-a_1$. If $n\equiv 2\pmod{3}$, then noticing $a_t = n-1\equiv 1\pmod{3}$ and $a_{t-1} = n-3\equiv 2\pmod{3}$, we obtain $3\mid a_{t-1}+a_t$. So, $n\equiv 1\pmod{3}$. Next, we show the sequence is of form $(1,0,1,0,\dots)$ in modulo 3. To see this, note that $a_1+a_2\in\{1,2\}\pmod{3}$ and $n-a_1+n-a_2\equiv 2-(a_1+a_2)\in\{1,2\}\pmod{3}$. So, $a_1+a_2\equiv 1\pmod{3}$. Continuing, we obtain the pattern $(1,0,1,0\dots,1,0)$. Now an implication of this result is that if $q<n$ is a prime with $q\equiv 2\pmod{3}$ then $q\mid n$. We now show this is not possible for $n>10$. Note that $n\equiv 4\pmod{6}$, and $n=4,6$ both work. Assume $n\ge 16$. Then, $2,5,11\mid n$, forcing $n\ge 110$. We next inspect the numbers $n+7,n+1,n+37,n+31,n+67,n+19,n+13$, all of which are distinct modulo 63, and congruent to 5 modulo 6. So, each such number must either (a) be a prime, or (b) have a prime divisor $q\equiv 2\pmod{3}$. Note that since $n\ge 110$ and $q\mid n$ for every $q<110$ and $q\equiv 2\pmod{3}$ prime, we have a clear contradiction unless all these numbers are prime. But then, all of them are greater than 7, and since at least one is divisible by 7, we have another contradiction.