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

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