Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

2018-12-22から1日間の記事一覧

中国剰余定理で2式の場合の解を求める

中国剰余定理とは、2式の場合を互いに素とするとき、 を満たす整数xがの範囲内にただ一つ存在するというものです。 xの求め方はこうです。 まずを満たす(p, q)のセットを一つ求めます。 以下のアルゴリズムを用います。 37x+10y = 1 を拡張されたユークリッ…

37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる

37と10は違いに素なので、は整数解(x, y)を持ちます。 この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。 具体的には、の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。 とおきます。 とおきます。 とおきま…

プライバシーポリシー

お問い合わせ

スポンサーリンク