最大公約数の例

問題は，「20 と 40 の最大公約数 は何ですか?」と聞いています。 これを言う他の方法は， 「gcd(20,40)?」です。 gcd は英語の最大公約数の 頭文字をとったものです。 「最小公倍数」と同じように， これも漢字で書くと長いので このように英語の頭文字で 短く書くことが多いです。 G は Greatest の G， 「最大の」という意味です。 C は Common の C で，「公の」， とか，「共通の」という意味で，そして， D は Divisor の Dで 「約数」という意味です。 略して GCD と書きます。 この意味は最大公約数です。 日本の学校でもこの略を使うことが 多いので説明しておきます。 「最大公約数」とはとても風変りに 聞こえる言葉ですけれども それは単に 20 と 40 の 両方を割ることができる 一番大きな数は何ですか? と聞いているだけです。 この問題は簡単ですね。 なぜなら 20 は 40 を 割り切るからです。 40 は 20 で余りなしで 割れると言うこともできます。 ですから，20 と 40 の因数， あるいは約数，のうち， 最大の数というのは， 実は 20 です。 20 = 20 × 1 で, そして 40 = 20 × 2 です。 この状況では，紙を取り出す 必要もないですね。 単に 20 と答えを書けばいいです。 あってますね。 ではもう少し他の 問題を解きましょう。 「10 と 7 の最大公約数は何 ですか?」と問題は聞いています。 これは紙を使って考えます。 10 と 7 の最大公約数です。 まずは 10 と 7 を書いておきます。 最大公約数，GCD， これの， 10 と 7 の，…これはがいくつで しょうかというのが問題です。 この問題を解くには 2 つの 方法があります。 1 つ目の方法は，全ての因数， これは素因数ではなくて， 普通の因数全部を 文字通り並べる方法です。 これらの数のそれぞれの 普通の因数をまず並べます。 そしてどれが最大か，いや， 単に最大ではなくて， 両方の数が共通して持って いる因数のうちで 最大のものはどれかをみつけます。 そうですね，まずは 10 があります。 10 があります。 10 の約数は何かと いうと，それは 2 と… ちょっと気をつけます。 1 と 10 が最初です。 次は 2 と 5 です。 2 × 5 は 10 です。 1, 2, 5, 10, これらは皆 10 の因数です。 これらが全て，これらを10 の 「約数」と言うことができます。 7，この因数はなんでしょうか? 7 は 素数です。ですから 1 と 7 の 2 つしか因数，約数はありません。 では何が最大公約数ですか? ここには 1 だけしか 公約数がないです。 1 がたった 1 つの公約数です。 ですから，10 と 7 の最大 公約数は 1 に等しいです。 これを書いておきましょう。 はい，あっています。 他の問題もやってみましょう。 21 と 30 の最大公約数は何ですか? ここにあるのが他の書き方です。 21 と 30 の 2 つの数， それを考えてみましょう。 最大公約数，gcd， この 21 と 30… これにも 2 つの方法があります。 1 つは先程の方法のように， 文字通り全部書いてみます。 21 の因数は，1 と 21， そして 3 × 7 も因数です。 これで全部でしょう。 30 は，… まずは 1 があります。 1 と 30，そして 2 と 15， そして 3 と… これでは 書く場所がないです。 もう一回書き直します。 1 と 30， 2 と 15， 3 と 10，そして 5 と 6 があります。 これが 30 の約数全部です。 では，共通の約数は何ですか? そうですね，1 は公約数です。 3 も公約数です。 でも，最大の公約数は何ですか? それは 3 ですね。これは 3 と書いておきましょう。 これは 3 です。 これまで，2 つの方法があると 何度も言ってきていますので， もう 1 つの方法もお見せしましょう。 それは素因数分解を使う方法です。 21 の素因数分解は 3 と 7 です。 3 × 7 = 21 です。 30 の素因数分解は 何かというと，それは… 3 と 10， 3 × 10 = 30 で， 10 は 2 × 5 です。 では，21 と 30 の両方から とってくることができて， 可能な限り大きな数を作るための 最大の因数，約数，は何ですか? 素因数分解を見ると， ここにあるもので共通して いるものは 3 だけです。 ですから 21 と 30 の 最大公約数は 3 です。 もしここにあるものに共通する ものが何もない場合は， 最大公約数は 1 ですと 言うことができます。 これで最小公約数のビデオが ない理由もわかりますね。 最小公約数はいつも 1 なので， 特にビデオを作ることもありません。 ではもう1つ面白い問題を やってみましょう。 この感覚をつかんで 欲しいと思います。 その数は 21 と 30 では ないことにしましょう。 そうですね。gcd，最大公約数の 105 と 30 にしましょう。 素因数分解をしたら，今度はもう 少しはっきりするのではないでしょうか。 実際に，「105 の全ての 因数は何だい?」 という質問に答えるのは ちょっと大変です。 105 の素因数分解をしてみますね。 105 の素因数分解は， 5 × 21，21 は 3 × 7 です。 105 の素因数分解は，小さいもの から書くと，3 × 5 × 7 です。 30 の素因数分解は，やりました からもうわかっていますね。 30 は 2 × 3 × 5 に等しいです。 これらの数が両方とも持っている 素数は何でしょうか? これらの 2 つの数は両方とも 3 を 1 つと 5 を 1 つ持っています。 ですから最大の共通の因数， あるいは最大公約数というのは このかけ算になります。 この場合，gcd,最大公約数， 105 と 30 の最大公約数は 3 × 5 = 15 になります。 どちらの方法でもできます。 何というか，昔ながらの方法では 因数を全部書き出して， 両方にある共通のもので 最大のものをみつけます。 あるいは 2 つの数のコアに なっている共通の基盤， これは素因数分解のことですが， そこから共通する素数の組で 最大になるものをみつけます。 そしてそれらのかけ算が 最大の公約数です。 それが両方の数を割ることのできる 最大の数になります。 素数の操作がちょっと 見えてきましたか?