2進数の3による剰余 - ポタージュを垂れ流す。

命題

整数 $N$ を2進法表記したときに $n$ 桁の数になったとする．このとき，第 $k$ 桁目の数を $a_k$ とおくと， $N$ を3で割ったときの余りは $\displaystyle \sum_{k=1}^n (-1)^{k-1} a_k$ を3で割ったときの余りに一致する．

証明

以下法を3とします． $2^{k-1} a_k$ は2進法では $k$ 桁の数で， $k$ 桁目だけが1で $k-1$ 桁目まで0が並ぶ数です． $N$ はこれを $k=1,2,......,n$ まで足し合わせたものだと考えられるので，
$\displaystyle N= \sum_{k=1}^n 2^{k-1} a_k$
です．ここで整数 $m$ とします．

$k=2m$ のとき
$\displaystyle 2^{2m-1} a_{2m}=2 \cdot 4^m a_{2m} \equiv -a_{2m}$
$k=2m+1$ のとき
$\displaystyle 2^{2m} a_{2m+1}=4^m a_{2m+1} \equiv a_{2m+1}$

よって， $2^k a_k \equiv (-1)^{k-1} a_k$ となりますから，これを $k=1,2,......,n$ まで足し合わせることで，
$\displaystyle \sum_{k=1}^n 2^{k-1} a_k \equiv \sum_{k=1}^n (-1)^{k-1} a_k \Leftrightarrow N \equiv \sum_{k=1}^n (-1)^{k-1}$
が成り立つことがわかり，命題は示されました．

補足とか

普通にラウンジとかいうところで勉強してたら2進法が関係ある問題を出されたので，それにちょっと関連した感じで覚え書きです．シグマとか使って書かれてますけど要は2進法で表されてる数の桁を交互に足し引きしてそれが3の倍数になったら元の数を10進法で表した数も3の倍数ってことです．