Thread: Problem to prove "always divisible by"

1. Problem to prove "always divisible by"

Hi guys! I did not know how to write this out with the math language here so here's a screen shot from word :> Thanks!

2. Hello !
Originally Posted by ride12
Hi guys! I did not know how to write this out with the math language here so here's a screen shot from word :> Thanks!

Here is your question in LaTeX language (click on it to see the code) :

$\displaystyle \forall n \ge 0,\text{ show that } 157^{2n+1}+1098^{2n+1}+46^{2n+1}+707^{2n+1} \text{ is always divisible by 2008.}$
Let this number be N.

The first reflex will be "We may be able to do it by induction". Nope, the numbers are such that it will be difficult (if not impossible).

I hope you're familiar with using modulus.
-------------------------------------------------------------
Note that $\displaystyle 2008=8 \times 251$
Since 8 and 251 are coprime, if a number is divisible by 8 and 251, then it is divisible by 2008.
We'll study the numbers modulo 8.

$\displaystyle 157=8 \times 20-3 \implies 157 \equiv -3 \bmod 8.$
$\displaystyle \text{Thus } 157^{2n+1} \equiv (-3)^{2n+1} \bmod 8 \equiv -3^{2n+1} \bmod 8$

$\displaystyle 1098=8 \times 137+2 \implies 1098 \equiv 2 \bmod 8.$
$\displaystyle \text{Thus } 1098^{2n+1} \equiv 2^{2n+1} \bmod 8$

$\displaystyle 46=8 \times 6-2 \implies 46 \equiv -2 \bmod 8.$
$\displaystyle \text{Thus } 46^{2n+1} \equiv (-2)^{2n+1} \bmod 8 \equiv -2^{2n+1} \bmod 8$

$\displaystyle 707=8 \times 88+3 \implies 707 \equiv 3 \bmod 8.$
$\displaystyle \text{Thus } 707^{2n+1} \equiv 3^{2n+1} \bmod 8$

Therefore $\displaystyle N \equiv -3^{2n+1}+2^{2n+1}-2^{2n+1}+3^{2n+1} \bmod 8$
$\displaystyle \implies N \equiv 0 \bmod 8$

$\displaystyle \boxed{\text{8 divides N}}$

------------------------------------------------------------
Now, does 251 divide N ?

$\displaystyle 157=0 \times 251+157=1 \times 251-94 \implies 157 \equiv -94 \bmod 251$
$\displaystyle \text{Thus } 157^{2n+1} \equiv -94^{2n+1} \bmod 251$

$\displaystyle 1098=4 \times 251+94 \implies 1098 \equiv 94 \bmod 251$
$\displaystyle \text{Thus } 1098^{2n+1} \equiv 94^{2n+1} \bmod 251$

$\displaystyle 46=0 \times 251+46 \implies 46 \equiv 46 \bmod 251$
$\displaystyle \text{Thus } 46^{2n+1} \equiv 46^{2n+1} \bmod 251$

$\displaystyle 707=2 \times 251+205=3 \times 251-46 \implies 707 \equiv -46 \bmod 251$
$\displaystyle \text{Thus } 707^{2n+1} \equiv -46^{2n+1} \bmod 251$

Therefore $\displaystyle N \equiv -94^{2n+1}+94^{2n+1}+46^{2n+1}-46^{2n+1} \bmod 251$
$\displaystyle \implies N \equiv 0 \bmod 251$

$\displaystyle \boxed{\text{251 divides N}}$

And we're done !

3. Originally Posted by Moo

Note that $\displaystyle 2008=8 \times 251$
Since 8 and 251 are coprime, if a number is divisible by 2008, then it is divisible by 8 and by 251.
I think that should be: a number is divisible by 2008 if and only if it is divisible by 8 and by 251. Otherwise you haven't proved it.