If d|(b+1), Then d|(ak ... a1a0)b if and only if d|((-1)kak + ... + a2 - a1 + a0)

If \(d|(b+1)\), then \(b ≡ -1 \bmod d\), and \(b^j ≡ (-1)^j \bmod d\).

$$ \begin{align} (a_k a_{k-1} \ldots a_0)_b &≡ a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 \bmod d \\ &≡ a_k (-1)^k + a_{k-1} (-1)^{k-1} + \cdots + a_1 (-1)^1 + a_0 \bmod d \\ &≡ (-1)^k a_k \cdots + a_2 - a_1 + a_0 \bmod d \end{align}$$

Styles

(uses cookies)