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

Question

Related (but different) question: Is it true that $76^n=76\pmod{100}$ for all $n>0$?

If you raise $76$ to an integer power ($n\ge2$) and ignore the last two digits, it appears that you always have an integer that is divisible by $57$, because the prime factorisation always seems to involve $3$ and $19$:

$76^2$ = 5776, and 57 = 3 x 19

$76^3$ = 438976, and 4389 = 3 x 7 x 11 x 19

$76^4$ = 33362176, and 333621 = 3 x 3 x 19 x 1951

$76^5$ = 2535525376, and 25355253 = 3 x 7 x 11 x 19 x 53 x 109

$76^6$ = 192699928576, and 1926999285 = 3 x 5 x 19 x 71 x 95231

$76^7$ = 14645194571776, and 146451945717= 3 x 3 x 7 x 11 x 19 x 1951 x 5701

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

Using the formula for the sum of a geometric series: $$ \begin{align} \frac{76^n-76}{76-1} &=76\,\frac{76^{n-1}-1}{76-1}\\ &=76\left(76^{n-2}+76^{n-3}+\cdots+1\right) \end{align} $$ Therefore, since $75\cdot76=5700$, $$ \begin{align} \frac{76^n-76}{100} &=57\left(76^{n-2}+76^{n-3}+\cdots+1\right) \end{align} $$