3
$\begingroup$

Show that: $2903^n - 803^n - 464^n + 261^n$ is divisible by $1897$ for all integers $n\geq1$ using induction.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ See this answer for a significant generalization. $\endgroup$ – Bill Dubuque Jun 22 '14 at 17:12
2
$\begingroup$

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 !! ).

$\endgroup$
  • $\begingroup$ This amounts to constructing a constant coeff order $4$ recurrence for $\,S_n,\,$ see the explanation here. $\endgroup$ – Bill Dubuque Apr 26 '15 at 21:48

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.