ホーム >> 整数 >> $1$ 次合同式の解の個数

学校教育では学ぶ機会が少ない $1$ 次合同式の理論について解説します.




$1$ 次合同式とは

普通の数の世界で方程式を解くことを考えたように,合同式の世界でも方程式を解くということを考えることができます.ここでは最も簡単な $1$ 次合同式について考えてみましょう.

たとえば,次の式を見てください. $$3x \equiv 4  (mod\ 5)$$ この式は,どのような $x$ に対して,$3x$ を $5$ で割った余りが $4$ になるかということを問うている $1$ 次合同式です.ここで,$5$ を法として考えているので,考えられる答えの候補は $x \equiv 0,1,2,3,4 (mod\ 5)$ の $5$ 通りです.ひとつずつ代入してみると,$x \equiv 3 (mod\ 5)$ のときにのみ,$9 \equiv 4 (mod\ 5)$ となり,式が成り立つことがわかります.したがって,$1$ 次合同式 $3x \equiv 4  (mod\ 5)$ の解は $x \equiv 3 (mod\ 5)$ です.このようにして,$1$ 次合同式を解くことができます.

$\underline{Example}$
$4x \equiv 5 (mod\ 3)$ の解は $x \equiv 2 (mod\ 3)$
$5x \equiv 3 (mod\ 4)$ の解は $x \equiv 3 (mod\ 4)$
$12x \equiv 5 (mod\ 11)$ の解は $x \equiv 5 (mod\ 11)$

$1$ 次合同式の解がない例

普通の数の世界における $1$ 次方程式には必ず解が存在します.ところが,$1$ 次合同式には解が存在しない場合があります.次の例を見てください.
$$5x \equiv 1 (mod\ 5)$$ この $1$ 次合同式の解は存在しません.実際に,$x \equiv 0,1,2,3,4$ のいずれを代入しても合同式が成り立たないことは容易にわかります.合同式の意味を考えれば,与えられた式は,どのような $x$ に対して,$5x$ を $5$ で割った余りが $1$ となるかということを聞いていますが,$x$ が $mod 5$ の世界でいかなる数であっても,$5x \equiv 0 (mod\ 5)$ なので,$5x \equiv 1 (mod\ 5)$ を満たす $1$ 次合同式は存在しません.

$\underline{Example}$
$4x \equiv 3 (mod\ 6)$ の解はない
$5x \equiv 2 (mod\ 10)$ の解はない
$12x \equiv 7 (mod\ 4)$ の解はない

$1$ 次合同式の解が複数ある例

普通の数の世界における $1$ 次方程式の解は必ず $1$ つですが,$1$ 次合同式の解は必ずしもひとつとは限りません.一般には,有限個ならばいくらでも解をもつ $1$ 次合同式が存在します.たとえば, $$4x \equiv 8 (mod\ 6)$$ の解は,$x \equiv 2,5 (mod\ 6)$ の $2$ つあります.

$\underline{Example}$
$3x \equiv 12 (mod\ 9)$ の解は $x \equiv 1,4,7 (mod\ 9)$ の $3$ つ
$4x \equiv 0 (mod\ 8)$ の解は $x \equiv 0,2,4,6 (mod\ 8)$ の $4$ つ

一般論

さて,これまで,$1$ 次方程式の解の個数が様々あることを見てきましたが,どのような時に解が $1$ つで,どのようなときに解がなくて,どのようなときに解が複数個あるのでしょうか.それらを判定する一般的な手段について,次のことが知られています.証明は載せませんが,それほど難しくないので,できれば考えてみてください.

解が一つの場合: 一般に,$1$ 次合同式 $$ax \equiv b (mod\ m)$$ について,$a$ と $m$ が互いに素ならば,解がただひとつ存在する.

解が存在しない場合: 一般に,$1$ 次合同式 $$ax \equiv b (mod\ m)$$ について,$a$ と $m$ の最大公約数 $d$ が $b$ の約数でないならば,解は存在しない.

解が複数存在する場合: 一般に,$1$ 次合同式 $$ax \equiv b (mod\ m)$$ について,$a$ と $m$ の最大公約数 $d$ が $b$ の約数ならば,解の個数は $d$ 個である.

$d=1$ のときは,$a$ と $m$ が互いに素となるので,解はひとつです.


$1$ 次合同式と $1$ 次不定方程式は本質的に同じです.