そんな事に気がついたのが一昨日だったので、即座にヨドバシさんで購入・・・
しようとしたのですが、何故か販売休止に・・・
仕方なく、困ったときの amazon さんで購入しようとしたら、２２００円という意味不明なプレミアがついていました・・・
って事で、図書室に出入りしている本屋さんに取り寄せを頼みました。まあ、特段急ぐものでもないのでいいのですが・・・
何故、ヨドバシさんでは販売休止になっていたのでしょうか？？
休校期間が続いていて、勉強出来ない高校生が買って・・・って事も無さそうだけど・・・
今日は、授業で出題した課題の解説。
不定方程式の問題。我々の様に、高校生のときに整数がなかった世代では、好き嫌いが分かれるところですが、私は専門が代数的組合せ論（代数的符号理論）だったので、整数の内容は大好物です。
ということで, 週末課題 No.04 の解説を.
(1) 不定方程式 $23x+41y=0$ の整数解をすべて求めよ.
(2) 不定方程式 $23x+41y=1$ の整数解を $1$ 組求めよ.
(3) 不定方程式 $23x+41y=1$ の整数解をすべて求めよ.
(1)
$23x+41y=0$
$23x=-41y$
ここで, $23$ と $41$ は互いに素であるので, 整数 $k$ を用いて
$x=41k$, $y=-23k$ と表すことができる.
で終わりなのだが, 結構これをちゃんと理解していない人も多い.
そこで, これをちゃんと説明していくと...
$23x=-41y$ となったところから...
$x$, $y$ は整数なので, 左辺は $23$ の倍数, 右辺は $41$ の倍数, ということになる.
左辺が $23$ の倍数, 右辺が $41$ の倍数で, それらが等しい, ということは,
この値は $23$ の倍数かつ $41$ の倍数なので, $23 \times 41$ の倍数...
ではないですよね.
$23$ の倍数かつ $41$ の倍数, って事は, $23$ と $41$ の公倍数, って事です.
$23$ と $41$ の公倍数, って事は, $23$ と $41$ の最小公倍数の倍数, って事です.
で, 結構重要な性質として...
$2$ つの自然数 $a$, $b$ に対し,
$\gcd(a, b) \times \mathrm{lcm}(a, b) = ab$
が成り立つ.
を使ってやると,
$\gcd(23, 41) \times \mathrm{lcm}(23, 41) = 23 \times 41$
$1 \times \mathrm{lcm}(23, 41) = 23 \times 41$
$\mathrm{lcm}(23, 41) = 23 \times 41$
であるので...
$23$ と $41$ の最小公倍数の倍数, って事は, $23\times41$ の倍数, って事です.
なので, 整数 $k$ を用いて
$23x=-41y=23 \times 41 \times k$
と表すことができ, これより
$23x=23\times41\times k$
$x=41k$,
$-41y=23\times41\times k$
$y=-23k$
と表すことができる.
(2)
$41 = 23 \times 1 + 18$
$23 = 18 \times 1 + 5$
$18 = 5 \times 3 + 3$
$5 = 3 \times 1 + 2$
$3 = 2 \times 1 + 1$
より,
$18 = 41 - 23 \times 1$
$5 = 23 - 18 \times 1$
$3 = 18 - 5 \times 3$
$2 = 5 - 3 \times 1$
$1 = 3 - 2 \times 1$
であるので,
$1 = 3 - 2 \times 1$
$= 3 - (5 - 3 \times 1) \times 1$
$= 3 \times 2 + 5 \times (-1)$
$= (18-5 \times 3) \times 2 + 5 \times (-1)$
$= 18 \times 2 + 5 \times (-7)$
$= 18 \times 2 + (23 - 18 \times 1) \times (-7)$
$= 18 \times 9 + 23 \times (-7)$
$= (41 - 23 \times 1) \times 9 + 23 \times (-7)$
$= 41 \times 9 + 23 \times (-16)$
$= 23 \times (-16) + 41 \times 9$
よって, 特殊解 $(x, y)=(-16, 9)$ を得る.
というのが, よくある一般的な解法なのだが...
ユークリッドの互除法よりも計算回数を減らせるかも知れない, 高速ユークリッドの互除法を用いる.
ユークリッドの互除法では, 割り算 $a=bq+r$ の
余りの範囲を $0 \le q < r$ としているが,
これを $-\dfrac{r}{2}<r\le\dfrac{r}{2}$ として計算すると,
ユークリッドの互除法よりも計算回数が増えることはない.
（必ず減るとは言えない, 減ることもある, 程度だが非常に有用）
$41 = 23 \times 2 - 5$
$23 = 5 \times 5 - 2$
$5 = 2 \times 2 + 1$
より,
$5 = 23 \times 2 - 41$
$2 = 5 \times 5 - 23$
$1 = 5 - 2 \times 2$
であるので,
$1 = 5 - 2 \times 2$
$= 5 - (5 \times 5- 23) \times 2$
$= 5 \times (-9) + 23 \times 2$
$= (23 \times 2 - 41) \times (-9) + 23 \times 2$
$= 41 \times 9 + 23 \times (-16)$
よって, 特殊解 $(x, y)=(-16, 9)$ を得る.
（高速）ユークリッドの互除法を用いる解法として, 更に別解もある.
$23x+41y=1$
$23x+(23 \times 2 - 5)y = 1$
$23x+23\times2y-5y = 1$
$23(x-2y)-5y = 1$
ここで, $x-2y=x_1$ とおく.
$23x_1-5y=1$
$(5 \times 5 - 2)x_1 - 5y = 1$
$5 \times 5x_1-2x_1 - 5y = 1$
$-2x_1+5(5x_1-y) = 1$
ここで, $5x_1-y=y_1$ とおく.
$-2x_1+5y_1=1$
これくらいになると, $x_1=2$, $y_1=1$ というような特殊解が思いつく.
前述の置き換えの式より
$y=5x_1+y_1$
$x=x_1+2y$
であるので, 前述の特殊解を代入すると,
$y=5 \times 2 + 1 = 11$
$x=2+2 \times 11 = 24$
であるので, 特殊解 $(x, y)=(24, 11)$ を得る.
$x_1$, $y_1$ の特殊解が異なると, 最後に出てくる特殊解も異なる.
他にも, 適当に代入して $1$ になる値を見つけられればいいが,
$-16$ と $9$ なんて, なかなか見つけられない...
そこで, $1$ にならなくてもいいので, 互いに素な値になる $2$ 式を考える.
例えば,
$23 \times 2 + 41 \times (-1) = 5$
$23 \times (-5) + 41 \times 3 = 8$
なんていう $2$ 式を見つけたとする.
ここから, $23$ と $41$ を文字のように考え, 右辺が $1$ になるように計算をしていく.
具体的にいうと, 第 $1$ 式の $2$ 倍から第 $2$ 式を引く.
$23(2 \times 2 - (-5)) + 41 (-2-3) = 5 \times 2 - 8$
$23 \times 9 + 41 \times (-5) = 2$
第 $1$ 式からこの式の $2$ 倍を引く.
$23(2-9 \times 2) + 41(-1-2 \times (-5)) = 5 - 2 \times 2$
$23 \times (-16) + 41 \times 9 = 1$
これより, 特殊解 $(x, y)=(-16, 9)$ を得る.
式同士の計算の手順が異なったりすると,
異なる特殊解を得ることがある.
(3)
(2) で求めた特殊解が $(x, y)=(-16, 9)$ であるとする.
(他の特殊解だったとしても解法は同様)
$23x+41y=1$ から特殊解を代入した $23 \times (-16) + 41 \times 9 = 1$ を引くと,
$23(x+16)+41(y-9)=0$
$23(x+16)=-41(y-9)$
あとは (1) と同様に,
$23$ と $41$ は互いに素であるので, 整数 $k$ を用いて
$x+16=41k$, $y-9=-23k$
即ち
$x=41k-16$, $y=-23k+9$
を得る.
0 件のコメント:
コメントを投稿