アルゴリズム論特論（塩田）第6回 (4) 法と互いに素でない除数
法と互いに素でない除数
問 (1) $4 \times x \equiv 3 \pmod{10}$ は解を持つか？
答え
$4x$ を $10$ で割った余りは偶数しかあり得ませんので、$3$ にはなりません。
よって解はありません。
(2) $4 \times x \equiv 6 \pmod{10}$ は解を持つか？
答え
問題は
$4 x = 6 + 10y$ は整数解 $(x,y)$ を持つか
と言い換えられます。両辺を $2=\gcd(4,10)$ で割れば
$2 x = 3 + 5y$ は整数解 $(x,y)$ を持つか
となり、結局
$2 \equiv 3 \pmod 5$ は解 $x$ を持つか
という問題に帰着します。
これは
Th.5 より $\bmod 5$ で唯一の解 $x \equiv 4 \pmod 5$ を持ちますが、
$\bmod 10$ では 2 つの解 $x \equiv 4,\,9 \pmod{10}$ を持つことになります。
これを一般化すると
Prop.8 $d = \gcd(b,n) \gt 1$ とする。このとき、合同式
$b \times x \equiv a \pmod n$
の解は
- $a$ が $d$ の倍数でなければ存在しない。
- $a$ が $d$ の倍数であれば $\bmod n$ で $d$ 個の解が存在する。
証明 は上の
問 と同じことを記号で書くだけです。(証明終)
※ 演算では結果が唯一であることが好ましいので、
法 $n$ の除算を考えるときは大抵、
除数 $b$ が $n$ と互いに素 であることを仮定します。