Let $p$ be a prime number. For each $k$, $1\le k\le p-1$, there exists a unique integer denoted by $k^{-1}$ such that $1\le k^{-1}\le p-1$ and $k^{-1}\cdot k=1\pmod{p}$. Prove that the sequence \[1^{-1},\quad 1^{-1}+2^{-1},\quad 1^{-1}+2^{-1}+3^{-1},\quad \ldots ,\quad 1^{-1}+2^{-1}+\ldots +(p-1)^{-1} \] (addition modulo $p$) contains at most $\frac{p+1}{2}$ distinct elements.
Problem
Source: Baltic Way 2010
Tags: modular arithmetic, number theory proposed, number theory
19.11.2010 22:07
I think you forget, that they are distinct in $Z/pZ$.
19.11.2010 22:16
Rust wrote: I think you forget, that they are distinct in $Z/pZ$. It says "addition modulo $p$"
20.11.2010 18:15
A very similar problem appeared in Baltic Way 2010 as problem 18. See http://www.stae.is/bw10/problems [moderator edit: Yeah, this is Baltic Way 2010, user WakeUp has posted all of problems.]. One need to prove only that \[\sum_{i=1}^{p-j}i^{-1}= \sum_{i=1}^{p}i^{-1}\] for some $j\in \{ 1,\ldots,p-1\}$ or the sequence \[1^{-1},\quad 1^{-1}+2^{-1},\quad 1^{-1}+2^{-1}+3^{-1},\quad \ldots ,\quad 1^{-1}+2^{-1}+\ldots +p^{-1} \] contains at most $\frac{p+1}{2}-1$ distinct elements, in which case you might have \[\sum_{i=1}^{p-j}i^{-1}\ne \sum_{i=1}^{p}i^{-1}\] for every $j\in \{ 1,\ldots,p-1\}$.
21.11.2010 03:39
For $p=2$ the sequence contains only 1 element, which is less than $\frac{2+1}2$. Assume $p>2$. Let $S_i=\sum_{k=1}^ik^{-1}$. All congruence henceforth are in modulo $p$. Note that for each $k$, $1\le k\le p-1$, we have $k(p-k)(k^{-1}+(p-k)^{-1})\equiv(p-k)+k\equiv0$, therefore $k^{-1}+(p-k)^{-1}\equiv0$. For $i<\frac{p-1}2$, we have $(i+1)^{-1}+(p-i-1)^{-1}\equiv0$, $(i+2)^{-1}+(p-i-2)^{-1}\equiv0$, $\ldots$, $(\frac{p-1}2)^{-1}+(\frac{p+1}2)^{-1}\equiv0$. Thus $S_i\equiv S_i+(i+1)^{-1}+\ldots+(p-i-1)^{-1}\equiv S_{p-i-1}$. So we get $S_1\equiv S_{p-2}$, $S_2\equiv S_{p-3}$, and so on. We conclude that there are at most $\frac{p+1}2$ distinct elements in the sequence, namely $S_1,S_2,\ldots,S_{\frac{p-1}2},S_{p-1}$.