3

中国式剰余定理を理解する(第1回 高校数学)

425
0
$$$$

はじめに

中国式剰余定理については、名前はよく聞くが正直よくわかっていないという印象であった。そのため,自分の理解のために中国式剰余定理についてまとめてみることを考えた。
当初は1つの記事で高校数学における中国式剰余定理と,一般の中国式剰余定理およびその関係について紹介しようと考えていたが,書き始めるといろいろとボリュームが増えてきたため記事を分割することとした。目標は全4回である。

  1. 高校数学における中国式剰余定理(本記事)
  • 群論および環論の基礎
  • 整数環における中国式剰余定理
  • 一般の環における中国式剰余定理

2020/12/07 追記
とりあえず第4回まで終えた。 第2回 第3回 の記事は群論と環論の定義や命題等の紹介なのでめんどくさい方は 第4回 までジャンプしてほしい。

高校数学における中国式剰余定理

7で割ると1余り,5で割ると2余る整数をすべて求めよ。

この問題は以下の連立合同式の解を求めることと同じである。
$ \begin{eqnarray} \left\{ \begin{array}{l} x \equiv 1 \pmod 7 \\ x \equiv 2 \pmod 5 \end{array} \right. \end{eqnarray}$
$1$式を満たす$x$$x = 7y + 1$の形でかけるものだけである。
これを第$2$式に代入すると$7y+1 \equiv 2$ ($\mod 5$)つまり,$7y \equiv 1$($\mod 5$)である。これを満たす整数$y$は,$y = 5k + 3$($k$は任意の整数)である。
従って,求めるものは$x = 35k + 22$($k$は任意の整数)となる。

中国式剰余定理(高校数学)

$m,n$を互いに素な整数,$a,b$を任意の整数とする。このとき,次を満たす整数$x$$0 \leq x < mn$にただ1つ存在する。
$ \begin{eqnarray} \left\{ \begin{array}{l} x \equiv a \pmod m \\ x \equiv b \pmod n \end{array} \right. \end{eqnarray}$

$a$,$c$,$m$を整数で$m>$ 1,$g =gcd(a,m)$$g | c$とする。このとき,$ax \equiv c \pmod m$はちょうど$g$個の互いに合同でない解をもつ。

補題2

$ax \equiv c \pmod m $の解を見つけるには,$ax-c = my$となる整数$y$を見つければよい。つまり,
$ax \equiv c \pmod m$ が解をもつ $\Leftrightarrow ax-my=c$が解をもつ
ということである。いま,$g = \gcd (a,m)$であるから,$au + mv = g$は常に解をもつ。さらに,ユークリッドの互除法から解$u = u_0$$v = v_0$が見つかる。$g | c$だから,両辺に整数$ c/g$ をかけて,$a\frac{cu_0}{g} +m\frac{cv_0}{g} = c$を得る。これは$ x_0 \equiv \frac{cu_0}{g} \pmod m $は合同式$ax \equiv c \pmod m$の解であることを意味している。
次に$x_0$から$g$個の合同でない解を作る。
$x_1$$x_0$とは異なる解とする。このとき,$ax_1 \equiv ax_0 \pmod m$となるので$m$$ax_1 - ax_0$を割り切る。つまり,$\frac{m}{g}$$\frac{a(x_1-x_0)}{g}$を割り切る。また,$\gcd(a,m)=g$なので$m/g$$a/g$は互いに素。したがって,$m/g$$x_1-x_0$を割り切る。つまり,ある整数$k$が存在して,$x_1 = x_0 + k\cdot \frac{m}{g}$と表せる。
しかし,どの2つの解も$m$の倍数の違いに関しては同一の解とみなすので,$k=0,1,\cdots,g-1$$g$個の異なる解を得る。

定理1

問題1と同様の手法により証明できる。
第1式を満たす$x$$y$を任意の整数として,$x = my + a$の形にかけるもののみ。これを第2式に代入すると$my \equiv b-a \pmod n$となる。このとき$m,n$は互いに素であるから,これを満たす整数$y_1$$0 \leq y_1 < n$にただ1つ存在する(補題2)。このとき$x_1 = my_1 + a$は元の合同式の解となる。$x_1$の一意性は$y_1$の一意性から従う。
最後に,この$x_1$$0 \leq x_1 < mn$を満たすことを示す。$0 \leq y_1 \leq n-1$だから,$0 \leq mx_1 \leq mn-m + a$である。ここで,$a$$m$で割ったときのあまりなので$a < m$であるから$mm-m+a < mn$となり,$0 \leq x_1 < mn$が成り立つ。

なお,定理1を$n$本の互いに素でない連立合同式に拡張することもできるが,本記事では割愛する(気が向いたら追記します)。

参考文献

ジョセフ・H・シルヴァーマン:はじめての数論 原著第3版 発見と証明の大航海―ピタゴラスの定理から楕円曲線まで(訳,鈴木 治郎)

投稿日:20201130

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

とも
とも
17
9458
広島県の高校で数学の教員をやっていたはずなのに,気づけば違う仕事をしております。高校数学と大学で学ぶ数学の橋渡しのようなことができればいいなと思っています。記事に誤り等あれば教えてください。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中