1次不定方程式

整数(教科書範囲)　★★

1次不定方程式について一通り扱います．

1次不定方程式と解法

$x$，$y$ の1次方程式( $a$，$b$，$c$ は整数．$a\neq 0$，$b\neq 0$ )

$ax+by=c$

は未知の文字 $x$，$y$ に対して式が1つしかないので解が1つに定まらず，このような方程式を不定方程式といいます．不定方程式を成立させる整数 $x$，$y$ のことをこの方程式の整数解といいます．上の式は1次不定方程式といいます．

以下では基礎の2タイプの解法を紹介します．

基礎のタイプ( $c=0$ )

まずは下の不定方程式の整数解を考えます．今後の基礎の形になります．

$3x-4y=0$

移項すると

$3x=4y$

$x$ は整数なので左辺は $3$ の倍数です．すると右辺も $3$ の倍数ですが，$4$ は $3$ の倍数でないので $y$ が $3$ の倍数とならなければなりません．同様に $x$ は $4$ の倍数なので

$\begin{cases}x=4k \\ y=3k\end{cases}$ ( $k$ は整数)

が求める整数解になります．

基礎のタイプ( $c=1$ )

次に下の不定方程式の整数解を考えます．

$3x-4y=1$

先程と同じように移項すると $1$ が邪魔なことに気がつきます．そこで，元の式から，好みの整数解を1組代入した式を辺々引きます．

$3x-4y=1$

$\underline{-) \ 3\cdot\color{red}{3}-4\cdot \color{red}{2}=1 \ }$

$3(x-3)-4(y-2)=0$

すると右辺が $0$ になりましたので先程と同様に

$3(x-3)=4(y-2)$

$\begin{cases}x-3=4k \\ y-2=3k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}x=4k+3 \\ y=3k+2\end{cases}$ ( $k$ は整数)

となります．

好みの整数解1組を特殊解ということが多いようです(それに対し整数解すべてを一般解といいます)．今回は $(x,y)=(\color{red}{3},\color{red}{2})$ としましたが，正しければ何でもよく，チョイスした特殊解によって整数解の表記が異なる点に注意です．

例えば特殊解を $(x,y)=(\color{blue}{7},\color{blue}{5})$ としたら整数解は

$\begin{cases}x=4k+\color{blue}{7} \\ y=3k+\color{blue}{5}\end{cases}$ ( $k$ は整数)

となり，解の定数部分に特殊解が来ることがわかります(検算になります)．

以上のように示している整数解は同じでも表現方法が無限通りあるので試験で採点する方は大変だったりします．

ポイント

1次不定方程式の整数解の存在条件

1次不定方程式はそもそも常に整数解をもつのかについて，以下の定理を扱います．

稀に証明が入試で扱われます．

ポイント

右辺が $1$ なら $a$ と $b$ が互いに素でないと整数解をもちません．

例題と練習問題

例題

講義

すべて特殊解を見つけるのが先です．

(2)は右辺が $1$ のときの特殊解を $2$ 倍して見つける作戦が有効です．

(3)はユークリッドの互助法による特殊解の算出で特殊解を見つけます．見つけ方が独特なので初めての方やわからない方はリンク先をご覧ください．

解答

(1)

$2x-7y=1$

$\underline{-) \ 2\cdot4-7\cdot 1=1 \ }$

$2(x-4)-7(y-1)=0$

$\Longleftrightarrow \ 2(x-4)=7(y-1)$

$\therefore \ \begin{cases}x-4=7k \\ y-1=2k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}\boldsymbol{x=7k+4} \\ \boldsymbol{y=2k+1}\end{cases}$ ( $\boldsymbol{k}$ は整数)

※ 整数解を元の式に代入して成立していれば他の表現ももちろん正解です．

※ 数学B既習者向けですが，1次不定方程式の解は直線の媒介変数表示をしただけです．上の解は直線 $2x-7y=1$ 上の格子点に他なりません．

(2)

$9x+8y=1$ のときの特殊解 $(x,y)=(1,-1)$ を $2$ 倍して考えます．

$9x+8y=2$

$\underline{-) \ 9\cdot2+8\cdot (-2)=2 \ }$

$9(x-2)+8(y+2)=0$

$\Longleftrightarrow \ 9(x-2)=8(-y-12)$

$\therefore \ \begin{cases}x-2=8k \\ -y-2=9k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}\boldsymbol{x=8k+2} \\ \boldsymbol{y=-9k-2}\end{cases}$ ( $\boldsymbol{k}$ は整数)

(3)

これを踏まえ

$155x+42y=2$

$\underline{-) \ 155\cdot(-13)+42\cdot 48=1 \ }$

$155(x+13)+42(y-48)=0$

$\Longleftrightarrow \ 155(x+13)=42(-y+48)$

$\therefore \ \begin{cases}x+13=42k \\ -y+48=155k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}\boldsymbol{x=42k-13} \\ \boldsymbol{y=-155k+48}\end{cases}$ ( $\boldsymbol{k}$ は整数)

※ ユークリッドの互助法による特殊解の出し方の例題と同じ式です．

練習問題

練習1の解答

(1)

$5x+8y=1$

$\underline{-) \ 5\cdot5+8\cdot (-3)=1 \ }$

$5(x-5)+8(y+3)=0$

$\Longleftrightarrow \ 5(x-5)=8(-y-3)$

$\therefore \ \begin{cases}x-5=8k \\ -y-3=5k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}\boldsymbol{x=8k+5} \\ \boldsymbol{y=-5k-3}\end{cases}$ ( $\boldsymbol{k}$ は整数)

(2)

$\begin{align}\color{red}{1}&=\color{red}{13}-\color{red}{4}\times 3 \\ & =\color{red}{13}-(\color{blue}{30}-\color{red}{13}\times2)\times3 \\ & =\color{red}{13}\times7-\color{blue}{30}\times3 \\ & =(\color{blue}{133}-\color{blue}{30}\times4)\times7-\color{blue}{30}\times3 \\ & =\color{blue}{133}\times7-\color{blue}{30}\times31\end{align}$

$133x-30y=2$

$\underline{-) \ 133\cdot14-30\cdot 62=2 \ }$

$133(x-14)-30(y-62)=0$

$\Longleftrightarrow \ 133(x-14)=30(y-62)$

$\therefore \ \begin{cases}x-14=30k \\ y-62=133k\end{cases}$ ( $k$ は整数)

求める整数解は

$\begin{cases}\boldsymbol{x=30k+14} \\ \boldsymbol{y=133k+62}\end{cases}$ ( $\boldsymbol{k}$ は整数)

※ ユークリッドの互助法による特殊解の算出の練習問題と左辺は同じ式です．

練習2の解答

$n=9x+6=11y+5$ ( $x$，$y$ は整数)とおく．

$9x-11y=-1$

$\underline{-) \ 9\cdot6-11\cdot 5=-1 \ }$

$9(x-6)-11(y-5)=0$

$\Longleftrightarrow \ 9(x-6)=11(y-5)$

$\therefore \ x-6=11k \ \Longleftrightarrow \ x=11k+6$ ( $k$ は整数)

$\therefore \ n=9(11k+6)+6=99k+60$

$k=9$ で $n=951$，$k=10$ で $n=1050$ より，$1000$ に最も近いのは $\boldsymbol{951}$