最小公倍数と最大公約数の問題をユークリッド互除法で解決!また、倍数の証明も解説【数学IA]

今回は「数学A」の整数の性質について語ります。

 

具体的には最大公約数と最小公倍数の問題を「ユークリッド互除法」という公式で解くだけでなく、倍数の証明についても行います。

 

また、最後に整数の性質についての大学入試の問題を解くことで知識をより高めることができます。

 

高校数学で整数の性質は、「ユークリッド互除法」などの公式が出てくるものの、新しい内容ではありませんが、特にセンター試験・二次試験のどちらにおいても、よく出題されます。

 

解法が独特で、この単元が得意になれば、試験において有利になること間違いなしです。例題を繰り返し練習して、きちんと理解しておきましょう。

 

この「整数の性質」の記事を読むとできること・最大公約数と最小公倍数の問題が解ける

・ユークリッド互除法がわかる

・倍数の証明がわかる

・倍数の問題について実際の入試問題を解ける

スポンサーリンク
スポンサーリンク

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

はじめに、最大公約数・最小公倍数の問題を解いてみます。最大公約数・最小公倍数については、小学校で習った内容から変わりはありませんが、扱う数字が大きくなったり文字になったりする分、難しくなります。

 

例題(1) \(12, 36, 60\) の最大公約数・最小公倍数を求めよ。
(2) \(2\) つの正の整数が\(m, n\) があり、最大公約数は\(5\)、また、\(mn=300\) である。\(m, n\) を求めよ。
(3) \(3103\) と\(4387\) の最大公約数を求めよ。

(1) 最初は復習を兼ねて、定義を思い出すための問題です。

 

まず、それぞれの数を因数分解します。
\(12=2^2\times3\)
\(36=2^2\times3^2\)
\(60=2^2\times3\times5\)

最大公約数:\(2^2\times3=12\)
最小公倍数:\(2^2\times3^2\times5=180\)

(2) 高校数学らしく、難易度が上がりました。
\(m, n\) についてどう表すかが重要なポイントです。

 

最大公約数が\(5\) なので、\(m=5m’, n=5n’\) とおく。(\(m’, n’\) は互いに素で、\(m’>n’\) を満たす正の整数。)

ここで、最小公倍数を\(l\) とおくと、\(mn=5l\) が成り立つので、\(l=60\) …①

よって、\(60=5m’n’\) これより、\(m’n’=12\)
\(m’>n’\) であり、\(m’, n’\) は互いに素なので、
\((m’, n’)=(12, 1), (4, 3)\)

 

\((m, n)=(60, 5), (20, 15)\)

説明文中、①の部分、疑問に思う人もいると思うので、もう少し詳しく解説します。

 

初めに、\(m=5m’, n=5n’\) とおきました。\(m’, n’\) は互いに素なので、公約数はありません。

 

ということは、\(m, n\) の最小公倍数\(l\) は、\(l=5m’n’\) と表されます。

 

よって、\(mn=5m’\times5n’=5^2m’n’=5l\) となり、最終的に\(m’, n’\) が求められます。

 

(3) 扱う数字が大きくなりました。(1)と同じように一つ一つ素因数分解することも可能ですが、時間がかかりすぎます。こういったときに使うのが、ユークリッドの互除法です。

 

この方法は、簡単に説明すると、

ユークリッドの互除法「\(a\) を\(b\) で割ったときの商を\(q\)、余りを\(r(\neq0)\) とすると、\(a=bq+r\) と表すことができ、\(a\) と\(b\) の最大公約数は、\(b\) と\(r\) の最大公約数に等しい」

というものです。

 

たなか君
たなか君
わからん!!

 

このユークリッドの互除法を簡単な数字を使って説明します。

 

例えば、\(56\) と\(126\) の最大公約数を求めてみます。

 

\(126\) を\(56\) で割ると、\(126=56\times2+14\) …②と表せます。

 

ここで、\(126\) と\(56\) の最大公約数を\(g\) とすると、

 

\(126=ag, 56=bg\) …③(\(a, b\) は互いに素)

と表せるので、

 

②と代入すると、\((a-2b)g=14\)

 

これを\(14=cg\) と表すと、\(b\) と\(c\) は互いに素であり(※)、③と合わせて考えると、\(g\) は\(56\) と\(14\) の最大公約数といえます。

 

これと同じことをもう一度繰り返すと、\(56=14\times4+0\) となり、余りが\(0\) になったときの割る数\(14\) が最大公約数となります。

 

※の部分、\(b\) と\(c\) がなぜ互いで素であるといえるかの証明は、背理法を使います。

 

\(a\) と\(b\) が互いに素であるとき、\(b\) と\(a-2b\) が互いに素でないとする。

 

