1. ## divisible by 100

Prove that if the difference of the integers a, b is divisible by 100, then
$\displaystyle a^{100}-b^{100}$
is divisible by 10 000.

2. Originally Posted by perash
Prove that if the difference of the integers a, b is divisible by 100, then
$\displaystyle a^{100}-b^{100}$
is divisible by 10 000.
The best way to answer this depends on how much Math you've had.

Here's one way:
If (a - b)|100 then we can say that (a - b)k = 100, where k is a positive integer.

Thus $\displaystyle b = a - \frac{100}{k}$. So
$\displaystyle a^{100} - b^{100} = a^{100} - \left ( a - \frac{100}{k} \right )^{100}$

$\displaystyle = a^{100} - \sum_{i = 0}^{100} (-1)^i{100 \choose i} a^{100 - i} \cdot \left ( \frac{100}{k} \right )^i$

$\displaystyle = a^{100} - a^{100} - \sum_{i = 1}^{100} (-1)^i{100 \choose i} a^{100 - i} \cdot \left ( \frac{100}{k} \right )^i$ <-- Singling out the first term of the summation

$\displaystyle = -\sum_{i = 1}^{100} (-1)^i{100 \choose i} a^{100 - i} \cdot \left ( \frac{100}{k} \right )^i$

Now, each term in the series is divisible by at least 100 due to the factor of $\displaystyle \frac{100}{k}$. But there is another 100 involved: from the $\displaystyle 100 \choose i$, i > 0. So all terms are divisible by at least 10000.

-Dan