不定方程式【ノート】
1人で学べる！高校数学

高校数学[総目次]

高校数学ワンポイント

	スライド	ノート
1. ファクシミリの原理
2. バウムクーヘン分割
3. 円と放物線
4. 垂線の長さ
5. 不定方程式
6. 関数の連続性は導関数に遺伝するか
7. 極方程式における $r$ の正負について
8. 極座標表示における扇形分割積分
9. 素因数分解の一意性
10. 三角関数の不定積分
11. コーシー・シュワルツの不等式
12. 放物線と2接線で囲まれた部分の面積
13. 整式の除法(発展編)
14. 3次関数のグラフの特徴
15. 曲線の長さを求める公式の証明について
16. もう迷わない！必要条件・十分条件のくすっと笑える判定方法
17. 同じものを含む円順列の考え方
18. $f(f(x))=x$ の形をした関数方程式の取り扱い方
19. パラメータが2次で表された直線の通過領域
20. 四面体の面上及び内部を表すベクトル

1．有名な例題

Q. 　「命題：$3x+7y$ は，適当な自然数 $x,y$ を選べば，$n$ 以上の整数を全て表すことができる．」
　この命題を真にする最小の自然数 $n$ を求めなさい．

答

$$\begin{array}{rl}3\cdot 5+7\cdot 1& =22\\ 3\cdot 3+7\cdot 2& =23\\ 3\cdot 1+7\cdot 3& =24\end{array}$$ です．実は本問の場合，連続する3つの整数が表現できれば，それらより大きい整数を全て表現できます．何故というに，$i=0,1,2,\cdots$ とすれば， $$\begin{array}{rl}3\cdot (5+i)+7\cdot 1& =22+3i\\ 3\cdot (3+i)+7\cdot 2& =23+3i\\ 3\cdot (1+i)+7\cdot 3& =24+3i\end{array}$$ と表せるからです．
　次に，$3x+7y=21$ となる自然数の組 $(x,y)$ がないことを示します．$y=1$ のとき， $$3x+7=21$$ となりますが，これを満たす自然数 $x$ は存在しません．$y=2,3$ のときも同様に示されます．
　よって，求める自然数 $n$ は 22 です．

2．不定方程式の重要な定理

　整数論における次の定理は重要です．先ほどの問題とは違って，$(x,y)$ は整数の組であることに注意が必要です．

定理 　$a,b$ を自然数とする．$a,b$ の最大公約数を $d$ とすると $$ax+by=d$$ を満たす整数の組 $(x,y)$ が存在する．

証明

　$S$ を $ax+by(x,y$ は整数) の形で表せる整数の集合とします：

$S=\{ax+by|x,y$ は整数$\}$

　$x,y$ が整数全体を動きますから，集合 $S$ には正の整数があります．その中で最小のものを $m$ とします．証明の流れは次のようになります．

証明の流れ

1. $S\subset \{km|k$ は整数$\}$ を示す．
2. $S\supset \{km|k$ は整数$\}$ を示す．
3. $m=d$ を示す．すると $ax+by=d$ とできる．

1．$S\subset \{km|k$ は整数$\}$ を示す

　$m$ は $S$ の元ですから，ある整数 $x_0,y_0$ によって $$m=a{x}_0+b{y}_0$$ と書けます．
　次に，$S$ の任意の元 $s$ を $m$ で割った商を $k$，余りを $r$ とすると， $$\begin{array}{rl}s& =mk+r(0\leqq r<m)\cdots \mathrm{①}\\ \therefore r& =s-mk\end{array}$$ と書けます．$s=ax+by,m=a{x}_0+b{y}_0$ を代入すると， $$\begin{array}{rl}r& =s-mk\\ & =(ax+by)-(a{x}_0+b{y}_0)k\\ & =a(x-x_{0}k)+b(y-y_{0}k)\end{array}$$

となって，$a\times ($整数$)+b\times ($整数$)$ という形に書けていますから，$r$ も $S$ の元です．$m$ で割った余りである $r$ は $0\leqq r<m$ ですから，$m(>0)$ の最小性より $r=0$ となるしかありません．（もし $r=1,2,\cdots ,m-1$ だったら，$m$ より小さな $S$ の正の元が存在することになり，$m$ が最小であるという設定に矛盾してしまいます．）従って①より $s=km$ です．即ち $S$ の任意の元は，集合 $\{km|k$ は整数$\}$ の元ですから

$S\subset \{km|k$ は整数$\}$

がいえました．

2．$S\supset \{km|k$ は整数$\}$ を示す

　$m=a{x}_0+b{y}_0$ ですから $km=a(k{x}_0)+b(k{y}_0)$ です．これは $km$ が $a\times (\text{整数})+b\times (\text{整数})$ という形に書けることを意味しますから $S$ の元です．従って

$S\supset \{km|k$ は整数$\}$

がいえました．

---

　1．及び2．により，「 $S\subset \{km|k$ は整数$\}$ かつ $S\supset \{km|k$ は整数$\}$ 」 となりましたから，

$S$ $=$ $\{km|k$ は整数$\}$

