0でないp進数の逆数

Last-modified: Thu, 29 Dec 2016 20:25:18 JST (1801d)
Top > 0でないp進数の逆数

ここまでで、「自然数の\( p \)進法表記を拡張する形で整数を\( p \)進数とみなす方法があること」と「\( p \)進数は自然数の足し算と掛け算を延長する形で演算が定義されること」を説明しました。実はそれだけでなく、\( p \)進数の演算が整数の演算を延長していること等の基本的な性質がいくつかあるのですが、「左に無限桁まで伸びる数」という\( p \)進数の定義のままではそれらを直接証明することは非常に面倒です*1。そのため、後に別の方法で\( p \)進数と等価な概念を定義し、実際に\( p \)進数と等価であることを示した上で、そちらの定義を用いて他の基本性質を証明していくことにします。それを踏まえた上で、今後は\( p \)進数の演算が整数の演算を拡張していること、すなわちいかなる整数\( n \)\( m \)に対しても

\begin{eqnarray*} \begin{array}{rcll} n^{(p)} + m^{(p)} & = & (n+m)^{(p)} & (p \textrm{進整数だと思って足した値と、整数だと思って足した値が、同じ} p \textrm{進整数になる}) \\ n^{(p)} \times m^{(p)} & = & (n \times m)^{(p)} & (p \textrm{進整数だと思って掛けた値と、整数だと思って掛けた値が、同じ} p \textrm{進整数になる}) \end{array} \end{eqnarray*}

が成り立つことを認めて使っていきます。

さて、次に「逆数」という概念を考えます。\( 0{} \)でない実数\( a \)にはその逆数、つまり\( x \times a = 1 \)を満たすような実数\( x \)がただ1つ存在しました。\( p \)進数でも同様に次の命題が成り立ちます。

命題1(\( 0{} \)でない\( p \)進数の可逆性)
\( \alpha \)\( 0^{(p)} \)でない\( p \)進数とする。この時、\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)がただ1つ存在する。

先程述べたように、後に\( p \)進数の概念を定義し直すことで、こういった命題も簡単に証明できるようになるのですが、全て後回しにしてしまうのも物寂しいので今の定義のまま\( 0{} \)でない\( p \)進数の可逆性を証明してみようと思います。非常に骨が折れますが、頑張っていきましょう。

まずは\( \alpha \)\( p \)に対応する\( p \)進整数\( p^{(p)} = \cdots 000000000010_{(p)} \)の場合を考えます。\( \cdots 000000000010_{(p)} \)\( p \)進数に掛けることは、筆算を用いた掛け算の定義から単にその\( p \)進数の小数点を右に1つずらすことと一致します。従って、\( x \times p^{(p)} = 1^{(p)} \)という式は「\( x \)の小数点を右に1つずらしたものが\( 1^{(p)} = \cdots 00000000001_{(p)} \)と一致する」ということを言っているので、その解である\( x \)\( \cdots 0000000000.1_{(p)} \)に他なりません。従って、\( (p^{-1})^{(p)} \)\( \cdots 0000000000.1_{(p)} \)として定めます。

次に、\( \alpha \)が自然数\( v \geq 2 \)を用いて\( (p^v)^{(p)} \)と表せる場合を考えます。自然数を\( p \)進数とみなす方法を思い出すと、\( (p^v)^{(p)} \)は「一番右の桁から順に\( v \)\( 0{} \)が並んでその左に\( 1 \)が現れてそれ以降は左にずっと\( 0{} \)が並ぶ\( p \)進整数」となります*2。先程と同様に考えると\( (p^v)^{(p)} \)\( p \)進数に掛けることは小数点を右に\( v \)ずらすことに他なりません。従って、\( x \times (p^v)^{(p)} = 1^{(p)} \)という式は「\( x \)の小数点を右に\( v \)だけずらしたものが\( 1^{(p)} = \cdots 00000000001 \)と一致する」ということを言っているので、その解である\( x \)は「小数点の左は全て\( 0{} \)で小数点以下\( v-1 \)桁まで\( 0{} \)が並び\( v \)桁目に\( 1 \)が現れてそこで表示が止まる\( p \)進数」に他なりません*3。従って、\( (p^{-v})^{(p)} \)をそのような\( p \)進数として定めます。

