拡張ユークリッド互除法
ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。 ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。 例えば，GCD(13,5) を計算するのに， 13=2*5+3 5=1*3+2 3=1*2+1 2=2*1 を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると， 13-2*5=3 5-1*3=2 3-1*2=1 が得られます。ここで，３行
中国の剰余定理
m1，m2 を互いに素な正整数（即ち最大公約数が１）とする。a1，a2 を整数する。 このとき， x ≡a1 (mod m1) x ≡a2 (mod m2) を満たす整数 x が m1m2 を法にして唯ひとつ存在する。 この定理が中国の剰余定理と言われるのは，２世紀頃の中国の算術書「孫子算経」にこの性質の記述があることに由来します。そのことからまた孫子の定理と言われることもあります。 今の場合は２つの連立合同式ですが，全く同様にして，３個以上の連立合同式についての定理が得られます。この場合も中国の剰余定理と呼ばれます。 具体例挙げます。 （中国の剰余定理の証明） この定理の証明はいくつもありますが，ここでは実際の解を計算する法を与える証明を挙げます。 （一意性）x1，x2 共に解であったとすると， x1 ≡ a1 ≡x2 (mod m1) x1 ≡ a
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
