電波系美少女バーチャルインターネッツアイドル文野純がメッタメタ遊んでメッタメタ考えて勉強するゲヲログ姉妹サイト...

メニュー⇒ ソフトウェア 思想評論 数学 書評 歴史 統計 雑感 馬鹿企画

中国人の剰余定理から合同方程式の単純な解法まで

中国人の剰余定理から合同方程式の単純な解法まで

「中国人の剰余定理」ではこんな例がある。

x≡2 (mod3)
x≡3 (mod5)
を満たすxを求めよ。

このとき3*5を法とするただひとつのxの値を求められる。

3X+5Y=1を満たすX・Yはユークリッド互除法によれば…(勘を頼りに)
X=2,Y=-1
よって、求めるx=2*5*(-1)+3*3*2=8 これは3*5=15を法としてただ一つである。

すなわちmod15としてその範囲(15未満)にてただ一つである。だがちょっと待ってほしい、さらに深めていこう。ではこれをさらに深く追い求めて、変数を活用して、合同連立式として解を得ることにしてみると…

x≡2 (mod3)のとき、x=3y+2と表せる。・・・(1)
変形してx≡3(y-1) (mod5)
x=5z+3 従って x≡3 (mod5)・・・これは条件を満たしている。さらに変形して…
x=3(y-1)+5従ってy=5z+2・・・(1)
(1)に(2)を代入して…
x=3(5z+2)+2=15z+8
x≡8 (mod15)

ついでに言っておくとこいつもこう整理できる。

x≡2 (mod3)のとき、x=3n+2 and n∈Z (nは整数の集合Zに属する)

https://www.wolframalpha.com/input/?i=solve+x%E2%89%A12+(mod3)より確認

シェアする

  • このエントリーをはてなブックマークに追加

フォローする