【GMAT数学基礎講座】最大公約数・最小公倍数

GMAT数学基礎コーナーでは、単元別のポイントを例題を交えてまとめていきます。

受験生のみなさまが効率良くポイントで復習できることを目指しています。

本コーナーは全部終了後書籍化予定です。今回は「最大公約数・最小公倍数」問題の解き方です。

最大公約数・最小公倍数問題の解説

1.2 最大公約数・最小公倍数(GCD/LCM) 最大公約数とは いくつかの整数に共通な約数を公約数(common divisor) と言い、 公約数の中で最も大きい数を最大公約数(greatest common divisor, GCD) と言う。 公約数は最大公約数の約数となる。 具体例 36 と54 の公約数、最大公約数を求める。 解法 36 = 22  32 54 = 2  33 (1.2) と素因数分解できる。 よって、36 と54 に共通する因数は2, 32 であるので、最大公約数は、以下のように18 と計算するこ とが出来る。 (最大公約数) = 2  32 = 18 (1.3) また、公約数は最大公約数の約数であるので、以下の18 の約数が公約数となる。 (公約数) = 1; 2; 3; 6; 9; 18 (1.4) 最小公倍数とは いくつかの整数に共通な倍数を公倍数(common multiple) と言い、 公倍数の中で最も小さい数を最小公倍数(least common multiple, LCM) と言う。 公倍数は最小公倍数の倍数となる。 具体例 6 と8 の公倍数、最小公倍数を求める。 解法 6 の倍数: 6; 12; 18; 24; 30; 36;    8 の倍数: 8; 16; 24; 32; 40; 48;    (1.5) と6 の倍数と8 の倍数を書き出すことが出来る。 よって、6 の倍数と8 の倍数に共通する最も小さい24 が最小公倍数となる。 また、公倍数は最小公倍数の倍数なので以下のようになる。 (公倍数) = 24; 48; 72; 96; 120; 144;    (1.6) 最大公約数・最小公倍数の求め方1 (連除法) 最大公約数・最小公倍数は以下のステップで求める。 1. 小さな素数から順に割っていき、商が互いに素となるまで割り算を続ける。 2. 左側の数字を掛け合わせたものが最大公約数、すべての数字を掛け合わせたものが最小 公倍数。 具体例 36 と54 の最大公約数・最小公倍数を求める。 解法 36, 54 を小さな素数から順に2; 3; 3 と割っていくことで、最大公約数は18、最小公倍数は108 と計 算することが出来る。 最大公約数の求め方2 (互除法) 2 つの自然数a; b の最大公約数を以下のステップで求める。a とb の両方を割り切る素数が無 い事に自信が持てない場合に威力を発揮。 1. a をb で割った時の余りをr とする。 2. r = 0 なら、b がa とb の最大公約数。 r ̸= 0 ならr をb に、b をa に置き換えて、1: に戻る。 具体例 884 と323 の最大公約数・最小公倍数を求める。 解法 互除法のステップによると、以下の様に最大公約数を17 と求める事が出来る。 884 = 323  2 + 238 323 = 238  1 + 85 238 = 85  2 + 68 85 = 68  1 + 17 68 = 17  4 (割り切れた!) (1.7) また、これを筆算で以下のように書くことが出来る。 最大公約数・最小公倍数の性質 2 つの自然数a; b の最大公約数をg、最小公倍数をℓ とすると以下の等式が成立する。 ab = gℓ (1.8) 解説 a; b の最大公約数・最小公倍数は連除法で以下のように書くことが出来る(a′ とb′ は互いに素)。 これより、明らかに、a′; b′ は、 a = ga ′ b = gb ′ (1.9) と書くことができる。すると、 ab = (ga ′ )(gb ′ ) = (g)  (g  a ′  b ′ ) | {z } ℓ = gℓ (1.10) が成立することが分かる。

最大公約数・最小公倍数の確認問題

最大公約数・最小公倍数-確認問題1  For each of the following, nd the greatest common divisor and least common multiple of x and y. (A) x = 48; y = 16 (B) x = 18; y = 24 (C) x = 30; y = 135 (D) x = 1; 829; y = 2; 077   1.2 最大公約数・最小公倍数(GCD/LCM) 17 最大公約数・最小公倍数-確認問題1  次の各選択肢において、x とy の最大公約数および最小公倍数を求めよ。 (A) x = 48; y = 16 (B) x = 18; y = 24 (C) x = 30; y = 135 (D) x = 1; 829; y = 2; 077   解説 (A)~(C) は、x とy を割ることが出来る素数を簡単に見つけることが出来そうなので連除法、(D) はx とy を割ることが出来る素数を簡単に見つけることが難しそうなので互除法で解いてみる。 この様に、互除法で最大公約数は31 であることが分かったので、連除法で最小公倍数も求めると以 下のようになる。

