Prove that the expression is divisible by 247 for any natural number

Question

The task states:

Prove that for any natural number n∈N the following expression is correct:

247 | 285⋅n²³ + 209⋅n¹¹

My first thought and intuition was to prove it using mathematical induction, because I had solved a similar problem that way before.

So here goes:

Step 1: n = 1, 285⋅1²³ + 209⋅1¹¹ = 494

494 is divisible by 247, so we continue.

Step 2: Let's assume that the expression is true for n, so:

247 | 285⋅n²³ + 209⋅n¹¹; we assume to be true

Step 3: Now we only have to prove that the expression is correct for n + 1, i.e. we have to prove:

247 | 285⋅(n+1)²³ + 209⋅(n+1)¹¹

So around here I got stuck. I thought about the Binomial theorem, but that's about it, didn't know if there's any way to implement it here.

Later on, the professor told me that this problem can't be solved using Mathematical induction and didn't explain how it should be done. Any suggestions?

Answer 1

HINT:

using Modular Arithmetic,

As $247=13\cdot19$ where $(13,19)=1$

$$285n^{23}+209n^{11}\equiv n^{11} -n^{23}\equiv-n^{10}(n^{13}-n)\pmod{13}$$

Now use Fermat's little theorem

Now $(285,209)=19$

Can you take it from here?

Answer 2

$285$ and $209$ are multiples of $19$; furthermore $285\equiv -1\pmod{13}$ and $209\equiv 1\pmod{13}$. Hence $$-n^{23}+n^{11}=n^{11}(-n^{12}+1)\equiv 0\pmod{13}$$ by Fermat's little theorem. Thus the expression is multiple of $19\cdot13=247$ for all $n$.