それでは一般の状況で\( x \times \alpha = 1^{(p)} \)の解\( x \)を探すために、いくつかの命題を準備します。

命題2(加法付値の一意存在性)
\( \alpha \)\( 0^{(p)} \)でない\( p \)進数とする。この時、\( (p^{-v})^{(p)} \times \alpha \)が「\( p \)進整数であって一番右の桁が\( 0{} \)でないもの」となるような整数\( v \)がただ1つ存在する。

証明

まずは\( v \)が少なくとも1つは存在することを示す。筆算を用いた\( p \)進数の掛け算の定義から、\( (p^{-v})^{(p)} \)\( \alpha \)に掛けることは\( \alpha \)の小数点を右に\( -v \)\( v \)が正なら左に\( v \))ずらすことに他ならない。従って、\( \alpha \)\( p \)進整数であれば\( \alpha \)の一番右の桁から\( 0{} \)が並ぶ個数を\( \nu \)と置いて\( v \)\( \nu \)と定義すれば良く、\( \alpha \)\( p \)進整数でないなら\( \alpha \)の小数点以下の桁数(あってもなくても変わらない\( 0{} \)は無視する)を\( \nu \)と置いて\( v = - \nu \)と定義すれば良い。

次に\( v \)が他には存在しないことを示す。そのためには\( (p^{-v'})^{(p)} \times \alpha \)が「\( p \)進整数であって一番右の桁が\( 0{} \)でないもの」となるようないかなる整数\( v' \)\( v \)と一致することを示せば良い。\( (p^{v'})^{(p)} \times ( (p^{-v'})^{(p)} \times \alpha) = ( (p^{v'})^{(p)} \times (p^{-v'})^{(p)}) \times \alpha = 1^{(p)} \times \alpha = \alpha \)より、\( (p^{-v'})^{(p)} \times \alpha \)の小数点を右に\( v' \)\( v' \)が負の場合は左に\( -v' \))ずらしたものが\( \alpha \)となる。\( (p^{-v'})^{(p)} \times \alpha \)は一番右の桁が\( 0{} \)でない\( p \)進整数なので、\( v' \)が正ならば\( \alpha \)の小数点以下の桁数が\( v' \)となり、\( v' \)が負ならば\( \alpha \)\( p \)進整数で勝つ一番右の桁から\( 0{} \)が並ぶ個数が\( -v' \)となる。即ち、\( v' = v \)となる。

加法付値の一意存在性で与えられる\( v \)を、\( \alpha \)の加法的\( p \)付値と呼びます。自然数\( m \geq 1 \)に対応する\( p \)進数\( m^{(p)} \)の定義から容易に分かることとして、\( m^{(p)} \)の加法的\( p \)付値\( m \)が何回\( p \)で割れるかに他なりません。

命題3(\( p \)進単数の特徴付け)
\( \alpha \)を「一番右の桁が\( 0{} \)でない\( p \)進整数」とする。この時、\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)がただ1つ存在する。

\( p \)進単数の特徴付けを証明するには少し手間がかかりますので、その準備としてフェルマーの小定理を紹介します。

定理4(フェルマーの小定理)
\( m \)\( p \)と互いに素な整数とする。この時、\( m^{p-1}-1 \)\( p \)で割り切れる。

フェルマーの小定理を示すための命題を準備します。

命題5(フェルマーの小定理の補題)
\( l \)を整数とする。この時、\( l^p-l \)\( p \)で割り切れる。

証明

まず\( l \geq 0 \)の時に数学的帰納法で示す。\( l=0 \)の時、\( l^p-l = 0^p-0 = 0-0 = 0 \)なので\( p \)で割り切れる。\( l=k \)の時に\( l^p-l \)\( p \)で割り切れると仮定する。二項展開により

\[ (k+1)^p-(k+1) = \left( \sum_{h=0}^{p} {}_p \textrm{C}_h k^h \right) - (k+1) = k^p + \left( \sum_{h=1}^{p-1} {}_p \textrm{C}_h k^h \right) + 1 - (k+1) = (k^p-k) + \sum_{h=1}^{p-1} {}_p \textrm{C}_h k^h \]

となる。帰納法の仮定から\( k^p-k \)\( p \)で割り切れる。かつ\( 1 \leq h \leq p-1 \)なるいかなる自然数\( h \)に対しても、\( {}_p \textrm{C}_h \)は分子にのみ\( p \)の倍数が現れるような分数表示を持つ自然数であり、\( p \)が素数であることから\( p \)で割り切れる。従って\( l=k+1 \)の時も\( l^p-l \)\( p \)で割り切れる。以上より、\( l \geq 0 \)の時、\( l^p-l \)\( p \)で割り切れる。

次に\( l < 0 \)とする。\( l^p-l = (-(-l) )^p+(-l) = ( (-1)^p+1)(-l)^p - ( (-l)^p-(-l) ) \)であり、\( (-1)^p+1 \)がpで割り切れる*4ことと、\( -l > 0 \)であることから、\( l^p-l \)\( p \)で割り切れる。

フェルマーの小定理の補題より、\( m^p-m \)\( p \)で割り切れることが分かる。ここで\( m^p-m = m(m^{p-1}-1) \)であり、\( m \)\( p \)と互いに素でかつ\( p \)は素数であるので、\( m^{p-1}-1 \)\( p \)で割り切れる。

各自然数\( v \)に対し、\( p \)進整数\( \alpha \)の右から\( v+1 \)番目の桁を\( a_v \)と置く。つまり\( a_0, a_1, a_2, \ldots \)\( 0{} \)から\( p-1 \)までの自然数のみからなる数列で、\( \alpha = (\cdots a_2 a_1 a_0)_{(p)} \)である。\( \alpha \)の仮定より、\( a_0 \neq 0 \)である。

\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)がただ1つ存在することを示す。そのためにまず、そのような\( x \)が存在するならばただ1つであることを示す。

\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)が存在すると仮定する。\( x \)\( p \)進整数であることを示す。\( x \)は左に無限桁の小数なので、\( x = (\cdots b_2 b_1 b_0. c_1 c_2 c_3 \cdots c_v)_{(p)} \)と表すことが出来る。ただし\( v \)は自然数*5で、\( b_0, b_1, b_2, \ldots \)\( c_1, c_2, c_3, \ldots, c_v \)\( 0{} \)から\( p-1 \)までの自然数のみからなる数列である。\( v \ge 1 \)かつ\( c_v = 0 \)である場合は\( x = (\cdots b_2 b_1 b_0. c_1 c_2 c_3 \cdots c_{v-1})_{(p)} \)となるので、「\( v = 0 \)」または「\( v \geq 1 \)かつ\( c_v \neq 0 \)」として良い。

後者が起こり得ないことを背理法で示す。\( v \geq 1 \)かつ\( c_v \neq 0 \)とする。筆算を用いた掛け算の定義から、\( x \times \alpha \)の小数点以下\( v \)桁目は\( c_v a_1 \)\( p \)で割った余りに等しく、かつ\( x \times \alpha = 1^{(p)} = \cdots 00000000001_{(p)} \)より、それは\( 0{} \)に他ならない。\( a_1 \)\( 1 \leq a_1 \leq p-1 \)を満たす自然数なので\( p \)の倍数ではなく、\( p \)が素数であることから\( c_v \)\( p \)の倍数である。これは\( c_v \)\( 0 \leq c_v \leq p-1 \)かつ\( c_v \neq 0 \)を満たす自然数であることに反する。以上より\( v = 0 \)である。即ち\( x \)\( p \)進整数となる。

更に、\( b_0, b_1, b_2, \ldots \)を順に求める。自然数\( i \)に対し、\( b_i \)\( \alpha \)のみに依存して(つまり\( x \)の選び方によらず)決まることを帰納法で示す。

まず\( i=0 \)とする。\( x \times \alpha = (\cdots b_2 b_1 b_0)_{(p)} \times (\cdots a_2 a_1 a_0)_{(p)} \)の一番右の桁は\( b_0a_0 \)\( p \)で割った余りである。\( x \times \alpha = 1^{(p)} = \cdots 00000000001_{(p)} \)より、それは\( 1 \)に他ならない。従って、\( b_0a_0 = q_1p + 1 \)を満たすような自然数\( q_1 \)がただ1つ存在する。ここで、フェルマーの小定理により\( a_0^{p-1} \)\( p \)で割った余りは\( 1 \)となることから、\( b_0 \)\( b_0 \times a_0^{p-1} \)\( p \)で割った余りに等しく、\( b_0 \times a_0^{p-1} = b_0 a_0 \times a_0^{p-2} = q_1a_0^{p-2}p + a_0^{p-2} \)より、\( b_0 \)\( a_0^{p-2} \)\( p \)で割った余りに等しい。特に、\( b_i = b_0 \)\( \alpha \)のみに依存して決まる。

\( i > 0 \)として、\( b_0, \ldots, b_{i-1} \)\( \alpha \)のみに依存して決まるとする。\( x \times \alpha \)の一番右から\( i+1 \)桁は\( (\sum_{k = 0}^{i} b_kp^k)(\sum_{k = 0}^{i} a_kp^k) \)\( p^{i+1} \)で割った余りの\( p \)進法表記である。\( x \times \alpha = 1^{(p)} = \cdots 00000000001_{(p)} \)より、それは一番右の桁が\( 1 \)で他の桁が\( 0{} \)である。\( (\sum_{k = 0}^{i} b_kp^k)(\sum_{k = 0}^{i} a_kp^k) = \sum_{k = 0}^{2i} (\sum_{j = \max \{ 0, k-i \}}^{\min \{ k, i \}} b_ja_{k-j})p^k \)であり、これを\( p^{i+1} \)で割った余りは\( \sum_{k = 0}^{i} (\sum_{j = 0}^{k} b_ja_{k-j})p^k \)\( p^{i+1} \)で割った余りに他ならず、それが\( p \)進法表記で\( 1_{(p)} \)となるということは、\( -1 + \sum_{k = 0}^{i} (\sum_{j = 0}^{k} b_ja_{k-j})p^k \)\( p^{i+1} \)で割り切れるということである。従って、\( -1 + \sum_{k = 0}^{i} (\sum_{j = 0}^{k} b_ja_{k-j})p^k = qp^{i+1} \)を満たす自然数\( q \)がただ1つ存在する。\( a_0^{p-1} \)\( p \)で割った余りは\( 1 \)なので、\( b_i \)\( b_i a_0^{p-1} \)\( p \)で割った余りに等しく、\( b_i a_0^{p-1} = qa_0^{p-2}p^{i+1} - (-1 + (\sum_{k = 0}^{i-1} (\sum_{j = 0}^{k} b_ja_{k-j})p^k) + (\sum_{j = 0}^{i-1} b_ja_{i-1-j})p^i) )a_0^{p-2} \)より、\( b_i \)\( - (-1 + (\sum_{k = 0}^{i-1} (\sum_{j = 0}^{k} b_ja_{k-j})p^k) + (\sum_{j = 0}^{i-1} b_ja_{i-1-j})p^i) )a_0^{p-2} \)\( p \)で割った余りに等しい。特に、\( b_i \)\( \alpha \)のみに依存して決まる。

