BMO Short List

The answer is in the affirmative. Letting $\equiv$ denote congruence modulo $p^n$ throughout the argument, we will show that there exists a permutation $a_1,a_2,\dots ,a_N$ of the numbers in $U$ such that ${\sum }_{k=1}^N{a}_k{a}_{k+1}\equiv p^{n-1}$.

Let $m=p^{n-1}-1$, so $N=p^{n-1}(p-1)=(m+1)(p-1)$, and write $U=\{u_1,u_2,\dots ,u_N\}$, where $u_k=k+\lfloor k/(p-1)\rfloor$, $k=1,2,\dots ,N$, and $\lfloor t\rfloor$ denotes the largest integer (strictly) less than the real number $t$.

That the $u_k$ are pairwise distinct and they all lie in $U$ follows from the fact that every $k$ in the range $1,2,\dots ,N$ is uniquely expressible in the form $k=(p-1)j+i$ for some $j$ in the range $0,1,\dots ,m$ and some $i$ in the range $1,2,\dots ,p-1$. Thus, $u_k=u_{(p-1)j+i}=pj+i$, so the $u_k$ are indeed pairwise distinct and they all lie in $U$.

For $k$ in the range $1,2,\dots ,N-1$, notice that $u_{k+1}-u_k=1$, unless $k$ is divisible by $p-1$, in which case $u_{k+1}-u_k=2$. Setting $u_{N+1}=u_1$, it is readily checked that $u_{N+1}-u_N=2-p^n\equiv 2$, so $u_{k+1}-u_k\equiv 2$ for all $k$ divisible by $p-1$.

Letting now $a_k$ be the multiplicative inverse of $u_k$ modulo $p^n$, i.e., $a_k$ is the unique member of $U$ satisfying $a_k{u}_k\equiv 1$, we show that the $a_k$ form the desired permutation of $U$.

To begin with, notice that $a_k{a}_{k+1}\equiv a_k-a_{k+1}$, unless $k$ is divisible by $p-1$, in which case $a_k{a}_{k+1}\equiv \frac{1}{2}(a_k-a_{k+1})$. This is easily established by multiplying both sides of each congruence by $u_k{u}_{k+1}$, and noticing that $(a_k-a_{k+1})u_k{u}_{k+1}\equiv u_{k+1}-u_k\equiv 1\text{ or }2$.

We are now in a position to evaluate the sum $S={\sum }_{k=1}^N{a}_k{a}_{k+1}$ modulo $p^n$. Write $$S=\sum _{k=1}^N{a}_k{a}_{k+1}=\sum _{j=0}^m\sum _{i=1}^{p-1}{a}_{(p-1)j+i}{a}_{(p-1)j+i+1},$$ and consider the inner sum for a fixed $j$ in the range $0,1,\dots ,m$: $$\begin{array}{rl}\sum _{i=1}^{p-1}{a}_{(p-1)j+i}{a}_{(p-1)j+i+1}& =\sum _{i=1}^{p-2}{a}_{(p-1)j+i}{a}_{(p-1)j+i+1}+a_{(p-1)j(j+1)}{a}_{(p-1)(j+1)+1}\\ & =\sum _{i=1}^{p-2}(a_{(p-1)j+i}-a_{(p-1)j+i+1})+\frac{1}{2}(a_{(p-1)j(j+1)}-a_{(p-1)(j+1)+1})\\ & =a_{(p-1)j+1}-a_{(p-1)(j+1)}+\frac{1}{2}(a_{(p-1)j(j+1)}-a_{(p-1)(j+1)+1})\\ & =a_{(p-1)j+1}-\frac{1}{2}{a}_{(p-1)j(j+1)}-\frac{1}{2}{a}_{(p-1)(j+1)+1}.\end{array}$$

Hence $$\begin{array}{rl}S& \equiv \sum _{j=0}^m{a}_{(p-1)j+1}-\frac{1}{2}\sum _{j=0}^m{a}_{(p-1)(j+1)}-\frac{1}{2}\sum _{j=0}^m{a}_{(p-1)(j+1)+1}\\ & \equiv \left(a_1+\sum _{j=1}^m{a}_{(p-1)j+1}\right)-\frac{1}{2}\sum _{j=1}^{m+1}{a}_{(p-1)j}-\frac{1}{2}\left(\sum _{j=1}^m{a}_{(p-1)j+1}+a_{N+1}\right)\\ & \equiv \frac{1}{2}\sum _{j=1}^{m+1}{a}_{(p-1)j+1}-\frac{1}{2}\sum _{j=1}^{m+1}{a}_{(p-1)j}.\end{array}$$ Since $u_{(p-1)j+1}=pj+1$, the $a_{(p-1)j+1}$ form a permutation of the $pj+1$, therefore ${\sum }_{j=1}^{m+1}{a}_{(p-1)j+1}={\sum }_{j=1}^{m+1}(pj+1)$. Similarly, $u_{(p-1)j}=pj-1$, so the $a_{(p-1)j+1}$ form a permutation of the $pj-1$, and hence ${\sum }_{j=1}^{m+1}{a}_{(p-1)j}={\sum }_{j=1}^{m+1}(pj-1)$. Consequently, $$S\equiv \frac{1}{2}\sum _{j=1}^{m+1}((pj+1)-(pj-1))\equiv m+1\equiv p^{n-1},$$ as stated in the first paragraph. This completes the solution.