Find all natural numbers $n$ for which there is a permutation $(p_1,p_2,...,p_n)$ of numbers $(1,2,...,n)$ such that sets $\{p_1 +1, p_2 + 2,..., p_n +n\}$ and $\{p_1-1, p_2-2,...,p_n -n\}$ are complete residue systems $\mod n$.
Problem
Source: Serbian National Olympiad 2012, Problem 4
Tags: modular arithmetic, number theory proposed, number theory
05.04.2012 05:16
04.11.2012 08:10
mahanmath wrote:
I don't understand "symbols" $n \mid \frac{n(n+1)(2n+1)}{3}$ mean that And can you prove with $\gcd(6,n)=1$
04.11.2012 09:21
The symbol $a \mid b$ means "$a$ divides $b$"; for example $6\mid 12$ but $6\nmid 13$. The man just provided an example for $\gcd(6,n)=1$ at his Step 3, namely $p_i \equiv 2i \pmod{n}$ (since then $p_i+i \equiv 3i\pmod{n}$ will form a complete system of residues, while $p_i-i \equiv i\pmod{n}$).
29.12.2021 03:38
We claim the answer is all $n\equiv 1,5\pmod{6}.$ Let $S_k\equiv 1^k+2^k+\dots+n^k\pmod{n}.$ Notice that \begin{align*}S_1\equiv\sum_{i=1}^{n}{(p_i+i)}\equiv 2S_1&\pmod{n}\\ \implies\frac{n(n+1)}{2}\equiv 0&\pmod{n}\end{align*}so $2\nmid n.$ Also, \begin{align*}2S_2\equiv\sum_{i=1}^{n}{(p_i+i)^2}+\sum_{i=1}^{n}{(p_i-i)^2}\equiv 4S_2&\pmod{n}\\ \implies 2\cdot\frac{n(n+1)(2n+1)}{6}\equiv 0&\pmod{n}\end{align*}so $3\nmid n.$ If $n\equiv 1,5\pmod{6},$ let $\{p_1,p_2,\dots,p_n\}=\{2,4,\dots,2n\}.$ Then, $$\{p_1+1,p_2+2,\dots,p_n+n\}=\{3,6,\dots,3n\}$$which is a complete residue system modulo $n.$ Also, $$\{p_1-1,p_2-2,\dots,p_n-n\}=\{1,2,\dots,n\}.$$$\square$