一次合同方程式が解を持つ条件
補題1
主張
$ a, b, c \in \mathbb{Z} とする。$ a, c が互いに素な整数ならば $ ax \equiv b (\bmod c) は解を持つ。 証明
互いに素な整数の剰余定理より、$ 0, a, 2a, \dots, (c-1)a を$ c で割った余りはすべて異なる。 よってその中に$ c で割った余りが$ b と等しいものが存在するので、それを$ ka とすると、$ ax \equiv ak (\bmod c)
$ a, c は互いに素な整数だから両辺を$ a で割っても合同式は成り立つ。よって$ x \equiv k (\bmod c) である。 つまり$ x = cn + k (n \in \mathbb{Z}) が解である。
NOTE: 逆は必ずしも真ではない。つまり、解を持っても互いに素とは限らない。実際、
$ 4x \equiv 2 (\bmod 6) \Leftrightarrow 4x = 6n + 2(n \in \mathbb{Z}) \Leftrightarrow 2x = 3n + 1 \Leftrightarrow 2x \equiv 1 (\bmod 3) は$ \gcd(2, 3) = 1 より解を持つ。
次のようにすれば必要十分条件となる。
補題2
$ a, b, c \in \mathbb{Z} とする。次は同値である。
$ \gcd(a, c) で$ b が割り切れる。
$ ax \equiv b (\bmod c) は解を持つ。
証明
$ d = \gcd(a, c) とする。
必要性
$ ax \equiv b (\bmod c) \Leftrightarrow ax = cn + b (n \in \mathbb{Z}) \Leftrightarrow \frac{a}{d} x = \frac{c}{d} n + \frac{b}{d}
ここで、$ d は$ a, c の最大公約数だから$ a/d, c/d はともに整数。これを$ a', c' とする。
また、仮定より$ b/d も整数。これを$ b' とする。このとき与式は下記と同値。
$ a'x = c'n + b' \Leftrightarrow a'x \equiv b' (\bmod c')
また、$ a', c' は互いに素な整数である。実際、そうでないとすれば公約数$ k \ge 2 が存在するため$ dk > d が公約数となり$ d が最大公約数であることに矛盾する。 よって、補題1から$ a'x \equiv b' (\bmod c') は解を持つ。
よって、それと同値な元の式$ ax \equiv b (\bmod c) も解を持つ。
十分性
対偶を示す。$ ax \equiv b (\bmod c) \Leftrightarrow ax - cn = b (n \in \mathbb{Z})
左辺は$ d の倍数だが右辺は$ d の倍数ではない。よってこの式を満たす$ x, n の組は存在しない。