# Math Help - Proving divisibility

1. ## Proving divisibility

Originally Posted by the undertaker
Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
First of all, these numbers are really small for computers to handle, so a direct calculation isn't hard.

If you need to make the numbers smaller, you can use the Chinese remainder theorem and the fact that 174 = 2*3*29. (Although that might be more work in the end than just using 174.) You can also factor 20 = 2*10, and 4 = 2*2. Shouldn't be all that hard...

By the way, if you really have to do everything on paper, you can see this thread (post #7) for a description of fast modular exponentiation.

Edit: Upon further reflection, using the Chinese remainder theorem definitely results in less work. Mod 2, we see that from left to right we have an even minus an odd plus an even minus an odd, resulting in an even, so it is congruent to 0 (mod 2). Mod 3, the first two terms are both 2^22 (mod 3) and so together are 0 (mod 3), and the next term is simply 1^33 (mod 3) which is 1 (mod 3), so we see that the expression is congruent to 0 (mod 3). Now all we have to do is show that the expression is congruent to 0 (mod 29) and we are done. Working mod 29 should be more manageable on paper than 174. For 4^33 you can use Fermat's little theorem to get that 4^33 = 4^28*4^5 is congruent to 4^5 (mod 29).

Moderator edit: This post was moved from a thread created by a duplicate post. Unfortunately I misread the time stamps on both threads, which is why this post preceeds the original post (which is post #2 below). Apologies for any confusion.

2. ## Proving divisibility

Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.

3. Originally Posted by the undertaker
Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
Note that $174 = 2\cdot 3 \cdot 29$ we need to prove it is the multiple of 2 , 3 and 29 separately .

It is easy to prove it is divisible by 2 and 3 , i give them yo you .

I will prove it is divisible by 29 .

$20^{22} - 17^{22} + 4^{33} - 1$

$= (4^{22}5^{22}) +4^{33} - (17^{22} + 1)$

$= (4^{22}5^{22}) + (4^{22}4^{11}) - ((17^2)^{11} + 1)$

$= 4^{22} ( 5^{22} + 4^{11} ) - (289^{11} + 1)$

$\equiv 4^{22} ( 5^{22} + (-25)^{11}) - ( (289-290)^{11} + 1) \bmod{29}$

$\equiv 4^{22} ( 25^{11} - 25^{11}) - ( -1 + 1) \bmod{29} \equiv 0 \bmod{29}$

EDIT :

Is it a odd or an even number ?

And note that

$20 \equiv -1 \bmod{3}$
$17 \equiv -1 \bmod{3}$
$4 \equiv 1 \bmod{3}$

4. Thanks simplependulum,
but could you also prove it divisble by 2 and 3?
cheers.

5. Originally Posted by the undertaker
Thanks simplependulum,
but could you also prove it divisble by 2 and 3?
cheers.
I already did this in my post.. was it not clear?