最大公約数・最小公倍数の実際のGMAT問題

最大公約数・最小公倍数-基礎問題1 (PS問題)  If x is the least common multiple of 27 and 36, and y is the greatest common divisor of 817 and 988, then x + y = (A) 73 (B) 109 (C) 127 (D) 325 (E) 343   1.2 最大公約数・最小公倍数(GCD/LCM) 19 最大公約数・最小公倍数-基礎問題1 (PS問題)  x が27 と36 の最小公倍数で、y が817 と988 の最大公約数であるとすると、x + y = (A) 73 (B) 109 (C) 127 (D) 325 (E) 343   ポイント 基礎事項のまとめにある「最大公約数・最小公倍数の求め方」を理解できているかどうかの確認。 解説 まず、27 と36 の最小公倍数を連除法を用いて求めると以下のようになる。 つまり、x = 108 と分かる。 次に、817 と988 の最大公約数を互除法を用いて求めると以下のようになる。 つまり、y = 19 と分かる。 よって、x + y = 108 + 19 = 127 となるので、答えは(C) となる。 最大公約数・最小公倍数-応用問題1 (PS問題)  If x and y are positive integers, and 1 is the greatest common divisor of x and y, what is the greatest common divisor of 3x and 5y? (A) Connot be determined  (B) 1 (C) 3 (D) 5 (E) 15   最大公約数・最小公倍数-応用問題1 (PS問題)  x とy は正の整数で、x とy の最大公約数が1 である時、3x と5y の最大公約数はいくらか? (A) 決まらない(B) 1 (C) 3 (D) 5 (E) 15   ポイント 最大公約数とは何かを理解できているかどうかの確認。 解説 x とy の最大公約数が1 であるとは、x とy が互いに素ということが条件ということだ。 連除法の過程より、3x と5y を割り切る共通の素数があるかどうかが問題となる。 例えば、y が3 であれば3x と5y は3 を公約数に持つが、x とy が互いに素という縛りしかないの で、(x; y) = (7; 3) とすると3x と5y の最大公約数は3 となる。 また、x が5 であれば3x と5y は5 を公約数に持つが、x とy が互いに素という縛りしかないので、 (x; y) = (5; 7) とすると3x と5y の最大公約数は5 となる。 与えられた条件のみでは、3x と5y の最大公約数を決められないので、答えは(A) となる。 最大公約数・最小公倍数-応用問題2 (DS問題)  If x and y are positive integers, what is the value of xy? (1) The greatest common factor of x and y is 15. (2) The least common multiple of x and y is 100.  最大公約数・最小公倍数-応用問題2 (DS問題)  x とy が正の整数である時、xy の値はいくらか? (1) x とy の最大公約数は15 である。 (2) x とy の最小公倍数は100 である。   ポイント 基礎事項のまとめにある「最大公約数・最小公倍数の性質」を理解できているかどうかの確認。 解説 (ステップ1) 質問文に条件(1) のみを加えて考えてみる。 与えられた条件を連除法で表すと整数x′; y′ を用いて以下のようになる。 すると、xy の値は以下の式のように定める事が出来る。 xy = (15x ′ )  (15y ′ ) = 152x ′ y ′ (1.11) ここで、x′ とy′ が互いに素という条件のみからx′y′ の値を決めることは出来ないので、xy の値は定まらない。よって、質問文に解答するのに、条件(1) のみでは不十分。 (ステップ2) 質問文に条件(2) のみを加えて考えてみる。 同様に与えられた条件を連除法で表すと整数x′; y′; g を用いて以下のようになる。 すると、xy の値は以下の式のように定める事が出来る。 xy = (gx ′ )  (gy ′ ) = g2x ′ y ′ = g(gx ′ y ′ ) = 100g (1.12) ここで、x′ とy′ が互いに素という条件のみからx′y′ の値やg の値を決めることは出来ないの で、xy の値は定まらない。よって、質問文に解答するのに、条件(2) のみでは不十分。 (ステップ3) 質問文に条件(1) と(2) を両方加えて考えてみる。 与えられた条件を連除法で表すと整数x′; y′ を用いて以下のようになる。 すると、xy の値は以下の式のように定める事が出来る。 xy = (15x ′ )  (15y ′ ) = 15  (15  x ′  y ′ ) = 15  100 = 1; 500 (1.13) よって、条件(1), (2) 両方が揃った場合、質問文に解答するのに十分であるといえる。 よって、答えは(C)。

 

最短3週間でGMAT数学50点の体験:無料ダウンロード

苦手分野判定&最適学習プランを提案する
オリジナル模擬試験問題全37問と
3週間で50点取れるテキストサンプル
ジェイマス講師Jより『51点取得者が語る!GMAT数学 高得点獲得のヒント』もメルマガで配信!

コメントを残す