がいえました．即ち $S$ は $m$ の倍数の集まりなのです．

---

3．$m=d$ を示す

　$m=a{x}_0+b{y}_0$ でした．この右辺は $a$ と $b$ の最大公約数 $d$ を用いて

$d\times$ (整数)

と書けますから $d$ の倍数，従って左辺の $m$ も $d$ の倍数です ($m\geqq d\cdots \mathrm{②}$)．

　一方，$a=a\cdot 1+b\cdot 0$，及び $b=a\cdot 0+b\cdot 1$ ですから，$a,b\in S$．従って $a$ も $b$ も $m$ の倍数ですから $m$ は $a$ と $b$ の公約数です ($m\leqq d\cdots \mathrm{③}$)．
　②，③より $m=d$ がいえました．

　以上により，

集合 $\mathit{S}$ と集合 $\mathbf{\{}\mathit{k}\mathit{d}|\mathit{k}$ は整数$\mathbf{\}}$ は一致する

ことが示されました．故に $ax+by=d$ を満たす整数の組 $(x,y)$ が存在します．

■

補足

　不定方程式 $ax+by=c$ は，$c$ が $d$ の倍数のときのみ解をもつことが，上の考察からわかります．

系 　自然数 $a,b$ について，
　　$a,b$ が互いに素
　　$⟺ax+by=1$ を満たす整数の組 $(x,y)$ が存在する．

証明

$\Leftarrow )$ $a$ と $b$ が互いに素でないなら，$a$ と $b$ が1より大きい公約数 $d$ をもち，

$$a=a^{\prime }d,b=b^{\prime }d$$

と表せますから，$a^{\prime }dx+b^{\prime }dy=1$，即ち

$$d(a^{\prime }x+b^{\prime }y)=1$$

を満たす整数 $x,y$ が存在することになります．ところが $d$ は2以上，右辺は1ですからこれは不合理です．

$\Rightarrow )$　$a$ と $b$ が互いに素ですから最大公約数 $d$ は 1 です．従って先に示した定理により $ax+by=1$ となる整数 $x,y$ が存在します．

■

補足

$\Rightarrow )$ については次のように示すこともできます：

　$a>b$ としても一般性は失われません．$b$ 個の整数

$$a\times 1,a\times 2,a\times 3,\cdots ,a\times b$$

について，これらを $b$ で割った余りはすべて異なります．実際，$a\times i$ と $a\times j$ (ただし，$1\leqq i\leqq j\leqq b$) を $b$ で割った余りがともに $r$ とすれば，$q_1,q_2$ を整数として

$$\{\begin{array}{l}a\times i=b{q}_1+r\\ a\times j=b{q}_2+r\end{array}$$

と表せます．2式から $r$ を消去して，

$$a(i-j)=b(q_1-q_2)$$

　右辺は $b$ の倍数ですから左辺も $b$ の倍数でなければなりません．ところが $a$ と $b$ は互いに素で，$0\leqq i-j\leqq b-1(<b)$ ですから結局

$$i-j=0\therefore i=j$$

となるしかありません．つまり余りが同じなら，元の数も同じだったということです．対偶をとれば，元の数が異なれば，余りも異なるといえます．これで先の $b$ 個の整数を $b$ で割った余りがすべて異なることが示されました．

　整数を $b$ で割った余りは

$$0,1,2,\cdots ,b-1$$

の $b$ 個しかありませんから，先の $b$ 個の整数の中に $b$ で割ったときの余りが1であるものが存在します．即ち

$$a\times i=bq+1$$

$$\therefore a\times i+b\times (-q)=1$$

を満たす整数 $i,-q$ が存在しますから，題意が示されました．

■

例1

　$6x+9y(x,y$ は整数$)$ で表される数は 3(6と9の最大公約数)の倍数(全て)です．また，例えば $6\cdot (-1)+9\cdot 1=3$ です．

例2

　$3x+5y(x,y$ は整数$)$で表される数は整数全体です．例えば $3\cdot 2+5\cdot (-1)=1$ ですから，$k$ を任意の整数として， $$3\cdot 2k+5\cdot (-k)=k$$ と表せます．

---

高校数学[総目次]

高校数学ワンポイント

	スライド	ノート
1. ファクシミリの原理
2. バウムクーヘン分割
3. 円と放物線
4. 垂線の長さ
5. 不定方程式
6. 関数の連続性は導関数に遺伝するか
7. 極方程式における $r$ の正負について
8. 極座標表示における扇形分割積分
9. 素因数分解の一意性
10. 三角関数の不定積分
11. コーシー・シュワルツの不等式
12. 放物線と2接線で囲まれた部分の面積
13. 整式の除法(発展編)
14. 3次関数のグラフの特徴
15. 曲線の長さを求める公式の証明について
16. もう迷わない！必要条件・十分条件のくすっと笑える判定方法
17. 同じものを含む円順列の考え方
18. $f(f(x))=x$ の形をした関数方程式の取り扱い方
19. パラメータが2次で表された直線の通過領域
20. 四面体の面上及び内部を表すベクトル