About $5$ years ago, Joydip was researching on the number $2017$. He understood that $2017$ is a prime number. Then he took two integers $a,b$ such that $0<a,b <2017$ and $a+b\neq 2017.$ He created two sequences $A_1,A_2,\dots ,A_{2016}$ and $B_1,B_2,\dots, B_{2016}$ where $A_k$ is the remainder upon dividing $ak$ by $2017$, and $B_k$ is the remainder upon dividing $bk$ by $2017.$ Among the numbers $A_1+B_1,A_2+B_2,\dots A_{2016}+B_{2016}$ count of those that are greater than $2017$ is $N$. Prove that $N=1008.$
Problem
Source: BdMO 2022 Secondary P6
Tags: number theory
12.04.2022 08:28
If $1\leq i,j \leq 2016$ and $i+j=2017$ then $(A_i+B_i)+(A_j+B_j)=4034$. Hence, exactly one of $A_i+B_i, A_j+B_j$ are greater than $2017$. (Obviously, $A_k+B_k\neq 2017$.)
22.12.2023 12:43
$\color{green} \boxed {\textbf{SOLUTION P6}}$ We have, $$A=(A_i, 1\le i \le 2016)=(ai, 1\le i\le 2016) \equiv (1,2,3...,2016) \pmod {2017}$$ $$B=(B_i, 1\le i \le 2016)=(bi, 1\le i\le 2016) \equiv (1,2,3...,2016) \pmod {2017}$$ $$S=A+B=(A_i+B_i, 1\le i \le 2016)=((a+b)i, 1\le i\le 2016) \equiv (1,2,3...,2016) \pmod {2017}$$ So $A_i+B_i$ represent the sum(modulo $2017$) of remainders of $A_i$ and $B_i$ modulo $2017$ that is every element is Set $S$ is the sum of two remainders of mod $2017$ $S$ contains $(1 \to 2016)$ exactly once. Here we get, $A_i+B_i=k, 1\le k \le 2016$ or $A_i+B_i=2017+k,1\le k \le 2016$ Also note, $A_i+B_i=2018$ and $A_i+B_i=2016$ as $A_i+B_i$ can't be $1$ or $4033 > 2\times 2016$ FTSOC, Assume There exist at most $1006 j$'s such that $A_i+B_i > 2017$ for $2\le i \le 2015$ And atleast $1008 i$'s such that $A_i+B_i \le 2017$ So, $$\sum_{i=2}^{2015} {A_i +B_i=4062238} \le \sum_{i=2015}^{1008} {i} + \sum_{j=2019}^{3024} {j}= 4060221 \le \sum_{i \in (2 \to 2015), |i| \ge 1008} {i} + \sum_{j \in (2019 \to 4032), |j| \le 1006} {j}$$Which is a contradiction So we must have $1007$ element from $A_i+B_i, 2\le i \le 2015$ s.t $A_i+B_i > 2017$ and we had some $k$ such that $A_k+B_k=2018>2017$ before. Hence we are done $\blacksquare$