読者です 読者をやめる 読者になる 読者になる

tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

循環小数(4): 平方剰余の相互法則

循環小数問題
1/12377の小数点以下6193桁目は何か?(問題編) - tsujimotterのノートブック
1/12377の小数点以下6193桁目は何か?(解答編) - tsujimotterのノートブック


解説編
第1回:循環小数(1): フェルマーの小定理 - tsujimotterのノートブック
第2回:循環小数(2): Midyの定理(前編) - tsujimotterのノートブック
第3回:循環小数(3): Midyの定理(後編) - tsujimotterのノートブック
第4回:循環小数(4): 平方剰余の相互法則 - tsujimotterのノートブック


(※ p は以下、断りなく 2, 5 以外の素数として扱います。)


本記事は、循環小数問題の解説編として書いています。


今回が、私がもっとも書きたかったことです。この記事のためだけに、今まで (1)から(3)まで書いてきました。


第4回のテーマは

「循環小数 1/p の 循環節の長さが
(p-1)/2 の約数となる条件」

です。これさえわかれば、循環小数の後半の桁がわかることは前回示しました。

その条件とはいったい何なのでしょうか。


先に言ってしまうと、それは次の条件です。

《定理4》
 1/p の循環節の長さが  (p-1)/2 の約数となる必要十分条件は、
 p 40 で割った余りが  1, 3, 9, 13, 27, 31, 37, 39 のいずれかであることである。

私が最初にこの条件を見たとき、

「なぜ 40 が関係があるのか」

と疑問に思いました。みなさんもそうでしょう。


でも安心してください。ちゃんと計算によって 40 という数字が出てくるのです。

しかもその計算には、初等整数論で最も美しいとされる定理

「平方剰余の相互法則」

が登場します。

期待に胸を膨らませて、《定理4》の証明に進んでいきましょう。





平方剰余との関係

第1回の記事では、次の条件が得られました。

《循環小数が  (p-1) 桁で循環する条件》

 \displaystyle 10^{(p-1)}\equiv 1 \pmod p


これとまったく同様に、《循環節の長さが  (p-1)/2 の約数となる条件》を考えると、次のようになるでしょう。

《循環節の長さが  (p-1)/2 の約数となる条件》

 \displaystyle 10^{(p-1)/2}\equiv 1 \pmod p


この左辺に着目します。
すると次の式とよく似ていることがわかります。

《オイラーの基準》

 \displaystyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \pmod p
ただし、 \displaystyle \left(\frac{a}{p}\right) は平方剰余を表すルジャンドル記号。

 a 10 で置き換えれば、まったく同一ですね。


したがって、《循環節の長さが  (p-1)/2 の約数となる条件》は、平方剰余を使って次のように置き換えることができます。

《循環節の長さが  (p-1)/2 の約数となる条件(の書き換え)》

 1/p の循環節の長さが  (p-1)/2 の約数となる必要十分条件は


 \displaystyle \left(\frac{10}{p}\right) = 1
が成り立つことである。


これで最初の問題が「平方剰余」と見事結びつきました!


あとはこの左辺を計算し、平方剰余になる  p の条件を考えればいいわけです。


ここで 《平方剰余の相互法則》 の登場です!

平方剰余の相互法則

証明はしませんが、今回使う 《平方剰余の相互法則》 をまとめます。

まずは、《平方剰余の定義》から。

《平方剰余の定義》

 a,  p を互いに素な整数とするとき、


 \displaystyle x^2\equiv a \pmod p
が解をもつならば 「 a \pmod p で平方剰余である」という。
解を持たないならば、「 a \pmod p で平方非剰余である」という。

このことをルジャンドル記号を用いて次のように表す。

  •  a \pmod p で平方剰余である

 \displaystyle \left(\frac{a}{p}\right)=1

  •  a \pmod p で平方非剰余である

 \displaystyle \left(\frac{a}{p}\right)=-1

続いて今回のメインディッシュである 《平方剰余の相互法則》 です。

《平方剰余の相互法則》

 p,  q を相異なる奇素数とするとき

 \displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}

今回は使わないですが、重要な定理である 《第1補充則》 です。

《第1補充則》

 p を奇素数とするとき

 \displaystyle \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}

《第2補充則》 は後程つかいます。

《第2補充則》

 p を奇素数とするとき

 \displaystyle \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}

最後に 《平方剰余の積に関する法則》 です。

《平方剰余の積に関する法則》

 p を奇素数、 a,  b を互いに素な整数とするとき

 \displaystyle \left(\frac{ab}{p}\right) =  \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)

これだけあれば十分でしょう。

フル活用して計算していきます。

《平方剰余の相互法則》を使って展開

それでは、 \displaystyle \left(\frac{10}{p}\right) を展開していきましょう。

《平方剰余の積に関する法則》から、次式が得られます。

 \displaystyle \left(\frac{10}{p}\right) = \left(\frac{2}{p}\right)\left(\frac{5}{p}\right)


左辺が平方剰余となる条件は、右辺が平方剰余の積となっていることから、

 \displaystyle \left(\frac{2}{p}\right)=1\; かつ  \displaystyle \;\left(\frac{5}{p}\right)=1

または

 \displaystyle \left(\frac{2}{p}\right)=-1\; かつ  \displaystyle \;\left(\frac{5}{p}\right)=-1

であることがわかります。


《第2補充則》より

 \displaystyle \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}

