Joydip's Research


 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, \cdots, A_{2016}$ and $B_1, B_2, \cdots, 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, \cdots, A_{2016} + B_{2016}$ count of those that are greater than $2017$ is $N$. 

Prove that $N = 1008$. 



Proof Based Problems  


  0 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

Step 1:

Prove that $A_k \neq 0$ and $B_k \neq 0$ for all $k$

Proof: For the sake of contradiction, assume that $A_k = 0$.

But, $0 = A_k \equiv ak \pmod{2017}$.

So, $2017\mid ak$

But, 2017 is a prime. So, $2017\mid a$ or $2017\mid k$

But, $a,k<2017$. So, $2017\nmid a$ and $2017\nmid k$

Contradiction. In the same way, $B_k\neq 0$ can be proved.


Step 2: 

Prove that $A_k+B_k \neq 2017m$ for all $k$ and any integer $m$

Proof: For the sake of contradiction, assume that $A_k + B_k \equiv 0 \pmod{2017}$.

But, $0 \equiv A_k+B_k \equiv ak+bk \equiv (a+b)k \pmod{2017}$.

So, $2017\mid (a+b)k$

But, 2017 is a prime. So, $2017\mid a+b$ or $2017\mid k$

But, $a,b,k<2017$ and $a+b\neq 2017$. So, $2017\nmid a+b$ and $2017\nmid k$

Contradiction.


Step 3: 

For $x,y$ with $x+y = 2017$, prove that $A_x+A_y=B_x+B_y=2017$

$A_x+A_y\equiv ax+ay \equiv a(x+y) \equiv 0 \pmod{2017}$

But, $A_x,A_y \neq 0$ and $A_x,A_y<2017$ (remainder when divided by 2017).

So, $0< A_x+A_y < 2\cdot 2017$

So, $A_x+A_y = 2017$

In the same way, $B_x+B_y=2017$ can be proved.


Step 4: 

For $x,y$ with $x+y = 2017$, prove that,  either $A_x+B_x>2017$ and $A_y+B_y<2017$ 

or $A_y+B_y>2017$ and $A_x+B_x<2017$

Proof: From step 3, we have $A_x+A_y=B_x+B_y=2017$

So, $(A_x+B_x)+(A_y+B_y) = A_x+A_y+B_x+B_y = 2\cdot 2017$

But, $A_x+B_x \neq 2017$ from step 2.

So, either $A_x+B_x > 2017 \implies A_y+B_y < 2\cdot2017-2017 = 2017$

Or, $A_x+B_x < 2017 \implies A_y+B_y > 2\cdot2017-2017 = 2017$.


So, with $x+y=2017$, exactly one of $A_x+B_x$ and $A_y+B_y$ is greater than 2017.

There are $\frac{2016}{2} = 1008$ such pairs $(x,y)$. So, there are exactly 1008 $k$ with $A_k+B_k>2017$.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial