5. What remainder do we get when the number $2002^{2001}$ is divided by 2003? Justify your answer.

Mathematical Competition for High School Students in Slovenia

## Optional Competition

March 28, 2003

## Problems for 3rd Year Students
II/5. 1. way If the number $a$ gives a remainder of 2002 when divided by 2003, then $a=2003 \cdot a^{\prime}+2002$ for some integer $a^{\prime}$. The product 2002 $\cdot$ a gives a remainder of 1 when divided by 2003, because

$$
2002 \cdot a=2003 \cdot 2002 \cdot a^{\prime}+2002^{2}=2003 \cdot\left(2002 \cdot a^{\prime}+2001\right)+1
$$

If the number $b$ gives a remainder of 1 when divided by 2003, then $b=2003 \cdot b^{\prime}+1$ for some integer $b^{\prime}$. The product $2002 \cdot b$ gives a remainder of 2002 when divided by 2003, because

$$
2002 \cdot b=2003 \cdot 2002 \cdot b^{\prime}+2002
$$

From this, we conclude that the powers of the number 2002 alternately give remainders of 2002 and 1 when divided by 2003. The power $2002^{2001}$ has an odd exponent, so it gives a remainder of 2002 when divided by 2003.

2. way Let $a=2003$. When we expand $(a-1)^{2001}$, all terms except $(-1)^{2001}=-1$ are divisible by $a$. This term has a remainder of 2002 when divided by 2003. Therefore, the remainder is 2002.
3. way The above conclusion can be written using congruences: from $2002 \equiv-1(\bmod 2003)$, it follows that $2002^{2001} \equiv$ $(-1)^{2001} \equiv-1 \equiv 2002(\bmod 2003)$.
4. way Discovery that the remainders when dividing the powers of the number 2002 by 2003 are alternately equal to 1 and 2002: 3 points. Justification of this discovery (i.e., why the pattern repeats): 3 points. Conclusion that the remainder is equal to 2002: 1 point.
5. way Writing $2002=2003-1: 2$ points. Using the formula $(2003-1)^{2001}=2003^{2001}-\ldots-1: 3$ points. Conclusion that the remainder is equal to 2002: 2 points.
6. way Discovery $2002 \equiv-1(\bmod 2003): 2$ points. Calculation with congruences: 4 points. Conclusion: 1 point.