3
$\begingroup$

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$

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
2
$\begingroup$

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}$}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.