高校数学 (2) - ノリの悪い日記

いろいろ試行錯誤しているうちに, 一次不定方程式の解き方は, やっぱり合同式がもっともよいという結論に達した. 解くのに試行錯誤さえいらず, どんな場合にも解けることがわかったし計算も簡単である. 自然数解が簡単に扱えるので適用範囲も広い. 以下の問題を最終結論に達した方法で解いてみる.

【問】
次の方程式の整数解をすべて求めよ.

$344x + 149y = 1$

【解】
合同式,

$344x \equiv 1 \pmod{149}$

を解けばよいのだが, まずユークリッド互除法を実行する.

$344= 2\times 149 + 46$
$\Rightarrow 46= 344 - 2\times 149$

$149 = 3 \times 46 + 11$
$\Rightarrow 11= 149 - 3\times 46$

$46 = 4 \times 11 + 2$
$\Rightarrow 2= 46 - 4\times 11$

$11 = 5 \times 2 + 1$
$\Rightarrow 1= 11 - 5\times 2$

後は, 上の互除法の式に合わせて順番に合同式を計算するだけである. 最初に,

$344x \equiv 1 \pmod{149}$
$149x \equiv 0 \pmod{149}$

とする.

$\begin{eqnarray} 46x &=& 344x - 2 \times 149x \\ &\equiv& 1 \pmod{149}\\ \end{eqnarray}$

$\begin{eqnarray} 11x &=& 149x - 3 \times 46x\\ &\equiv& -3 \pmod{149}\\ \end{eqnarray}$

$\begin{eqnarray}2x &=& 46x - 4 \times 11x\\ &\equiv& 1-4\times(-3) \pmod{149}\\ &\equiv& 13 \pmod{149} \\\end{eqnarray}$

$\begin{eqnarray} x &=& 11x - 5 \times 2x\\ &\equiv& -3 -5 \times 13 \pmod{149}\\ &\equiv& -68 \pmod{149}\\ \end{eqnarray}$

したがって, $k$ を整数として,

$x = -68 + 149k$

これを代入して,

$\begin{eqnarray} 149y &=& 1- 344x \\ &=& 1-344(-68 + 149k)\\ &=& 1 + 344 \times 68 -344 \times 149 k\\ &=& 23393 -344 \times 149 k\\ \end{eqnarray}$

$y = 157 - 344k$

となる.//

灘中の自然数解の問題をこのやり方でも解いておこう. 問題に相応しい簡単さで解けているのではないかと思う.

(解)
$66x + 35y = 3890$ の自然数解 $x$ , $y$ を求める.

$66= 35 + 31$
$\Rightarrow 31= 66- 35$

$35 = 31 + 4$
$\Rightarrow 4 = 35 - 31$

$31 = 7 \times 4 + 3$
$\Rightarrow 3 = 31 - 7\times 4$

$4= 3 + 1$
$\Rightarrow 1= 4- 3$

最初に,

$66x \equiv 3890 \equiv 5 \pmod{35}$
$35x \equiv 0 \pmod{35}$

とおく.

$\begin{eqnarray} 31x &=& 66x - 35x\\ &\equiv& 5 \pmod{35}\\ \end{eqnarray}$

$\begin{eqnarray} 4x &=& 35x - 31x\\ &\equiv& -5 \pmod{35}\\ \end{eqnarray}$

$\begin{eqnarray} 3x &=& 31x - 7\times 4x\\ &\equiv& 5- 7 \times(-5) \pmod{35}\\ &\equiv& 5 \pmod{35}\\ \end{eqnarray}$

$\begin{eqnarray} x &=& 4x - 3x\\ &\equiv& -10 \pmod{35}\\ &\equiv& 25 \pmod{35}\\ \end{eqnarray}$

したがって, $k$ を整数として,

$x = 25 + 35k$

とおける.

$\begin{eqnarray} 35y &=& 3890 - 66x \\ &=& 3890 - 66(25 + 35k)\\ &=& 3890 - 1650 - 66 \times 35k \\ &=& 2240- 66 \times 35k \\ \end{eqnarray}$

したがって,

$y = 64 - 66k$

以上,

$x = 25 + 35k$ ,
$y = 64 - 66k$

なので, $x$ , $y$ の両方が自然数となるのは, $k = 0$ のときのみで,

$x = 25$ , $y = 64$

となる. //