あれこれ。: 5月 2014

備忘録。

数学のことはよくわからないのでところどころ端折っている。あと結局間違ってる可能性も・・・。

とりあえず、こんなことできる方法がある！程度のメモ書き。

たとえば $23^{95}$ という数を323で割ったあまりを求めたいとき。

暗算でも手計算でも電卓でもパソコンでも何でもいいけど使って求められるだろうか？

僕は初見ではどれも不可能だった。

暗算なんて $2^{12}$ くらいまでしかできないｗ手計算したけど $23^{4}$ で紙を破いた。電卓は簿記で使ってものを用いたが桁が余裕で足りない。パソコンはC言語で素直に計算させたら桁が足りなかった。各桁用の配列を作ればたぶん簡単だと思うけど。とりあえず

・・・どうしたものか。

離散数学の授業でこんな問題を解決してくれる方法を習ったのを思い出した。

それが中国人の剰余定理。

特にちゃんと理解はしてないけれど過程をざっくりメモっとく。

「中国人の剰余定理」

$23^{95}\mod\323$ （23の95乗を323で割った余り）

→323を素因数分解する。

17, 19を約数に持つ(この2つの数は素数で、323は1とこの2つの素数しか約数に持たない)、より

$23^{95}\mod\323$ は

→ $23^{95}\mod\19$

→ $23^{95}\mod\17$

の2つに分解できる。

ここでラグランジュの定理を用いる。

ラグランジュの定理はここでは $23^{n}$ (nは0を含む自然数)を19, 17で割った余り=1となる形を見つけるってこと。

ということで

$23^{9}\equiv 1\mod\19$ 　（23^9を19で割った余りは1）

$23^{17}\equiv 1\mod\17$ 　（23^17を17で割った余りは1）

(なんで「≡」合同記号なのかは分からない^^;)

で、 $23^{95}$ をこの2つを使って表現していく。

mod 19のとき。

$23^{95}\equiv \left ( 23^{9} \right )^{10}\cdot 23^{5}\mod\19\\$

※ $23^{9}\mod\19$ は１だから $\left ( 23^{9} \right )^{10}$ は $1^{10}$ と同じ。

$23^{95}\equiv \left ( 23^{9} \right )^{10}\cdot 23^{5}\mod\19\\$

$23^{95}\equiv1\cdot 23^{5}\mod\19$

$23^{95}\equiv23^{5}\mod\19\\$

（補足）--------

$23^{1}&\equiv& 4\mod\19$

$23^{2}&\equiv& 4^{2}\equiv 16\mod\19$

$23^{3}&\equiv& 4^{3}\equiv 64\mod\19$ さらに19で割ると余りは $&\equiv 7\mod\19$

--------------

$23^{95}&\equiv& 23^{3}\cdot23^{2}\mod\19$

$23^{95}&\equiv& 7\cdot16\mod\19$

$23^{95}&\equiv& 112\mod\19$

112をさらに19で割る→余り17

$23^{95}&\equiv& 17\mod\19$

同様にmod 17でもやる。

$23^{95}\equiv \left ( 23^{17} \right )^{5}\cdot 23^{10}\mod\17$

（補足）--------

$23^{2}&\equiv& 2\mod\17$

--------------

$23^{95}\equiv 1^{5}\cdot \left ( 23^{2} \right )^{4}\cdot 23^{2}\mod\17$

$23^{95}\equiv 1\cdot 2^{4}\cdot 2\mod\17$

$23^{95}\equiv 32\mod\17$

※32はまだ17で割れるから、割った余りは15

$23^{95}\equiv 15\mod\17$

ここで

$X\equiv \left \{ \begin{matrix} 17\mod\19\\ 15\mod\17 \end{matrix}$

を満たすXが存在する。

a = 17, b = 15 とおく。

19と17の最小公約数は1

ここで

$19x_{1}+17x_{2}= 1$ 　（後でS_1とS_2のところで使う）

とする。

拡張ユークッリッド互除法を使う。

$\binom{{\color{Red}19 }}{17}= \begin{pmatrix} {\color{Red} 1} &1 \\ 1& 0 \end{pmatrix}\begin{pmatrix} 17\\ {\color{Red} 2} \end{pmatrix}$ 　　　　・・・19÷17=1 余り2

$\binom{{\color{Red}17 }}{2}= \begin{pmatrix} {\color{Red} 8} &1 \\ 1& 0 \end{pmatrix}\begin{pmatrix} 2\\ {\color{Red} 1} \end{pmatrix}$ ・・・17÷2=8 余り1

$\binom{{\color{Red}2 }}{1}= \begin{pmatrix} {\color{Red} 2} &1 \\ 1& 0 \end{pmatrix}\begin{pmatrix} 1\\ {\color{Red} 0} \end{pmatrix}$ 　　　　　・・・2÷1=2 余り0

よって

$\begin{pmatrix} 19\\ 17 \end{pmatrix}= \begin{pmatrix} 1 &1 \\ 1 &0 \end{pmatrix} \begin{pmatrix} 8 &1 \\ 1 &0 \end{pmatrix} \begin{pmatrix} 2 &1 \\ 1 &0 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix}$

$= \begin{pmatrix} 9 &1 \\ 8 &0 \end{pmatrix} \begin{pmatrix} 2 &1 \\ 1 &0 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix}$

$= \begin{pmatrix} 19 &9 \\ 17 &8 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix}$

$\begin{pmatrix} 1\\ 0 \end{pmatrix} = \begin{pmatrix} 19 &9 \\ 17 &8 \end{pmatrix}^{-1}\begin{pmatrix} 19\\ 17 \end{pmatrix}$

$\begin{pmatrix} 19 &9 \\ 17 &8 \end{pmatrix}^{-1}=\frac{1}{19\cdot 8-9\cdot 17}\begin{pmatrix} 8&-9 \\ -17&19 \end{pmatrix}=\begin{pmatrix} {\color{Red} -8} &{\color{Blue} 9} \\ 17&-19 \end{pmatrix}$

よって

$x_{1}=-8, \,x_{2}=9$

ここでS_1とS_2を以下のように設定する。

$S_{1}=19x_{1}=1-17x_{2}=-152$

（↑　 $x_{1}=-8, \,x_{2}=9$ 　を代入した。）

$S_{2}=17x_{2}=1-19x_{1}=153$

$X=aS_{2}+bS_{1}$

とするので各値を代入すると

$=17\cdot 153+15\cdot \left ( -152 \right )$
$=321\mod\323$

つまり

$23^{95}\mod\323$ 　・・・23の95乗を323で割った余りは

「321」

2014年5月17日土曜日

中国人の剰余定理

あれこれ。