よく使う性質
合同方程式の解き方
$ax \equiv 0 \pmod M$ の解き方
$ax \equiv b \pmod M$ の解き方
$x$ と $k$ に関する1次不定方程式 $ax + Mk = b$ を解けばよい。
$x \equiv a \pmod M,\ x \equiv b \pmod N$ の解き方
CRT をする → 代数学を使った整数論
CRT は N と M が互いに素である必要がある点に注意
出題例
$ax + by = 1$ （$a,b$ は互いに素）は解を持つ
とくに $|x| \leq |b|$、$|y| \leq |a|$ をみたす解が存在する。
拡張ユークリッドの互除法をすると、自然に$|x| \leq |b|$、$|y| \leq |a|$ をみたす解が得られる。
また、1つ解 $(x_0, y_0)$ が得られたとき、以下の方法で一般解が得られる
$a,b$ が互いに素で $ax + by = 1$ が解 $(x_0, y_0)$ を持つとき、$a(x-x_0) + b(y - y_0) = 0$ を満たす。
このとき、$x-x_0 = bk,\ y - y_0 = -ak$ と書けるので、$x = x_0 + bk,\ y = y_0 - ak$ が一般解になる。
$ax + by = d$ （$a,b$ は互いに素）は解を持つ
$ax + by = \gcd(a,b)$ は解を持つ