Congruence of Sum of Digits to Base Less 1

From ProofWiki
Jump to: navigation, search


Theorem

Let $x \in \Z$, and $b \in \N, b > 1$.

Let $x$ be written in base $b$:

$x = \left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b$


Then:

$\displaystyle s_b \left({n}\right)\sum_{j \mathop = 0}^m r_j \equiv x \pmod {b-1}$

where $s_b \left({n}\right)$ is the digit sum of $n$.


That is, the digit sum of any integer $x$ in base $b$ notation is congruent to $x$ modulo $b-1$.


Proof

Let $x \in \Z, x > 0$, and $b \in \N, b > 1$.

Then from the Basis Representation Theorem, $x$ can be expressed uniquely as:

$\displaystyle x = \sum_{j \mathop = 0}^m r_j b^j, r_0, r_1, \ldots, r_m \in \left\{{0, 1, \ldots, b-1}\right\}$


Proof by induction:

For all $n \in \N_{>0}$, let $P \left({n}\right)$ be the proposition $\displaystyle \sum_{j \mathop = 0}^n r_j \equiv x \pmod {b-1}$.


Basis for the Induction

$P(1)$ is trivially true:

$\forall x: 0 \le x \le b: x \equiv x \pmod {b-1}$

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\displaystyle \sum_{j \mathop = 0}^k r_j \equiv \sum_{j = 0}^k r_j b^j \pmod {b-1}$


Then we need to show:

$\displaystyle \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv \sum_{j = 0}^{k \mathop + 1} r_j b^j \pmod {b-1}$


Induction Step

This is our induction step:

Let $y$ be expressed as:

$\displaystyle y = \sum_{j \mathop = 0}^{k \mathop + 1} {r_j b^j}, r_0, r_1, \ldots, r_{k+1} \in \left\{{0, 1, \ldots, b}\right\}$


Then:

$\displaystyle y = \sum_{j \mathop = 0}^k r_j b^j + r_{k+1} b^{k+1}$


Now from Congruence of Powers:

$b \equiv 1 \pmod {b-1} \implies b^n \equiv 1^n \pmod {b-1} \implies b^n \equiv 1 \pmod {b-1}$

So by modulo multiplication:

$r_{k+1} b^{k+1} \equiv r_{k+1} \pmod {b-1}$

From the induction hypothesis:

$\displaystyle \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv y \pmod {b-1}$


Thus by modulo addition:

$\displaystyle \sum_{j \mathop = 0}^{k \mathop + 1} r_j \equiv \sum_{j \mathop = 0}^k r_j + r_{k+1} \pmod {b-1}$


Hence $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction:

$\displaystyle \sum_{j \mathop = 0}^n r_j \equiv \sum_{j \mathop = 0}^n r_j b^j \pmod {b-1}$

$\blacksquare$