ポタージュを垂れ流す。

マイペースこうしん(主に旅行)

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の倍数ってことです.