Problem

Source: MOP 2005 Homework - Black Group #27

Tags: number theory unsolved, number theory



Let $p$ be a prime number, and let $0 \le a_1<a_2<...<a_m<p$ and $0 \le b_1<b_2<...<b_n<p$ be arbitrary integers. Denote by $k$ the number of different remainders of $a_i+b_j$, $1 \le i \le m$ and $1 \le j \le n$, modulo $p$. Prove that (i) if $m+n>p$, then $k=p$ (ii) if $m+n \le p$, then $k \ge m+n-1$