Problem to prove "always divisible by"

ride12 · #1 $Old$ 08-26-2008, 07:58 PM

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!

Moo · #2 $Old$ 08-27-2008, 03:51 AM

Hello !

Quote:

Originally Posted by ride12 $View Post$

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) :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

And we're done ! $Name: 0039.gif Views: 103 Size: 6.1 KB$

jenius · #3 $Old$ 08-27-2008, 09:05 PM

Quote:

Originally Posted by Moo $View Post$

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