高校数学の窓LaTeX版: 質問＜３７２２＞２００８／５／１４　from=ぴぴ　「代数学」

ユークリット互除法を使って、（６１８８　４７０９）の最大公約数は、１７と出来ました。
　次の
（６１８８，４７０９）＝６１８８λ+４７０９μ
となるλ　μ　を見つけよ。
この意味が分かりません。解答を教えてください。

★希望★完全解答★

僕も意味が分かりません(笑)。さて、どうしたものか。

と言うより、恐らくもう記述がダメダメですね。問題文は本当にこの通りでしたか?
通常は、数値x, yがあって、(x, y)と記述されたりする場合、これは単にベクトルを表すんで、上の

（６１８８，４７０９）＝６１８８λ+４７０９μ

なんて書かれた暁にゃあ、手も足も出ないですね。何を言ってるんだかチンプンカンプンです。
まあ、僕が知らない記述法があるのかもしれませんが、ちょっと「おかしな記述の」問題のような気がします。出版元に問い合わせた方が良いと思います。

とは言っても、まあ、恐らくこう言う意味だろう、ってのは類推出来たんで、問題文を次のように読み替えてみます。

$gcd(6188,4709)$

$gcd(6188,4709)=6188\lambda + 4709\mu$

$\lambda$

$\mu$

なお、ユークリットじゃなくってユークリッドですね。この辺から既にこの問題は提示されたままだとかなり怪しいです(笑)。英語ではEuclidですが、ギリシャ文字だとΕυκλείδηςですね。読めませんが(笑)。

さて、ユークリッドの互除法と言うアルゴリズムはgcd(Greatest Common Diviser=最大公約数の事)を求める手法で、結局それが表す大変地味な計算過程を書き直せば、次のようになってるのが分かるでしょう。

$6188=1\times 4709+1479$

$4709=3\times 1479+272$

$1479=5\times 272+119$

$272=2\times 119+34$

$119=3\times 34+17$

$34=17\times 2$

最後で出てくる17が $gcd(6188,4709)$ なんですから、5番から逆に辿っていってみると、まずは5番は

$119=3\times 34+gcd(6188,4709)$

$\therefore 119-3\times 34=gcd(6188, 4709)\dots (1)$

と書き表されて、そこに入ってる３４と言う数は４番のステップより、

$34=272-2\times 119\dots (2)$

なんでこれを(1)に代入して、

$119-3\times (272-2\times 119)=gcd(6188, 4709)\dots (1)^{\prime}$

次に、３番のステップより、

$119=1479-5\times 272\dots (3)$

なんで、これを $(1)^{\prime}$ に代入すると、

$(1479-5\times 272)-3\times \left{ 272-2\times (1479-5\times 272)\right} = gcd(6188, 4709)\dots (1)^{\prime\prime}$

同様に、２番のステップより、

$272=4709-3\times 1479\dots (4)$

なので、これを $(1)^{\prime\prime}$ に代入すると、

$\left{ 1479-5\times (4709-3\times 1479)\right}$

$-3\times \left[ (4709-3\times 1479)-2\times \left{ 1479-5\times (4709-3\times 1479)\right} \right]$

$=gcd(6188, 4709)\dots (1)^{\prime\prime\prime}$

最後に1番のステップより、

$1479=6188-4709\dots (5)$

なんで、これを $(1)^{\prime\prime\prime}$ に代入すると、

$\left[ (6188-4709)-5\times \left{ 4709 -3\times (6188-4709)\right} \right]$
$-3\times \left< \left{ 4709-3\times (6188-4709)\right} -2\times \left[ (6188-4709)-5\times \left{ 4709-3\times (6188-4709)\right} \right] \right>$
$=gcd(6188, 4709)\dots (1)^{\prime\prime\prime\prime}$

ここで、さすがに見づらいので(笑)、 $x=6188$ 、 $y=4709$ とすると、 $(1)^{\prime\prime\prime\prime}$ は

$gcd(x,y)=\left[ (x-y)-5\left{ y-3(x-y)\right}\right]$

$-3\left< \left{ y-3(x-y)\right} -2\left[ (x-y)-5\left{ y-3(x-y)\right} \right] \right>$

となり、これを整理すると、

$gcd(x,y)=121\,x-159\,y$

つまり、

$gcd(6188, 4709)=121\times 6188-159\times 4709$

$\therefore \lambda = 121, \mu = -159$

になる、って意味でしょうね。

以上です。

ユークリッドの互除法

高校数学の窓LaTeX版

高校数学の窓過去問検索

質問＜３７２２＞２００８／５／１４　from=ぴぴ　「代数学」

0 コメント:

New

分類

ツール

数学ガール

たけしのコマ大数学科

ガスコン研究所

数学系ブログ記事