Find all odd positive integers $n>1$ such that there is a permutation $a_1, a_2, a_3, \ldots, a_n$ of the numbers $1, 2,3, \ldots, n$ where $n$ divides one of the numbers $a_k^2 - a_{k+1} - 1$ and $a_k^2 - a_{k+1} + 1$ for each $k$, $1 \leq k \leq n$ (we assume $a_{n+1}=a_1$).
Problem
Source: International Zhautykov Olympiad 2013 - D1 - P2
Tags: modular arithmetic, number theory proposed, number theory
mlequi
17.01.2013 19:40
Lemma : Given a prime $p \geq 5$, there exists $q$ such that $\left( \frac{q+1}{p} \right)= -1$ and $\left( \frac{q-1}{p} \right) = -1$, where $\left( \frac{q+1}{p} \right)$ denotes the Lagrange symbol.
Proof of lemma : For $p=5$, statement is true.
Suppose not. Since the number of $1$ and $-1$ in the sequence $\left( \frac{1}{p} \right),\left( \frac{2}{p} \right),\ldots,\left( \frac{p-1}{p} \right)$ is the same, then the sequence of $\left( \frac{1}{p} \right),\left( \frac{2}{p} \right),\ldots,\left( \frac{p-1}{p} \right)$ is obviously either $1,1,-1,-1,1,1,-1,-1,...$ or $1,-1,-1,1,1,-1,-1,...$. In both cases $\left( \frac{6}{p} \right) \neq \left( \frac{2}{p} \right) \left( \frac{3}{p} \right)$, contradiction. (lemma proved)
Suppose $p>5$ divides $n$. Let $q$ be a number satisfying our lemma, i.e $\left( \frac{q+1}{p} \right)= -1$ and $\left( \frac{q-1}{p} \right) = -1$. Note that we must have $a_k=q$ for some $k$. This means
\[ b^2 - q \equiv \pm 1 \pmod{p} \]
must have a solution, which is impossible. Thus, the only prime that can divide $n$ is $3$, i.e $n=3^k$ for some $k$.
Now, set $n=3^k$ and suppose $k \geq 2$. Let $m = 3^us$, where $u \geq \frac{k}{2}$, and $3$ does not divide $s$. Then, we have for the next number (if $a_s=m$, then we are talking about $a_{s+1}$) $t$, we have $t \equiv \pm 1 \pmod{n}$. The same happens when $m=0$.
However, there are only $2$ of such $\pm 1$ in mod $n$, namely $1$ and $-1$ themselves.
Thus, there can only be two such $m$'s. Now if $k \geq 2$, then $0,3^u,2 \times 3^u$ where $u \geq \frac{k}{2}$ are such three $m$'s, contradiction.
Therefore, we have $k < 2$, so $n=3$. It is easy to check that $n=3$ is indeed a solution.
siddigss
18.01.2013 19:23
An easier solution .. !!
The problem is $n|a_k^2-a_{k+1}+\epsilon _k$ , $\epsilon_k $ is $1$ or $-1$ , $\forall k\in\left\{1,2,...,n\right\}$
Clearly $a_s\equiv a_r( \mod n )\Leftrightarrow s\equiv r ( \mod n ) $
All the following congruences are mod n
We claim that if $k\not\equiv l$ such that $a_k^2\equiv a_l^2$ ,then $\epsilon _k\not=\epsilon _l$
Assume not . We have $a_k^2-a_{k+1}+\epsilon _k\equiv a_l^2-a_{l+1}+\epsilon _l \Leftrightarrow a_{k+1}\equiv a_{l+1}\Leftrightarrow l+1\equiv k+1 $ . Contradiction !
Let $a_k=i$ , assume that $\alpha_i=\epsilon _k$ . Using what we proved above , we get $\alpha_{i}=-\alpha_{n-i}$ $\forall i\in\left\{1,2,...,\frac{n-1}{2}\right\}$ .
we have
$n|\sum_{i=1}^{n}(a_i^2-a_{i+1}+\epsilon _i)=\sum_{i=1}^ni^2-\sum_{i=1}^ni+\sum_{i=1}^n\epsilon _i$
$=\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}+\sum_{i=1}^n\alpha_i=\frac{n(n+1)(n-1)}{3}+\alpha_n$
$\Rightarrow n|n(n+1)(n-1)+3\alpha_n\Leftrightarrow n|3$ since $\alpha_n\in\left\{1,-1\right\}$
Therefore $n=3$ which is easy to see that it satisfies the problem condition
mto
19.01.2013 17:23
Lemma: For $n = 2k+1$, then among any $k + 2$ numbers in the set $\{1,2,\ldots,n\}$ there always exist two numbers whose sum equals $n$. Proof: Consider the $k$ pairs $(1, n-1) , (2, n-2), \ldots, (k, k+1)$. For arbitrary $k + 2$ numbers from $\{1,2,\ldots, n\}$, there are two numbers falling into the same pair ... For each $i$, let $c_i$ belong to the set $\{-1, 1\}$, with $n \mid a_i^2 - a_{i+1} + c_i$. Denote $A = \{ i \mid c_i = 1 \}$ and $B= \{ i \mid c_i = -1\}$; using the lemma we have that if $\textrm{card}(A)$ or $\textrm{card}(B)$ exceed $k +1$, then there are two different indices $i, j$ such that $a_i + a_j$ is divisible by $n$ (and $c_i=c_j$). But then $n \mid (a_i^2 + a_{i+1} + c_i) - (a_j^2 + a_{j+1} + c_j)$, therefore $n\mid a_{i+1} - a_{j+1}$, impossible. Therefore we have $\textrm{card}(A) = k$ and $\textrm{card}(B) = k + 1$, or $\textrm{card}(A) = k + 1$ and $\textrm{card}(B) = k$. (*) We have $1^2 + 2^2 + \cdots + n^2 - (1 + 2+ \cdots + n) + (c_1 + c_2 + \cdots + c_n)$ is divisible by $n$. From (*) we have $c_1 + c_2 + \cdots + c_n = 1$ or $-1$; that yields $n = 3$.
thomasmikava
03.01.2016 16:12
mto wrote: From (*) we have $c_1 + c_2 + \cdots + c_n = 1$ or $-1$ mto, please explain Why this implies that $n = 3$
Assassino9931
08.01.2022 05:31
Here is a somewhat different solution. A good first try to kill almost all $n$ is "size reasons". In detail, we want $a_{k+1} \equiv a_k^2 \pm1 \pmod {n}$ and here the left hand side, as $k$ varies from $1$ to $n$, attains $n$ values (since the $a_k$-s are given to be a permutation of $\{1,2,\ldots,n\}$. Now if $A$ is the number of different squares mod $n$, then the right-hand side attains at most $2A$ different values. In particular $2A\geq n$ and so $A \geq \frac{n+1}{2}$, as $n$ is odd. On the other hand, there are at most $\frac{n+1}{2}$ squares mod $n$ (as $x^2 = (n-x)^2 \pmod n$ for $x=0,1,\ldots,\frac{n-1}{2}$) and if $n$ is composite (and odd) with prime divisor $p$, then $x^2 \equiv y^2 \pmod n$ with $x\not\equiv \pm y$ is possible for $x-y = p, x+y = \frac{n}{p}$, i.e. $x = \frac{p+\frac{n}{p}}{2}$, $y = \frac{\frac{n}{p} - p}{2}$ and so there are two additional equal squares, hence overall at most $\frac{n-1}{2}$ squares mod $n$, contradiction. Therefore $n$ must be prime. Moreover, in this case we cannot have all $\pm$ to be $+$ or all to be $-$ as then the right-hand side would attain just $\frac{n+1}{2} < n$ different values. Now "size reasons" seem hard to deal with prime $n$ on their own, so we have to try something additional. Let us add all $a_{k+1} \equiv a_k^2 \pm1 \pmod {n}$ and denote the sum of the $\pm 1$-s by $B \in (-n,n)$ (we cannot have $B=\pm n$ due to the end of the previous paragraph). Then since the $a_k$-s permute $\{1,2,\ldots,n\}$, we must have $\sum_{i=1}^{n}a_i \equiv \frac{n(n+1)}{2}$ and $\sum_{i=1}^{n}a_i^2 \equiv \frac{n(n+1)(2n+1)}{6}$, hence $3n(n+1) \equiv n(n+1)(2n+1) + 6B \pmod n$ - in particular, $n$ must divide $6B$. Now for prime $n\geq 5$ this immediately implies $n\mid B$ - together with $B \in (-n,n)$ this forces $B=0$ but this is impossible, as the number of $\pm 1$-s is $n$, which is odd, and hence $B$ must be odd. So it remains to check only $n=3$ and we see it is a solution with the permutation ($1$, $2$, $3$).