Elementary number theory( divisor)

Question

If $n= 2009$, then $A=2009^n-1982^n-1972^n+1945^n$ is NOT divisible by..

1. 659
2. 1977
3. 1998
4. 2009

Please someone let me know how to solve these kind of problems.

Answer 1

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

Answer 2

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.

Answer 3

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