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

中国剰余定理とは、2式の場合を互いに素とするとき、


を満たす整数xがの範囲内にただ一つ存在するというものです。
xの求め方はこうです。
まずを満たす(p, q)のセットを一つ求めます。
以下のアルゴリズムを用います。

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

求まったpを用いて、解は、
となります。
なお、qを用いて、でもよいです。
ここでxがの範囲にない場合は、の倍数を加えて、範囲内に持ってこればよいです。