[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→
Copyright (C) virtual_high_school, 2022
§1. 商と余りのサイクル
§2. 原始根と回転盤双六
§3. 余り→商変換
§4. 循環節の長さと種類数
§5. g進小数展開
§∞. 文献
$p$ を素数とするとき、真分数 $\frac{a}{p} (0< a <p)$ を小数に直す(10進小数展開という)ことを考えてみよう。ただし、$p$ は 2, 5 ではないとする。(この場合は有限小数になってしまい、面白くない。) このとき、分子を分母で割りきることができないから無限小数になる。
【問題1-1】 $A=\frac{8}{73}$ を小数に直すには、分子を分母で割ればよい。筆算で割り算したときに出てくる、(1) 余りの数列、(2) 商の数列
(それぞれ繰り返しになるから、「余りのサイクル」、「商のサイクル」と呼ぼう)を求めよ。---
(解)(1) 余りの数列について
上図の赤丸で囲った数が余りであるから、余りのサイクルは
$7 \rightarrow 70 \rightarrow 43 \rightarrow 65 \rightarrow 66 \rightarrow 3 \rightarrow 30 \rightarrow 8 $ (答)
である。筆算が面倒なら、Excelワ−クシート "syosu.xlsx" (←ここをクリックすると open または save ができます。)で計算してもよい。73 で割った余りは 1〜72の72通り(有限個)だから、割っていくうちにやがて以前に出てきた余りと同じ余りが出てきて、そこから後は繰り返しになる。だから、サイクル(円環)になる(厳密に論じると問題1-2の通り)。しかもそのサイクルの長さ(周期)はたかだか $p-1=72$ である。
ところで、この数列って何だろう。初項(第1項)が $7$ で末項は $8$ である。筆算を見ると一瞬、初項は $8$ ではないかとも思えるが、初回の割り算は
$8 \div 73=0 \cdots 8 \Leftrightarrow 8=73 \times 0 +8$
なのではなく、小数第1位の $1$ に対応する、
$80 \div 73=1 \cdots 7 \Leftrightarrow 80=73 \times 1 +7$
が 1回目の割り算なのである。一瞬初項のように見えた $8$ は第0項であり、初項の1個手前であり、かつ末項に等しい。
項数は 8 項であると言ってもよいし、項数は ∞ 項で周期が 8 であると言ってもよい。
さて、この余りの数列の規則だが、初項の $7$ の次の項は 10倍して 73で割った余り=70 だから、公比が 10 の等比数列だと分かる。その次の項(第3項)は
70 の10 倍の 700 を73 で割った余り 43 である。73 で割った余りと、割る前の 700 を同一視して、
$700=43 (mod.73)$
と書くことにし、「700と43はモード 73で等しい(73を法として合同)」と読むことにしよう。($=$ でなく $\equiv$ を使う流儀もあるが、混乱しなければどちらでもよい。)
この $mod$ の考えを取り入れると、余りのサイクルは
$7 \rightarrow 70 \rightarrow 700=43 \rightarrow 430=65 \rightarrow 650=66 \rightarrow 660=3 \rightarrow 30 \rightarrow 300=8 ( \rightarrow 80=7 \rightarrow \cdots) $
と、見事に初項 7, 公比 10 の($mod.73$ の)等比数列である。
(2) 商のサイクルについて
筆算の結果を見れば分かる通り、商のサイクルは
$1 \rightarrow 0 \rightarrow 9 \rightarrow 5 \rightarrow 8 \rightarrow 9 \rightarrow 0 \rightarrow 4 $ (答)
である。余りのサイクルに対応して出てくるから、サイクルの長さ(周期)は余りのそれに等しく、8 項である。この答に基づいて、
$A=\frac{8}{73}=0. \dot{1} 095890 \dot{4}$
と書き、循環節の長さは 8 であると称する。これで循環節の長さはたかだか (分母)$-1$ であることも分かった。
【問題1-2】 上の余りのサイクルがほんとに円環状(サイクル)になることを示せ。---
(証明) 一見当たり前のような気がして、上では言及しなかった。もし下図のような鉄道の引込線のようなルートがあると、c から後はサイクルだが、全体を見ると円環にはなっていないことがありうることに気を配ろう。
示すべきはこのような引込線がありえないことだ。もし上図のようになれば
$10 b=10 h (=c)$
だが、10 の逆元 $x$ を両辺に掛ければ
$x 10 b= x 10 h \Rightarrow 1 b=1 h \Rightarrow b=h$
となって、矛盾する。問題は 10 の逆元が存在するのはなぜかという点に絞られれる。実際、$mod$ の $p$ は 2, 5 以外の素数であったから、10 と $p$ の最大公約数は 1 になる。したがって「表現定理」(下の不定方程式に整数解が存在する)により
$10 x+ p y =1$
となる整数 $x,y$ が存在する。よって、
$10 x=1-p y=1 (mod.p)$
で確かに逆元 $x$ が存在する。■
【問題1-3】 前問の余りのサイクル(等比数列)の一般項 $r_{n}$ を求めよ。---
(答) $r_{n}=7 \times 10^{n-1} (mod.73)$
上の一般項がもう少し簡単な式にならないかを考えてみよう。7 の方も $a^m$ の形に変形できれば、うまくすれば $10^{n-1}$ と掛けて指数法則
$a^x \times a^y=a^{x+y}$ が使えるかもしれない。
そのためには、1 〜 72 (73で割って割り切れないときに出てくる余りはこの72個の数のどれかだ)のすべてが $a^x$ の形に表すことができればラッキーだ。そのときの底 $a$ のことを原始根と言う。
オイラーは、$mod.p$ ($p$ は素数)の数体系には必ず原始根が存在することに気づいていたが、それを証明することはできなかった。それを初めて証明したのがガウスである。(原始根の存在証明については文献 [1] 参照)
【問題2-1】 $mod.73$ の原始根を 1つ求めよ。---
(解) 原始根を $\zeta$ とする。$mod.73$ の 0 以外の 72個の数が $\zeta^k$, すなわち
$\zeta, \zeta^2, \zeta^3, \cdots, \zeta^{72}$ (*)
で表される訳だ。当然この中に 1 があるが、それは末項で $\zeta^{72}=1$ が成り立つ。なぜなら、もし 72 より手前で、例えば 62 乗で 1 になったら、$\zeta^{62}=1$ の両辺に $\zeta$ を掛けて
$\zeta^{63}=\zeta$
となり、(*) の中に同じ数があることになり、72 個の数すべてを表すことができなくなるからだ。
結局、72乗して初めて 1 になる数が原始根である。
さて、10 がもし原始根なら、循環節の長さが最長($p-1$) の循環小数になって楽しいのだが、
$10^2=100=73 \times 1+27=27=3^3 $ $(mod.73)$,
$10^4=3^6=729=73 \times 10-1=-1$,
$10^8=(-1)^2=1$
となってしまう。10 は 8乗で 1になり、原始根ではない。この状況を「10 の位数は 8 である」と言い、
$|<10>|=8$
と書く。(だから、$mod.p$ の原始根の位数は $p-1$ ということになる。)
上に出てきた等式の1番目から、3 は 10 の 2/3 乗と分かるから、3 をなんとか攻略しよう。
$3=73 \times 6+3=441=21^2$,
$1=10^8=(10^2)^4=(3^3)^4=3^{12}=(21^2)^{12}=21^{24}$
21 は 24乗で 1 になる数(位数が 24の元) だ。上で導いた等式をうまく利用すれば
$21=-73 \times 2+21 =-125=-5^3$,
$1=21^{24}=(-5^3)^{24}=5^{72}$
これで 5 の位数が 72, すなわち原始根であることが分かった。
(答) 例えば、5 が原始根である。(実は、原始根は他にもある。)
【問題2-2】 $mod.73$ で 1〜72 の数を 5 の累乗の形に表せ。---
(解) $5,5^2,5^3, \cdots ,5^{72}$ を計算すればよい。手計算でももちろんできるが、Excel を使おう。Excelワ−クシート "genshi.xlsx" をクリック( open または save ができます。)
実はこのワークシートを使えば、先ほどの原始根探し(問題2-1)も試行錯誤的に(1〜72の数をいろいろ試して)行うことができたのであった。
この Excel のワークシートで $5, 5^2,5^3, \cdots , 5^{72}$ を計算すれば、順に
$5, 25 , 52, 41, 59, \cdots,66,38,44,1$
のようになることが分かる。途中を省略せずに全部書けば、下表である。問題1-1 に出てきた余りの数は黄色で塗っておいた。
【問題2-3】 改めて、余りのサイクル(上表の黄色)の一般項 $r_{n}$ を求めよ。---
(解) 問題1-3 に出てきた余りのサイクル(上表の黄色)を再録すると
$7 \rightarrow 70 \rightarrow 43 \rightarrow 65 \rightarrow 66 \rightarrow 3 \rightarrow 30 \rightarrow 8 $
で、その一般項は $r_{n}=7 \times 10^{n-1} (mod.73)$ であったが、上表を見ると
$7=5^{33}, 10=5^9$
であることが分かるから、
$r_{n}=5^{33} \times (5^9)^{n-1} =5^{33+9(n-1)}$ ……(答)
$r_{n}$ の底 5 に対する指数(index)を $i(n)$ とすれば、それは等差数列で
$i(n)={33+9(n-1)}$
具体的には
$i(1)=33,i(2)=42,i(3)=51,i(4)=60,i(5)=69,i(6)=78=6,i(7)=15,i(8)=24 $
上式で $78=6$ としたが、5 は 72乗で 1になり、よって例えば 5 の 73 乗と 1 乗は同じものになる。だから、指数は $mod.72$
($p$ ではなく $p-1$ であることに注意)で計算すればよい訳だ。
$i(n)$ は公差が 9 の(円環状の)等差数列で、72 個の数を 9 個ごとに飛び石のように飛んで回るのだから、項数(周期)は $72 \div
9=8$ である。
余りのサイクルは、その名の通り円環状になっているので、下図のように左回りに排列して、この図を回転盤双六と名付けよう。
そもそも双六とは、サイコロを振って出た目だけ進んでいくゲームで、スタート地点を「振り出し」、ゴールを「上がり」と呼ぶ。ここでの双六は、10 倍ずつ進む(今の場合は
9 コマずつ進む)のがルールだ。
$A=\frac{8}{73}$ の場合は振り出し=上がり(第0項)が 8 で、初項=第1項が $80=7$ である。
回転盤双六(上図)を見ながら解く問題に挑戦してみよう。
【問題2-4】 $B=\frac{43}{73}$ を小数にするために割り算をしたときに出てくる余りのサイクルを求めよ。---
(解) 振り出しの $43$ の次から始めて、9 コマずつ進めばよい。よって、余りのサイクルは
$65 \rightarrow 66 \rightarrow 3 \rightarrow 30 \rightarrow 8 \rightarrow 7 \rightarrow 70 \rightarrow 43 $ (答)
上の答を 問題2-3 で扱った余りのサイクルと比較すると、シフトしている(ズレてる)だけだ。でもサイクル=円環には初めも終わりもない。だから、これら 2つの余りのサイクルは本質的に同じ種類のものと見てよい。
【問題2-5】 $C=\frac{1}{73}$ の余りのサイクルを求めよ。---
(解) 1 を振り出しに 9 コマずつ進む。よって、余りのサイクルは
$10 \rightarrow 27 \rightarrow 51 \rightarrow 72 \rightarrow 63 \rightarrow 46 \rightarrow 22 \rightarrow 1$ (答)
(図には色を塗っていないので、見間違えないようによく見てください。) この答に出てきた余りのサイクルは、問題2-3 に出てきたそれと全く違うので、異なる種類のサイクルだ。よく見れば 1つとして同じ数が出てこない。(そりゃ、そうだ。もし同じ数が 1つでもあればそこから後は同じ数列になり、それは円環になっているから、結局サイクルとして同一ということになる。)