If d|(b-1), Then d|(ak ... a1a0)b If And Only If d|(ak + ... + a1 + a0)

If \(d|(b-1)\), then \(b ≡ 1 \bmod d\), and therefore \(b^j ≡ 1 \bmod d\). This means \(a_j b^j ≡ a_j \bmod d\).

$$\begin{align} (a_k \ldots a_1 a_0)_b = a_k b^k + \cdots + a_1 b + a_0 \\ a_k b^k + \cdots + a_1 b + a_0 ≡ a_k + \cdots + a_1 + a_0 \bmod d \end{align}$$

Therefore, if \(d|(a_k + \cdots + a_1 + a_0)\), then \(d|(a_k b^k + \cdots + a_1 b + a_0)\) and vice versa.

Styles

(uses cookies)