1
$\begingroup$

The task states:

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

247 | 285⋅n23 + 209⋅n11

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⋅123 + 209⋅111 = 494

494 is divisible by 247, so we continue.

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

247 | 285⋅n23 + 209⋅n11; 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)23 + 209⋅(n+1)11

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?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Not really, we haven't exercised such problems.. $\endgroup$
    – Mr. Nicky
    Sep 10, 2016 at 13:33
  • $\begingroup$ @Mr.Nicky, As $(285,209,247)=13$ the problem reduces to $$13|(285n^{23}+209n^{11})$$ But as $209=1+13\cdot16,285=13\cdot22-1$ $$13(285n^{23}+209n^{11})\iff13\mid-n^{10}(n^{13}-n)$$ Now use artofproblemsolving.com/wiki/… for $13\mid(n^{13}-n)$ $\endgroup$ Sep 10, 2016 at 13:37
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Wow, thanks..!!! $\endgroup$
    – Mr. Nicky
    Sep 10, 2016 at 14:05
  • $\begingroup$ You are welcome. $\endgroup$
    – Piquito
    Sep 10, 2016 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .