Prove that $76$ raised to any integer power and then divided by $100$ (ignoring the remainder) is always divisible by $57$

Once we accept that $76^n$ always ends in $76$, your question becomes: is it always true that $$ \frac{76^n - 76}{100} $$ is always divisible by $57$ (that is, by both $3$ and $19$)?

It's enough to focus on the numerator $76^n - 76$, since the denominator $100$ has no factors of $3$ or $19$ in it. The numerator

• is obviously divisible by $19$, since $76 = 4 \cdot 19$, and
• becomes $1^n - 1$ when we reduce it modulo $3$,

so it's divisible by $57$.

Another way to look at it:

$\frac {76^n - 76}{100} = \frac {76(76^{n-1} - 1)}{100} = \frac {19(76^{n-1}-1)}{25} = 19* \frac {(76 -1)(76^{n-2} + 76^{n-3} + ...... + 76 + 1)}{25} =$

$19*\frac {75(76^{n-2} + 76^{n-3} + ...... + 76 + 1)}{25} = 3*19*(76^{n-1} + 76^{n-2} + ...... + 76 + 1)$

So that's that.

But there so some interesting observations. If $n = m + 1$ is odd and $m$ is even then: $(76^{n-1=m} - 1) = (76^{2} - 1)(76^{m-2}+76^{m-4} + ... + 1) = (76-1)(76 + 1)(76^{m-2}+76^{m-4} + ... + 1)$ so $7=7*11|7^{n-1} - 1$ so for ever odd $n$, $57*77$ will divide it.

Likewise if $n = 3m + 1$ for some $m$ then $(76^{3m} - 1) = (76-1)(76^2 + 76 + 1)(76^{3m -3} + 76^{3m-6}.... + 1) = 7*(3*1951)*(76^{3m -3} + 76^{3m-6}.... + 1)$.

So for $n = 4,7,10, etc.$ you will get $3*19*3*1951$ will divide the values.

And we can find these patterns all day long.

$n = km + 1$ will always mean $76^{m-1}+ 76^{m-2} + ... + 76+ 1$ will divide the result.

For $n = 4m + 1$ we well always have $\frac{(76^2 + 1)(76^2 - 1)}{25}=3*53*109*7*11$ will always divide the results.

And so on.

Split the numbers in two parts, separating the last two digits from the rest.

We can easily calculate:

$$76^2 = 5776 = 57\cdot100 + 76$$

Clearly the hundreds part is divisible by $57$. But note that the low part is again $76$.

Let's assume that we can write the powers like this (with some integer $k_n$):

$$76^n = 57 \cdot k_n \cdot100 + 76 $$

then

$$76^{n+1} = 57 \cdot 76 \cdot k_n \cdot100 + 5776 $$ $$ = (57 \cdot 76 \cdot k_n + 57) \cdot 100 + 76 $$

$$ = 57 \cdot (76 \cdot k_n + 1) \cdot 100 + 76 $$

And the hundreds part is again divisible by 57. There's also the $76$ in the low part, so $76^{n+1}$ is also in the assumed form ($k_{n+1} = 76 \cdot k_n + 1$). Since the assumption held for $n=2$ ($k_2 = 1$), it also holds for any higher power.

For $n=0$ or $n=1$, the hundreds part is zero, and therefore trivially divisible by anything.