COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

$1$ 次不定方程式

解の存在条件

定理≪$1$ 次不定方程式と最大公約数≫

 $n$ を $2$ 以上の整数とし, $a_1,$ $\cdots,$ $a_n$ を $0$ でない整数とする. このとき, $n$ 変数 $1$ 次方程式 $a_1x_1+\cdots +a_nx_n = c$ が整数解を持つためには, $c$ が $a_1,$ $\cdots,$ $a_n$ の最大公約数の倍数であることが必要十分である.

証明

 十分性は明らかであるから, 必要性を数学的帰納法で示す.
(i)
$n = 2$ のとき. こちらを参照.
(ii)
$n = k$ ($k$: $2$ 以上の整数)のとき, 主張が成り立つとする. $a_1x_1+\cdots +a_kx_k+a_{k+1}x_{k+1} = c$ が整数解を持つとする. さらに, $a_1,$ $\cdots,$ $a_k$ の最大公約数を $g_k$ とおき, $a_1,$ $\cdots,$ $a_k,$ $a_{k+1}$ の最大公約数を $g_{k+1}$ とおく. このとき, ある整数 $y$ に対して \[ a_1x_1+\cdots +a_kx_k = c-a_{k+1}y\] は整数解を持つから, 帰納法の仮定によりある整数 $x$ について \[ c-a_{k+1}y = g_kx\] となる. $g_kx+a_{k+1}y = c$ は整数解 $(x,y)$ を持つから, (i) の結果により $c$ は $g_k$ と $a_{k+1}$ の最大公約数 $g_{k+1}$ の倍数となる. よって, $n = k+1$ の場合にも主張が成り立つ.
(i), (ii) から, $2$ 以上のすべての整数 $n$ に対して主張が成り立つ.

問題≪$1$ 次不定方程式とイデアル≫

 整数全体の集合を $\mathbb Z$ で表す. $a,$ $b \in \mathbb Z,$ $ab \neq 0$ として, \[ I = \{ ax+by|x,\ y \in \mathbb Z\}\] とおく. 各整数 $m$ に対して $m\mathbb Z = \{ mz|z \in \mathbb Z\}$ と定める. 次のことを示せ.
(1)
$c_1,$ $c_2 \in \mathbb Z,$ $i_1,$ $i_2 \in I$ $\Longrightarrow$ $c_1i_1+c_2i_2 \in I$ が成り立つ.
(2)
$I$ に属する最小の正の整数を $d$ とおく. このとき, $I = d\mathbb Z$ である.
(3)
$a,$ $b$ の最大公約数を $g$ とおく. このとき, $I = g\mathbb Z$ である.

解答例

(1)
$i_k = ax_k+by_k$ ($x_k,$ $y_k \in \mathbb Z,$ $k \in \{ 1,\ 2\}$)と表せるから, \begin{align*} c_1i_1+c_2i_2 &= c_1(ax_1+by_1)+c_2(ax_2+by_2) \\ &= a(c_1x_1+c_2x_2)+b(c_1y_1+c_2y_2) \in I \end{align*} が成り立つ.
(2)
(i)
$d \in I$ と (1) から, 各整数 $z$ に対して $dz \in I$ が成り立つ. よって, $d\mathbb Z \subset I$ である.
(ii)
$n \in I$ とする. 除法の定理により, $n = dq+r$ ($q,$ $r \in \mathbb Z,$ $0 \leqq r < d$)と表せる. このとき, (1) から, \[ r = 1\cdot n+(-q)d \in I\] となる. $d$ の最小性により $r = 0$ であるから, $n = dq \in d\mathbb Z$ が成り立つ. よって, $I \subset d\mathbb Z$ である.
(i), (ii) から, $I = d\mathbb Z$ である.
(3)
(i)
$a = ga',$ $b = gb',$ $d = ax+by$ ($a',$ $b',$ $x,$ $y \in \mathbb Z$)と表すと, 各整数 $z$ に対して \[ dz = (ga'x+gb'y)z = g(a'x+b'y)z \in g\mathbb Z\] となる. よって, $d\mathbb Z \subset g\mathbb Z$ である.
(ii)
\begin{align*} a &= a\cdot 1+b\cdot 0 \in I = d\mathbb Z, \\ b &= a\cdot 0+b\cdot 1 \in I = d\mathbb Z \end{align*} から, $a,$ $b$ は $d$ の倍数である. すなわち, $d$ は $a,$ $b$ の公約数であるから, $g$ は $d$ の倍数である. よって, 各整数 $z$ に対して $gz$ は $d$ の倍数, つまり $gz \in d\mathbb Z$ である. したがって, $g\mathbb Z \subset d\mathbb Z$ である.
(i), (ii) から, $d\mathbb Z = g\mathbb Z$ である.
(2) の結果とあわせると, $I = g\mathbb Z$ が得られる.

背景

  • $1$ 次不定方程式は, 次のように係数の最大公約数と密接な関係がある: 正の整数 $a_1,$ $\cdots,$ $a_n,$ $c$ に対して,
    $a_1x_1+\cdots +a_nx_n = c$ の整数解が存在   
    $\iff$ $c$ は $a_1,$ $\cdots,$ $a_n$ の最大公約数 $g$ の倍数
    が成り立つ. 本問では, $n = 2$ の場合を「集合論的」に示した.
  • 整数全体の集合 $\mathbb Z$ の部分集合 $I$ で \[ c_1,\ c_2 \in \mathbb Z,\ i_1,\ i_2 \in I\ \Longrightarrow\ c_1i_1+c_2i_2 \in I\] を満たす集合は, $\mathbb Z$ の「イデアル」と呼ばれる.
     $\mathbb Z$ のすべての「イデアル」は $m\mathbb Z = \{ mz|z \in \mathbb Z\}$ ($m$: 整数)の形に表されることが知られている.
     「イデアル」は整数全体 $\mathbb Z$ だけでなく, 加法, 減法と乗法が定義された「環」と呼ばれる数の集合において定義され, その概念を用いて数の理論が「集合論的」に整備されている.