# Remainder when $2009^{2009}-1982^{2009}-1972^{2009}+1945^{2009}$ is divided by $1998$

Find Remainder when $N=2009^{2009}-1982^{2009}-1972^{2009}+1945^{2009}$ is divided by 1998

I have written the given number $N$ as

$$N=(1998+11)^{2009}-(1998-16)^{2009}-(1998-26)^{2009}+(1998-53)^{2009}$$ and by binomial theorem the remainder when $N$ divided by $1998$ is

$$R=11^{2009}+16^{2009}+26^{2009}-53^{2009}$$

but how to find remainder when $R$ is divided by $1998$

• the next step should be using Euler's Totient Function, isn't! Aug 4, 2017 at 2:50
• (Hint) Use eulers theorem that $a^{\phi(n)}\equiv 1 \mod n$ where $\phi(n)$ is Euler Totient function. Also $\phi(1998) = 648$ Aug 4, 2017 at 2:50

The problem has innate $$\rm\color{#c00}{symmetry}$$ that greatly simplifies matters once brought to the fore.

\begin{align} 2009-1982 = 27,\quad 2009-1972 = 37\\ 1972-1945 = 27,\quad 1982-1945 = 37\end{align}

Thus $$\phantom{\Rightarrow}\ \ \{ 2009,\ \ \ 1945\}\ \ \equiv\, \{1982,\ \ \ 1972\}\ \ \ \ {\rm mod}\,\ 27\ \&\ 37,\$$

$$\qquad\Rightarrow\ \{2009^n,\ \ 1945^n\} \equiv \{1982^n,\ \,1972^n\}\,\ {\rm mod}\,\ 27 \ \&\ 27,\$$ by the Congruence Power Rule

$$\qquad\Rightarrow\ \ \ 2009^n\!+\! 1945^n\ \ \equiv \ \, 1982^n\!+1972^n\ \ \ {\rm mod}\,\ 27\ \&\ 37,\$$ so also $$\,{\rm mod}\ 999 = {\rm lcm}(27,37)$$

since addition $$\,f(x,y)\, =\, x + y\$$ is $$\rm\color{#c00}{symmetric}$$ $$\,f(x,y)= f(y,x),\,$$ therefore its value depends only upon the (multi-)set $$\,\{x,\ y\}.\,$$ Parity $$\,\Rightarrow\,$$ congruent mod $$2,\,$$ so also mod $$\,2\cdot 999 = 1998.$$

Remark  Generally if a polynomial $$\,f\in\Bbb Z[x,y]\,$$ is $$\rm\color{#c00}{symmetric}$$ then as above we deduce

$$\qquad\qquad\quad \{A, B\}\, \equiv\, \{a,b\}\,\ {\rm mod}\,\ m\ \&\ n\ \Rightarrow\ f(A,B)\equiv f(a,b)\, \bmod{\,{\rm lcm}(m,n)}$$

a generalization of CCRT =constant-case optimization of CRT = Chinese Remainder, plus a generalization of the Polynomial Congruence Rule to (symmetric) bivariate polynomials.

• See this answer for a generalization. May 25, 2019 at 17:14

Using the fact that when $n$ is odd, $$a^n + b^n = (a+b)(a^{n-1}-a^{n-2}b+\cdots+(-1)^{n-1}b^{n-1})$$ and similarly $$a^n - b^n = (a-b)(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}),$$ we note that $$R = (11^{2009}+16^{2009})+(26^{2009}-53^{2009})\equiv 0 \pmod {27}$$ because $11+16 = 27$ and $26-53 = -27$.

Similarly, we note that $$R = (11^{2009}-53^{2009})+(16^{2009}+26^{2009})\equiv 0 \pmod {42}.$$

Finally, we note that $$R = (11^{2009}+26^{2009})+(16^{2009}-53^{2009})\equiv 0 \pmod {37}.$$

Therefore, $R$ is a multiple of $27$, $37$, and $42$. Note that $27 * 37 = 999$, and that $42$ is even. Therefore, $R$ is a multiple of $1998$, meaning that $$\fbox{R \equiv 0 \pmod{1998}}$$