数酸

数学に関して書き留めておこうと思ったものを気まぐれに。

負の進法による整数表現

その他

 

{M}を2以上の整数として以下のような{-M}進法による整数の表示が考えられる。

{\displaystyle (a_n a_{n-1}...a_0)_{-M}=\sum_{k=0}^n a_k(-M)^k }　　

但し　{ a_k \in \{ 0,1,2,..,M-1 \} }　

{0}以外の表示においては {a_n \neq 0} 

命題　{-M}進法によって任意の整数が一意に表現できる

 

ことを確認する。

 証明

まず一意性を証明する。移項することで

{\displaystyle \sum_{k=0}^n b_k(-M)^k }=0　　

{ b_k \in \{-(M-1),..,-1,0,1,..,M-1 \} }　

ならば任意の{k}で{b_k=0}を示せばよい。

そうでないと仮定すると{b_k \neq 0}となる最小の{k}が存在するので、それを{k_0}とする。{(-M)^{k_0} }で割ると

{\displaystyle b_{k_0}-M \sum_{k=k_0+1}^n b_k(-M)^{k-k_0-1 }=0}　

左辺は明らかに{M}の倍数でないので矛盾する。

次に任意の整数が表現できることを示す。

整数{A}に対して{A-a}が{M}の倍数となるような{a \in \{ 0,1,..,M-1 \}}が存在する。もし{B=(A-a)/(-M)}が{-M}進法表示可能ならば{A}も{-M}進法表示可能。実際

{\displaystyle B=(a_n a_{n-1}...a_0)_{-M} }

なら

{\displaystyle A=(a_n a_{n-1}...a_0 a)_{-M} }

と表示できる。

{\displaystyle |B| \lt |A| }　

{\displaystyle \Leftrightarrow |A-a| \lt M|A| }

{\displaystyle \Leftarrow |A|+a \lt M|A| }

{\displaystyle \Leftrightarrow \frac{a}{M-1} \lt |A| }

であるから{|A| \gt 1}ならば{A}の表示可能性は{A}より絶対値の小さい整数の表示可能性に帰着する。{0,1}は明らかなので{-1}が{-M}進法表示できることだけ確認すればよいが

{\displaystyle -1=(M-1)+1 \times (-M)=(1,M-1)_{-M} }

となる。□