から  \displaystyle \left(\frac{2}{p}\right) が平方剰余となる必要十分条件は、 p\equiv 1, 7 \pmod 8 であることがわかります。逆に、非剰余となる条件は、 p\equiv 3, 5 \pmod 8 です。


また  \displaystyle \left(\frac{5}{p}\right) については、《平方剰余の相互法則》より、

 \displaystyle \left(\frac{5}{p}\right)\left(\frac{p}{5}\right) = (-1)^{\frac{5-1}{2}\cdot \frac{p-1}{2}} = 1

から、

 \displaystyle \left(\frac{5}{p}\right) = \left(\frac{p}{5}\right)

が得られることを利用します。
この右辺が 1 になることは、定義に戻って考えると、

 \displaystyle x^2\equiv p \pmod 5

となるような  x が存在することと同値です。


 \pmod 5 ですべてのパターンをチェックすると、

 1^2\equiv 1 \pmod 5
 2^2\equiv 4 \pmod 5
 3^2\equiv 4 \pmod 5
 4^2\equiv 1 \pmod 5

より、平方剰余となる条件は  p\equiv 1, 4 \pmod 5 であることがわかります。逆に非剰余になる条件は  p\equiv 2, 3 \pmod 5 です。


したがって、以上より次の関係がいえます。

 \displaystyle \left(\frac{10}{p}\right)=1 であることの必要十分条件は、


 p\equiv 1, 7 \pmod 8\; かつ  \;p\equiv 1, 4 \pmod 5
または
 p\equiv 3, 5 \pmod 8\; かつ  \;p\equiv 2, 3 \pmod 5

あとは、連立合同式を解いていけばいいわけですが、もう数が多くないので  \pmod {40} で全列挙して考えましょう。



f:id:tsujimotter:20140404214421p:plain:w500
図の赤い四角が平方剰余、紫が平方非剰余をあらわしています。

たしかに、1, 3, 9, 13, 27, 31, 37, 39 のときだけ、平方剰余・非剰余が一致していることがわかります。


これでついに、念願の条件が得られました。

 \displaystyle \left(\frac{10}{p}\right)=1 であることの必要十分条件は、
 p 40 で割った余りが  1, 3, 9, 13, 27, 31, 37, 39 のいずれかであることである。


翻って、元の命題に戻ると、

《定理4(再掲)》
 1/p の循環節の長さが  (p-1)/2 の約数となる必要十分条件は、
 p 40 で割った余りが  1, 3, 9, 13, 27, 31, 37, 39 のいずれかであることである。

が証明されたことになります。

1/12377 の 6193 桁目を計算しよう

ここで、最初の問題に立ち戻って考えてみましょう。

問題は

 1/12377 の 小数点以下  6193 桁目の数」がどうなるか

ということでした。


 12377 40 で割った余りを考えて、

 12377 \equiv 17 \pmod {40}

より、

 \displaystyle \left(\frac{10}{p}\right)=1 であることの必要十分条件は、
 p 40 で割った余りが  1, 3, 9, 13, 27, 31, 37, 39 のいずれかであることである。

から、

 \displaystyle \left(\frac{10}{12377}\right) = -1
すなわち平方非剰余です。
したがって、 1/12377 の循環節の長さは、 (12377-1)/2 の約数になりません


ここで、

《定理3(第3回の記事より)》
 1/p の 循環節の長さを  e、小数点以下  \displaystyle k \left(\leq \frac{e}{2}\right) 桁目を  a_k とすると、


(中略)

2.  e (p-1)/2約数でないとき


 a_{(p-1)/2+k} = 9 - a_k

から  a_{6193} は、 a_{5} を使って次のように計算できます。

 a_{6193} = a_{(12377-1)/2 + 5} = 9 - a_5


一方  1/12377 の循環節の前半は、

 1/12377 = 0.0000807...

ですから  a_5 = 8 です。


よって  a_{6193} = 9-8 = 1 より求める解が得られました。

まとめ

ここまで、長いこと説明してきましたが、いかがだったでしょうか。
「たかが循環小数」と思っていた方も、意外な奥深さに驚いたのではないでしょうか。


結論を言うと、循環節に関する下記の条件は、

 1/p の循環節の長さが  (p-1)/2 の約数となる条件》

 \displaystyle 10^{(p-1)/2}\equiv 1 \pmod p

次のように、平方剰余の定義そのものと対応していたわけです。

 1/p の循環節の長さが  (p-1)/2 の約数となる条件(の言い換え)》

 \displaystyle \left(\frac{10}{p}\right) = 1

美しい対応関係ですね。


また、

 p 40 で割った余りが  1, 3, 9, 13, 27, 31, 37, 39 のいずれかであることである。

という意味不明だった条件も、平方剰余と結びついて理由を付けることができました。


 40 というよくわからない数字は、 \pmod 8 \pmod 5 の連立合同式からきていたのですね。

そしてその  \pmod 8 \pmod 5 は、小数の基数である  10 2\times 5 と因数分解できることから生まれた条件だったわけです。


以上を持って循環小数の長い長い解説編は終わりです。
ここまで読んでくださってありがとうございます。


一見すると整数論とまったく関係ないように思える 《循環小数》 を整数論の代表格である 《平方剰余の相互法則》 で解決するという流れは、なかなか味があってよいのではないかと思っています。


循環小数の奥深さ・面白さを垣間見て私が味わった感動を、これらの記事を通して少しでも感じてもらえたら幸いです。

参考文献

平方剰余の相互法則については例によって、次の本の第一章を参照するとよいかと思います。

初等整数論講義 第2版

初等整数論講義 第2版