Elementary number theory( divisor) If $n= 2009$, then $A=2009^n-1982^n-1972^n+1945^n$ is NOT divisible by.. 


*

*659

*1977

*1998 

*2009 


Please someone let me know how to solve these kind of problems. 
 A: Hint $\ $ Both $\,659\,$ and $\,1977 = 3\cdot 659\,$ are divisors of $A\,$ since 
$$ 2009+1945 = 6\cdot659 = 1982+1972$$
so the paired summands are negatives of each other mod $659$ and $3\cdot 659\,$ so cancel out in $A$, i.e.
$\quad \begin{align}\color{#0a0}{2009\equiv -1945}\\ \color{#c00}{1982\equiv -1972}\end{align}$ $\ \ \Rightarrow\ \ $  $\begin{align} &\quad\ \color{#0a0}{2009}^n\ +1945^n -\quad\,\color{#c00}{1982}^n\ -\ 1972^n\\
\equiv\ &(\color{#0a0}{-1945})^n+1945^n-(\color{#c00}{-1972})^n-1972^n\equiv\, 0\ {\rm\ by\ n\ odd}\end{align}$ 
Similarly, rearranging the first equations, we get cancelling pairs of terms mod $27$ and $37$ 
$$\begin{align} 
2009-1982=27 = 1972-1945\\
2009-1972=37 = 1982-1942\end{align}$$
So $27$ and $37$ divisors of $A\,$ and by parity $2$ is too, thus so is their product $\,2\cdot 27\cdot 37 = 1998$.
That leaves $\,2009\,$ (choice $4)$ as the only possible nondivisor.

Remark $\ $ Abstracting the above argument immediately yields the following
Theorem $\ $ If $\ a,b,c,d\,$ are integers such that $\ a+b+c+d=0\,$ and $\,f(x)\,$ is an odd polynomial with integer coefficients then $\,f(a)+f(b)+f(c)+f(d)\,$ is divisible by $\,a+b,\, a+c,\, a+d$.
Above is the special case $\, f(x) = x^{\large 2009},\, $ and $\ a,b,c,d\, =\, 2009,-1982,-1972,1945$.
A: We have $1945\equiv -2009 \pmod {1977}$ and $1972\equiv -1982 \pmod {1977} .$
If $x\equiv -y \pmod z$, and $n$ is odd, then $x^n\equiv -y^n \pmod z.$ That is, $x^n+y^n\equiv 0\pmod z.$
So $2009^n+1945^n$ and $1982^n+1972^n$  are both divisible by $1977.$ Since $1977=(3)(659) $, they are both divisible by $659$ too.
Sorry I'm too tired right now to say more.
A: The best method I can think of is educated trial-and-error.
Let's try $659$.
$$2009^n - 1982^n - 1972^n + 1945^n \equiv 32^n - 5^n - (-5)^n + (-32)^n \pmod{659}$$
which, for odd $n$ like $2009$, is obviously $0$.
What about $1977$? Well, $1977 = 659 \times 3$ and a little more observation about the sizes of the numbers will tell us that the above equivalence is the same.
$1998$? $$2009^n - 1982^n - 1972^n + 1945^n \equiv 11^n - (-16)^n - (-26)^n + (-53)^n \pmod{1998}$$ This seems like a candidate, we'll come back to it later.
$2009$? Well, a hint here is that $n = 2009$ too. We can factorize $2009  = 7^2 \times 41$ and by Fermat's Little Theorem, we know $41$ divides the expression; we now have
$$2009^n - 1982^n - 1972^n + 1945^n \equiv - 22^n - 12^n + 34^n \pmod{49}$$
Since this is a multiple choice-question, I would leave this here because it looks like the congruence will be $0$ only when $n$ is $1$ or something similar (check out Euler's Totient Theorem), and choose $2009$.
