中国剰余定理

内容

$n_1,\dots,n_k$ が対ごとに互いに素な正の整数であるとき、任意の整数 $a_1,\dots,a_k$ に対して、合同式の系 $x\equiv a_i \pmod{n_i}$($i=1,\dots,k$)は解 $x$ を持ち、それは $N=n_1n_2\cdots n_k$ を法として一意である。

なぜ正しいのか?

対ごとに互いに素な法は独立した情報を運ぶため、それぞれについて余りを指定すると、それらの積を法として一意な剰余が定まる ― 互いに素な周期で動く複数の時計から一つの数を読み取るようなものである。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。