つまり、\(b\) と\(2a-b\) が\(2\) 以上の自然数\(p\) を約数にもつとすると、\(b=mp, a-2b=np\) (\(m, n\) は整数)と表せる。

 

\(a-2b=np\) を変形すると、\(a=2b+np=(2m+n)p\) となり、\(a\) も\(b\) も共通の約数\(p\) をもつことになり、互いに素ではない。

 

よって、\(a\) と\(b\) が互いに素であることに矛盾するので、\(b\) と\(a-2b\) は互いに素である。

 

…と、少し長くなりましたが、ここまでユークリッドの互除法について説明しました。

 

では例題(3)の解法です。

$
\begin{array}{rcll}
5593\div3689&=&1+1904\\
3689\div1904&=&1+1785\\
1904\div1785&=&1+119\\
1785\div119&=&15
\end{array}
$

 

最大公約数は\(119\)

頭の中が???でいっぱいになった人は、もう一度読み直してみましょう。

 

特に、一つ一つ値を確認しながら読むのが大事です。それでも解消されない場合は、他の問題を解いたりして少し時間をあけてから、改めて読んでみるのがいいです。

倍数の証明について

文字を含む数式で表された値が、ある整数の倍数であることを証明する問題も、よく出されています。例題を見てみましょう。

例題\(n\) を整数とするとき、\(n^3+3n^2-4n\) は\(6\) の倍数であることを示せ。

問題文はとってもシンプルです。でもどこから取り掛かればいいのかわかりにくい問題です。

 

こういった問題は、積の形に直して、その中に\(6\) あるいは\(2\) と\(3\) が含まれていることを示して証明します。

 

まず、因数分解です。

$
\begin{array}{rcll}
n^3+3n^2-4n&=&n(n-1)(n+4)\\
&=&(n-1)n\left\{(n+1)+3\right\}\hspace{5mm}&\cdots(1)\\
&=&(n-1)n(n+1)+3n(n-1)
\end{array}
$

ここで、\((n-1)n(n+1)\) は連続する\(3\) つの整数の積なので、\(3\) つのうち必ず\(1\) つは\(2\) の倍数であり、\(1\) つは\(3\) の倍数である。

 

よって、\((n-1)n(n+1)\) は\(6\) の倍数である。

 

また、\(3n(n-1)\) は連続する\(2\) つの整数の積であり、\(2\) つのうち\(1\) つは必ず\(2\) の倍数なので、\(3n(n-1)\) は\(6\) の倍数である。

 

以上より、\((n-1)n(n+1)+3n(n-1)\) すなわち\(n^3+3n^2-4n\) は\(6\) の倍数である。

 

連続する\(n\) 個の整数については、扱い方をおさえておくと便利です。

 

複数個あれば、必ず偶数(\(=2\) の倍数)が含まれます。連続した\(3\) 個の整数であれば、必ず\(1\) つ\(3\) の倍数が含まれますし、連続した\(5\) 個の整数であれば、必ず\(1\) つ\(5\) の倍数が含まれます。

 

わかりにくければ、実際の数字を入れてみて考えると、考えやすくなります。

 

また、(1)の部分の式変形ですが、「連続する\(3\) つの整数の積」の部分を作るために、\(4\) を強引に\(1\) と\(3\) に分けて\(n+1\) という部分を作っています。

 

上のような、「ある値が、ある整数の倍数である」ことを示す証明問題以外にも、「ある整数を\(p\) で割った余りに着目して分類して」いろんなことを証明する剰余系といわれる問題もよく出されます。

例題で練習してみましょう。

例題整数\(a\) の平方は\(4\) で割ると、割り切れるか\(1\) 余るかのどちらかであることを示せ。

こちらもとてもシンプルな問題です。

 

まず、問題に取り掛かるときに何をするべきかを考えます。

 

問題文中に「ある整数の平方\(4\) で割るとき」とあるので、ある整数\(a\) を\(2\) の倍数とそれ以外というときに分類することを考えます。

 

つまり、\(a=2n\) である場合と\(a=2n+1\) である場合(\(n\) は整数)に分けて考えます。

 

\(a=2n\) であるとき

\(a^2=4n^2\) であり、\(4\) で割り切れる。

 

次に\(a=2n+1\) であるとき

$
\begin{array}{rcll}
a^2&=&(2n+1)^2\\
&=&4n^2+4n+1\\
&=&4n(n+1)+1
\end{array}
$

このとき、\(a^2\) は\(4\) で割ると\(1\) 余る。

 

よって、整数\(a\) の平方は\(4\) で割ると、割り切れるか\(1\) 余る。

 

過去問を解いてみましょう!

それでは、過去問でさらに練習をしてみます。

例題

\(p\) は奇数である素数とし、\(N=(p+1)(p+3)(p+5)\)とおく。
(1) \(N\) は\(48\) の倍数であることを示せ。
(2) \(N\) が\(144\) の倍数になるような\(p\) の値を、小さい順に\(5\) つ求めよ。
[2014 千葉大学 教育学部 第3問]

(1) まずは、\(p\) の「奇数である素数」という条件を、他の文字で表します。

 

ただ、素数を文字で表すのは難しいので、一旦「奇数である」ことだけを表して進めます。

 

\(p\) は奇数なので、\(p=2k+1\)(\(k\) は自然数)とおく。

$
\begin{array}{rcll}
N&=&(2k+2)(2k+4)(2k+6)\\
&=&2^3(k+1)(k+2)(k+3)
\end{array}
$

連続する\(3\) つの整数は、少なくとも\(1\) つの偶数を含み、\(1\) つの\(3\) の倍数を含む。

 

よって、連続する\(3\) つの整数の積は\(6\) の倍数である。

 

よって、\(N\) は\(2^3\times6\)、つまり\(48\) の倍数である。

 

ここでも、連続する\(n\) 個の整数が出てきました。

 

この問題は、奇数であることを他の文字を使って表すことができれば、それほど難しくありませんでしたね。

 

(2) \(N\) と右辺の最小公倍数が\(144\) ということです。

 

\(N\) が\(144\) の倍数となるので、\(N=144m\) (\(m\) は自然数)と表せる。

 

$
\begin{array}{rcll}
N&=&2^3(k+1)(k+2)(k+3)\\
144m&=&2^3(k+1)(k+2)(k+3)\\
18m&=&(k+1)(k+2)(k+3)\\
2\times3^2m&=&(k+1)(k+2)(k+3)
\end{array}
$

右辺は連続する\(3\) つの整数の積なので、少なくとも\(1\) つは偶数を含む。

 

よって、上の式が成り立つためには、\((k+1)(k+2)(k+3)\) の部分が\(9\) の倍数であるときである。

 

連続する\(3\) つの整数には、\(3\) の倍数は\(1\) つしか含まれないので、\(k+1, k+2, k+3\) のうち\(1\) つのみが\(9\) の倍数になるときを考える。

 

  • \(k+3=9\) のとき \(k=6\) このとき\(p=13\)  \(13\) は素数である。
  • \(k+2=9\) のとき \(k=7\) このとき\(p=15\) \(15\) は素数でないので不適。
  • \(k+1=9\) のとき \(k=8\) このとき\(p=17\) \(17\) は素数である。
  • \(k+3=18\) のとき \(k=15\) このとき\(p=31\)  \(31\) は素数である。
  • \(k+2=18\) のとき \(k=16\) このとき\(p=33\) \(33\) は素数でないので不適。
  • \(k+1=18\) のとき \(k=17\) このとき\(p=35\) \(35\) は素数でないので不適。
  • \(k+3=27\) のとき \(k=24\) このとき\(p=49\)  \(49\) は素数でないので不適。
  • \(k+2=27\) のとき \(k=25\) このとき\(p=51\) \(51\) は素数でないので不適。
  • \(k+1=27\) のとき \(k=26\) このとき\(p=53\) \(53\) は素数である。
  • \(k+3=36\) のとき \(k=33\) このとき\(p=67\) \(67\) は素数である。

 

\(p=13, 17, 31, 53, 67\)

 

今回のまとめ

今回は、整数の性質について説明しました。特に、ある値に関する条件(奇数/偶数、〇の倍数である/ない など)を文字を使って表して解く問題に特化して説明しました。

 

整数の性質は、センター試験・二次試験のどちらでもよく出題されています。ただ、問題のパターンが多く、毎回同じ解法で解けるというものでもないのがとてもやっかいです。

 

確実にできることは、いろんなパターンの問題に触れて、いろんなアイデアを持っておくことです。また、触れた問題が多くなれば多くなるほど、解法の糸口を見つける勘のような、解法を見通す力は鋭くなります。やはり、練習あるのみ!ですね。

 

前回の記事:「【数学IA】データの相関を初学者でも理解できる方法(データの分析の過去問解説も)

度数分布表とヒストグラム(データの整理)の問題を解ける!【数学IA】
みなさん、こんにちは。数学IAのコーナーです。今回は、数学IAの中で「データの分析」のテーマの前半部分、データの整理について説明します。具体的には度数分布表とヒストグラムについて解説を加えていきます。 何をしているのかよくわからない…となり...
スポンサーリンク
スポンサーリンク

コメント

タイトルとURLをコピーしました