Every Tenth Power of Two Minus Every Third Power of Ten is Divisible By Three

From ProofWiki
Jump to navigation Jump to search



Theorem

Let $x \in \Z_{\ge 0}$ be a non-negative integer.

Then $2^{10 x} - 10^{3 x}$ is divisible by $3$.


That is:

$2^{10 x} - 10^{3 x} \equiv 0 \pmod 3$


Proof

\(\ds 2^{10 x}\) \(=\) \(\ds \paren {2^{10} }^x\) Power of Power
\(\ds \) \(=\) \(\ds 1024^x\) as $2^{10} = 1024$
\(\ds \) \(=\) \(\ds \paren {1000 + 24}^x\) rewriting $1024$ as the sum of a power of $10$ and some integer
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 0}^n 1000^{x - k} \, 24^k\) Binomial Theorem
\(\text {(1)}: \quad\) \(\ds \) \(=\) \(\ds 1000^x + \sum_{k \mathop = 1}^n 1000^{x - k} \, 24^k\) extracting first term from summation
\(\ds \) \(=\) \(\ds 1000^x + 24 \paren {\sum_{k \mathop = 1}^n 1000^{x - k} \, 24^{k - 1} }\) extracting $24$ as a divisor
\(\ds \leadsto \ \ \) \(\ds 2^{10 x} - 1000^x\) \(=\) \(\ds 24 i\) setting $i = \ds \sum_{k \mathop = 1}^n 1000^{x - k} \, 24^{k - 1}$
\(\ds \leadsto \ \ \) \(\ds 2^{10 x} - 10^{3 x}\) \(=\) \(\ds 24 i\) rewriting $1000^x$ as a power of $10$
\(\ds \) \(=\) \(\ds 3 k\) setting $k = 8 i$
\(\ds \leadsto \ \ \) \(\ds 2^{10x} - 10^{3 x}\) \(\equiv\) \(\ds 0 \pmod 3\) Definition of Congruence Modulo Integer

$\blacksquare$


Examples



Let us examine arguably the flagship example, the smallest number whose compliance is not obvious nor trivial:

$1 \, 048 \, 576$

This is equal to $2^{20}$, which is equal to $2^{10 \times 2}$, thus one of the valid powers of $2$.

We then subtract $10^{3 \times 2}$, or $10^6$:

$1 \, 048 \, 576 - 1 \, 000 \, 000 = 48 \, 576$

and we see that:

$48 \, 576 = 16 \, 192 \times 3$

satisfying the theorem.