Root One

数学中心のブログです。

高次合同式の10進数的解法

今回のテーマは、高次合同式

f:id:likethenovel:20190321171748j:plain

の解を求めることです。(今回は \mathbb{Z}_{10} の世界の関数の連続性という概念を使用するので話が難しくなります。)

実数の世界の話

実数 \mathbb{R} の世界で

 \displaystyle x^7=3

を解く必要があれば

 \displaystyle x = 3^{1/7}

として終了です。もし近似値が欲しければ、計算機にお任せしましょうという感じでしょうか。具体的には、テイラー展開

 \displaystyle 3^x = 1 + (\log 3) x + (\log 3)^2 \frac{x^2}{2} + (\log 3)^3 \frac{x^3}{3!} + \cdots 

を用いて、 \displaystyle \frac{1}{7} \fallingdotseq 0.1428 を代入して近似解を得ることができます。

(もちろん \log 3 の値も近似計算しなければならないですが。)

合同式の世界の話

では、合同式

 \displaystyle x^7 \equiv 3 \mod 10

 を解く場合はどうでしょうか。同じようにして

 \displaystyle x \equiv 3^{1/7} \mod 10

として終了するでしょうか。おそらくは、しないでしょう。そもそも解の候補は10通りしかないのですから、はっきり求めたいところです。しかし、

 \displaystyle x^7 \equiv 3 \mod 10000

となるとどうでしょうか。今度は解の候補は10000通りあります。こうなると

 \displaystyle x \equiv 3^{1/7} \mod 10000

として終了してしまいたくもなります。実数の場合であれば、3^{1/7}の計算方法は明確であったため、このような変形が意味を持ちましたが、合同式の場合ではどうでしょうか。

実数の場合であれば、近似解を得るとき

 \displaystyle \frac{1}{7} \fallingdotseq 0.1428

という近似の利用が可能でした。つまり、

 \displaystyle 3^{1/7} = 3^{0.1428\cdots}

のような変形を何気なくし、また適当に有限できって

 \displaystyle 3^{1/7} \fallingdotseq 3^{0.1428 }

を期待したわけです。(これは指数関数 3^x連続性を仮定していることになります.)

同じことが合同式でもできないかと考えます。

ただし 1/7の近似値として、実数の世界の近似値ではなくて、

\mathbb{Z}_{10} の世界の近似値を利用します。

\mathbb{Z}_{10} の世界では

 \displaystyle \frac{1}{7}= \cdots 2857143

だったので、

likethenovel.hatenablog.com

 \displaystyle 3^{1/7} = 3^{\cdots 2857143}

と変形します。mod 10000 であれば 4 桁しか必要ないので

 \displaystyle \frac{1}{7} \equiv 7143 \mod 10000

を利用して

 \displaystyle 3^{1/7} \equiv 3^{7143} \mod 10000

と「とりあえず」変形できたとしましょう。実際に計算すると(すごく大変ですが)

 \displaystyle 3^{7143} \equiv 1627 \mod 10000

が得られます。これは本当に

 \displaystyle x^7 \equiv 3 \mod 1000

の解になっているでしょうか。この計算も大変ですが

 \displaystyle 1627 ^7 \equiv 3 \mod 10000

を確認することができます。したがって、議論の正当性はさておき、結果が正しいことはわかりました。

難しい話になりますが、実はこの議論は、10進指数関数の連続性を示唆した結果になっています。

つまり \mathbb{Z}_{10} の世界では

 \displaystyle x  \fallingdotseq y

であれば

 \displaystyle 3^x \fallingdotseq  3^y

ということ、もっと正確に述べると、任意に指定した自然数nに対して

ある程度大きい m を用意して

 \displaystyle x \equiv y \mod 10^m

とすれば、

 \displaystyle 3^x \equiv 3^y \mod 10^n

が成立するようにできることを利用しています。

じつは、n\geq 2 であれば m=n と取れます。

つまり、n\geq 2 とすると、

 \displaystyle x \equiv y \mod 10^n

のとき

 \displaystyle 3^x \equiv 3^y \mod 10^n

が成立することが言えます。

議論の正当性の確認

主張1n\geq 2 とすると、

 \displaystyle x \equiv y \mod 10^n

のとき

 \displaystyle 3^x \equiv 3^y \mod 10^n

が成立する。

 

この主張1を仮定して x^7 \equiv 3 \mod 10^4 を解いた議論を

正当化してみます。

まず、

 \displaystyle \frac{1}{7} \equiv 7143 \mod 10000

の意味ですが、これは

 \displaystyle 7x \equiv 1 \mod 10000

の解が

 \displaystyle x \equiv 7143 \mod 10000

であるという意味です。

つまり、

 \displaystyle 7\times 7143 \equiv 1 \mod 10000

が成立するということです。これは直接的にも簡単に確認できます。

これをふまえて、

 \displaystyle a = 3^{7143}

とおき、

 \displaystyle a^7 \equiv 3 \mod 10000

を示します。左辺は

 \displaystyle \tag{eq.1} a^7 = 3^{7143\times 7} = 3^{50001}

となりますが、

 \displaystyle 50001 \equiv 1 \mod 10000

なので、「主張1のn=4のケース」より

 \displaystyle \tag{eq.2} 3^{50001} \equiv 3^1 \mod 10000

が成立します。

よって(eq.1)と(eq.2)より

 \displaystyle a^7 \equiv 3 \mod 10000

が得られました。これは明らかに

 \displaystyle x^7 \equiv 3 \mod 10000

の解が x=a となっていることを示します。

まとめ

 \!\!\! \mod 10^n合同式の世界は、\mathbb{Z}_{10} の距離感で考えると、指数関数の連続性という概念が、ある種の合同式の解法に利用できるということが分かりました。主張1の証明はしていませんが、これはオイラーの定理を精密化したものから証明できます。