Show $\,1897\mid 2903^n - 803^n - 464^n + 261^n\,$ by induction

Solution 1:

(I missed out the "by induction" in the question when I wrote this answer, but I will leave it here anyway. Do feel free to have it removed.)

I remember this as a classic Olympiad problem for factorization.

We can rewrite the given expression as:

$$(2903^n - 803^n) - (464^n - 261^n)$$

Then, factorizing (using the difference of powers factorization) we get:

$$(2903 - 803)(\dots) - (464 - 261)(\dots)$$ $$= 2100\cdot(\dots) - 203(\dots)$$

which is divisible by $7$. (I've omitted the expression in the bracket, but the important thing is that they are integers)

Next, we can also rewrite the given expression as:

$$(2903^n - 464^n) - (803^n - 261^n)$$

Factorizing, we get:

$$(2903 - 464)(\dots) - (803 - 261)(\dots)$$ $$=2439\cdot(\dots) - 542\cdot(\dots)$$

which is divisible by $271$ (because $271$ divides both $2439$ and $542$).

Since both $7$ and $271$ divides the given expression, it follows that $7\cdot271 = 1897$ must also divide it.

Solution 2:

Hint $\ $ Exploit innate $\rm\color{#c00}{symmetry}$! $ $ Consider a simpler analogous example

$\qquad\phantom{\Rightarrow}\ \ \{ 52,\ \ \ \ 23\}\ \ \equiv\, \{2,\ \ \ 3\}\ \ \ \ {\rm mod}\,\ 10,7,\ \ $

$\qquad\Rightarrow\ \{52^n,\ \ 23^n\} \equiv \{2^n,\ \,3^n\}\,\ {\rm mod}\,\ 10,7,\ \ $ by the Congruence Power Rule

$\qquad\Rightarrow\ \ \ 52^n\!+\! 23^n\ \ \equiv \ \ 2^n\!+3^n\ \ \,{\rm mod}\,\ 10,7,\ \ $ so also $\,{\rm mod}\ 70 = {\rm lcm}(10,7)$

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\}.\ $ Your problem is completely analogous since

$\qquad\!\phantom{\Rightarrow} \{2903,\, 261\}\ \equiv\ \{803,\, 464\}\,\ {\rm mod}\,\ 271,7,\ \, $ where $\,\ 271\cdot 7 = 1897$

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

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

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

Solution 3:

Let

$$S_n = 2903^n - 803^n - 464^n + 261^n$$

$S_1 = 1897$ so the statement is true for $n=1$.

Assume true for n, and evaluate for (n+1):

$$S_{n+1} = 2903^{n+1} - 803^{n+1} - 464^{n+1} + 261^{n+1}= $$ $$=261\cdot S_n + 2642\cdot 2903^n - 542\cdot803^n - 203\cdot464^n$$

The first term divides by $1897$ by assumption. Let

$$T_n = 2642\cdot2903^n - 542\cdot803^n - 203\cdot464^n$$

If we can prove that $T_n$ divides by 1897 then we are done. Proceed by induction (again). $T_1 = 7140308 = 3764\cdot1897$, i.e. $T_1$ divides by 1897. Assume true for n and evaluate for (n+1).

$$T_{n+1} = 2642\cdot2903\cdot2903^n -542\cdot803\cdot803^n - 203\cdot464\cdot464^n =$$ $$=464\cdot T_n + (2903-464)\cdot2642\cdot2903^n - (803-464)\cdot542\cdot803^n$$

Again the first term by assumption divides by 1897 and let $$U_n = 6443838\cdot2903^n - 183738\cdot803^n$$

Now we just need to prove that $U_n$ divides by 1897. Proceed (yet again) by induction. $U_1 = 18558920100 = 9783300\cdot1897$. So $U_1$ divides by 1897. Assume true for n and evaluate for (n+1).

$$U_{n+1} = 6443838\cdot2903\cdot2903^n - 183738\cdot803\cdot803^n =$$ $$=803\cdot U_n +6443838\cdot(2903-803)\cdot2903^n$$

again the first term divides by 1897 (by assumption). The second term = $6443838\cdot2100\cdot2903^n = 13532059800\cdot 2903^n$ and $13532059800 = 7133400\cdot 1897$, so $U_{n+1} $ divides by 1897.

(phew !! ).