以上より\( b_0, b_1, b_2, \ldots \)は全て\( \alpha \)のみに依存して決まる。即ち、\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)は、存在すればただ1つである。

また、\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)は実際に存在する。何故ならば、上の方法で順に定めた\( b_0, b_1, b_2, \ldots \)を用いて*6\( x \)\( (\cdots b_2 b_1 b_0)_{(p)} \)と定めれば実際に\( x \times \alpha = 1^{(p)} \)を満たすことが全く同じ計算で示される。

以上を用いて、ようやく目的の命題を証明することが出来ます。

まずは\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)の存在を示す。加法付値の一意存在性から、\( \alpha \)付値\( v \)と置けば\( (p^{-v})^{(p)} \times \alpha \)は一番右の桁が\( 0{} \)でない\( p \)進整数となる。従って、\( p \)進単数の特徴付けから、\( y \times ( (p^{-v})^{(p)} \times \alpha) = 1^{(p)} \)を満たす\( y \)が存在する。\( y \times (p^{-v})^{(p)} \)\( x \)と置くと、\( x \times \alpha = (y \times (p^{-v})^{(p)}) \times \alpha = y \times ( (p^{-v})^{(p)} \times \alpha) = 1^{(p)} \)となる。

次に、\( x' \times \alpha = 1^{(p)} \)を満たすようないかなる\( p \)進数\( x' \)も、\( x' = 1^{(p)} \times x' = (x \times \alpha) \times x' = x \times (\alpha \times x') = x \times (x' \times \alpha) = x \times 1^{(p)} = x \)となる。以上より、\( x \times \alpha = 1^{(p)} \)を満たすような\( p \)進数\( x \)はただ1つしか存在しない。

\( 0{} \)でない\( p \)進数の可逆性でただ1つ存在することが保証される\( x \)を、\( \alpha \)の逆数または\( \alpha \)の逆元と呼んで\( \alpha^{-1} \)と表記します。そしていよいよ、この逆数という概念を使うことで、有理数と\( p \)進数の関係を述べることが出来ます。




*1 難しくはないので、余力のある人は挑戦してみると良いです。
*2 例えば&mathjax{(p^2)^{(p)} = \cdots 0000000000100_{(p)}};、&mathjax{(p^3)^{(p)} = \cdots 00000000001000_{(p)}};となります。
*3 つまり&mathjax{v = 2};の時は&mathjax{x = \cdots 0000000000.01_{(p)}};、&mathjax{v = 3};の時は&mathjax{x = \cdots 0000000000.001_{(p)}};のようになります。
*4 &mathjax{p=2};の時は&mathjax{2};で、&mathjax{p \neq 2};の時は&mathjax{0{}};です。
*5 &mathjax{c_1 c_2 c_3 \cdots c_v};という表記は&mathjax{v \geq 5};という意味を内包するように見えますが、慣例上はそうとは限りません。&mathjax{v = 0};の時は&mathjax{x = (\cdots b_2 b_1 b_0)_{(p)}};で、&mathjax{v = 1};の時は&mathjax{x = (\cdots b_2 b_1 b_0. c_1)_{(p)}};で、&mathjax{v = 2};の時は&mathjax{x = (\cdots b_2 b_1 b_0. c_1 c_2)_{(p)}};で、&mathjax{v = 3};の時は&mathjax{x = (\cdots b_2 b_1 b_0. c_1 c_2 c_3)_{(p)}};で、&mathjax{v = 4};の時は&mathjax{x = (\cdots b_2 b_1 b_0. c_1 c_2 c_3 c_4)_{(p)}};という表記を表しています。
*6 上の方法ではそもそも前提として&mathjax{x \times \alpha = 1^{(p)}};を満たすような&mathjax{p};進数&mathjax{x};の存在を仮定してしまっているので文字通りに解釈すると循環論法になってしまいますが、&mathjax{b_0, b_1, b_2, \ldots};を構成するアルゴリズムそのものは&mathjax{\alpha};のみに依存して与えられているので、&mathjax{x};の存在を仮定せずに記述することが出来ます。本来ならば&mathjax{x};が高々1つしか存在しないことの証明の前にそのアルゴリズムを書いておけば何も問題がないのでそうすべきなのですが、そうすると読者にとって「理由は分からないけど謎のアルゴリズムが現れた」という体裁に見えてしまい読みにくくなってしまうので、今回は抽象的な議論に慣れていない人にも読みやすくなるように配慮をしてアルゴリズムを後回しにしました。