Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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 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.
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}$}$$
