0でないp進数の逆数

まずは\( v \)が少なくとも１つは存在することを示す。筆算を用いた\( 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 \)となる。

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

となる。帰納法の仮定から\( 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 \)がただ１つ存在することを示す。そのためにまず、そのような\( x \)が存在するならばただ１つであることを示す。

\( 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 \)がただ１つ存在する。ここで、フェルマーの小定理により\( 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 \)がただ１つ存在する。\( 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 \)は、存在すればただ１つである。

また、\( 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 \)はただ１つしか存在しない。