If d|b, (ak ... a1a0)b Is Divisible By dj If And Only If (aj-1 ... a1a0)b Is Divisible By dj

If \(d|b\), then \(d^j | b^j\), so:

$$ b^j ≡ 0 \bmod d^j \implies a_j b^j ≡ 0 \bmod d^j $$

If \(d^j | b^j\), then \(d^j | b^h\) where \(h \gt j\):

$$ b^h ≡ 0 \bmod d^j \implies a_h b^h ≡ 0 \bmod d^j $$

This means:

$$ a_k b^k + a_{k-1} b^{k-1} + \cdots + a_j b^j ≡ 0 \bmod d^j $$

If \(d^j | (a_{j-1} \ldots a_1 a_0)_b\), then:

$$\begin{align} (a_{j-1} b^{j-1} + \cdots + a_1 b + a_0 &≡ 0 &&\bmod d^j) \quad \wedge \\ (a_k b^k + a_{k-1} b^{k-1} + \cdots + a_j b^j &≡ 0 &&\bmod d^j) \implies \\ a_k b^k + \cdots + a_1 b + a_0 &≡ 0 &&\bmod d^j \end{align}$$

This means if \(d|b\) and \(d^j | (a_{j-1} \ldots a_1 a_0)_b\), then \(d^j | (a_k \ldots a_1 a_0)_b\).

Conversely, suppose \(d|b\) and \(d^j | (a_k \ldots a_1 a_0)_b\). If \(d|b\), then \(d^j | b^j\), which means:

$$ a_k b^k + a_{k-1} b^{k-1} + \cdots + a_j b^j ≡ 0 \bmod d^j $$

If \(d^j | (a_k \ldots a_1 a_0)_b\):

$$\begin{align} (a_k b^k + \cdots + a_1 b + a_0 &≡ 0 &&\bmod d^j) \quad \wedge \\ (a_k b^k + a_{k-1} b^{k-1} + \cdots + a_j b^j &≡ 0 &&\bmod d^j) \implies \\ a_k b^k + \cdots + a_1 b + a_0 - (a_k b^k + a_{k-1} b^{k-1} + \cdots + a_j b^j) &≡ 0-0 && \bmod d^j \\ \therefore a_{j-1} b^{j-1} + \cdots + a_1 b + a_0 &≡ 0 &&\bmod d^j \end{align}$$

This means if \(d|b\) and \(d^j | (a_k \ldots a_1 a_0)_b\), then \(d^j | (a_{j-1} \ldots a_1 a_0)_b\), and that completes the proof.

Since \(2|10\), then an integer is divisible by \(2^j\) if the last \(j\) digits are divisible by \(2^j\). Similarly, an integer is divisible by \(5^j\) if the last \(j\) digits are divisible by \(5^j\)

Styles

(uses cookies)