ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

ノリの悪い日記 https://www.port-k.com

陥没地帯 (239)

高校数学整数問題

$1$ 次方程式の整数解を求めるやり方として, 共通テストで出題されるような簡単な問題は, 合同式で求めた方が早いと思うが, そうでない場合は, 連分数で求めることにしている.

不定方程式 $ax+by=1$ の整数解 (特殊解) を見つけたかったら, $b/a$ を連分数展開して, $b/a$ の直前の近似分数 $d/c$ を求めてやると,

$\begin{align} \left|\frac{d}{c}- \frac{b}{a}\right| &=& \left|\frac{ad-bc}{ac}\right| \\&=& \left|\frac{1}{ac}\right| \end{align}$

という性質があるので,

$|ad-bc| = 1$

となり, $x=d$ , $y = -c$ または, $x= -d$ , $y = c$ が整数解のひとつとなる.

例として,

$115x + 366y =1$ の場合には,
$\mathrm{gcd}(115,366)=1$ だから, 整数解が存在する. まず, $\displaystyle{\frac{366}{115}}$ を連分数展開して,

$\displaystyle{ \frac{366}{115} \\= 3+ \dfrac{21}{115} \\= 3+ \dfrac{1}{5 + \dfrac{10}{21}} \\= 3+ \dfrac{1}{5+ \dfrac{1}{2 + \dfrac{1}{10}}}}$

とし, 直前の近似分数は最後の $1/10$ を切り捨てた,

$\displaystyle{ 3+ \dfrac{1}{5+ \dfrac{1}{2}} }$

で, これを普通の分数に戻す.

$\displaystyle{ 3+ \frac{2}{11} = \frac{35}{11} }$

したがって,

$\displaystyle{ \frac{366}{115} - \frac{35}{11} = \frac{366\cdot 11 - 115 \cdot 35}{315 \cdot 11}}$

となって,

$x = -35$ , $y = 11$ が特解として求まる. 後は,

$115x + 366y =1$
$-115\cdot 35 + 366 \cdot 11 =1$

から,

$115(x+35) = -366(y-11)$

となって, $115$ と $366$ が互いに素であることより,

$x = -35 -366k$ , $y = 11 + 115k$
( $k$ は整数)

のように求まる.

もう一題だけやっておくと,

$22x + 37y = 2$

の場合は, まず,

$22x' + 37y' = 1$

の特解を求めて結果を $2$ 倍すればよかった.

$\displaystyle{\dfrac{37}{22} = 1+ \dfrac{1}{1+\dfrac{1}{2 + \dfrac{1}{7}}}}$

なので, 直前の近似分数は,

$\displaystyle{1+ \dfrac{1}{1+\dfrac{1}{2 }} = \dfrac{5}{3}}$

したがって, $x' = -5$ , $y' = 3$ となり, $x = -10$ , $y = 6$ が特解として求まる.

したがって, 一般解は,

$x = -10-37k$ , $y = 6 + 22k$
( $k$ は整数)

となる.
//

※ もっとも, この問題ぐらいだと, 合同式で, 以下すべて法 $22$ として,

$37 y \equiv 2$
$15 y \equiv 2$ $(A)$

$2$ 倍して,

$30 y \equiv 4$
$8 y \equiv 4$ $(B)$

$(A) + (B)$ で,

$23y \equiv 6$
$y \equiv 6$

$y = 6 + 22k$ から,

$\begin {align} x &= \frac{2 - 37(6+22k)}{22} \\ &= -10 -37k \end{align}$

と求まるのだから, 連分数の方が早いかどうかは微妙である.
//