暗号理論第2回―数論基礎 中国人の剰余定理から合同方程式の単純な解法まで

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

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)より確認

では次回はミンコフスキー不等式とシュワルツ不等式について扱う。

marikoi

ここの主筆・共同管理人。ぶっちゃけ狂人。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA