高校数学A 互いに素な整数への分解—最大公約数で割った二数の共通因子を調べる｜武蔵野個別指導塾

最大公約数で割った商の関係を、連続整数の証明や積の割り切れ方に結びつけ、共通因子から互いに素を捉えます。

よくあるのは、高校生が「互いに素」と聞いて、2つの数がどちらも素数でなければならないと考える場面です。たとえば一方が合成数でも、その素因数がもう一方と共通しなければ、2つは互いに素です。数そのものの性質と、2つを比べたときの性質を区別すると、最大公約数で割る操作の意味も見えてきます。

数学Aの整数の学習範囲にある約数や倍数を用い、共通因子を取り除いた後の関係を調べます。ここでは正整数の組を中心に扱い、積が割り切れる条件の証明まで進みます。最大公約数と最小公倍数から元の組を逆算する問題には立ち入りません。

どの条件から始めるか

出方の1つは、与えられた2つの正整数を最大公約数で割り、商が互いに素であることを確かめる型です。計算結果を出すだけでなく、商に共通の約数が残っていると何が起こるかを説明します。元の2数にその約数を戻すことが、証明の鍵です。

もう1つは、連続する整数のように、2数の差がわかっている型です。共通の約数はそれぞれの差も割り切ります。差が1なら正の共通約数は1に限られますが、差が1以外なら、差の約数が候補に残ることに注意します。

3つ目は、積がある数で割り切れるとき、片方の因子がその数と互いに素であることを利用する型です。積を割り切ることだけから、勝手に片方を消すことはできません。どの2数が互いに素かを先に確認してから進みます。

共通因子を取り除くとは

正整数 a と b の最大公約数が1であるとき、a と b は互いに素といいます。素数は、1より大きい正整数で、正の約数が1と自分自身に限られる数です。素数という語は1つの数についての性質であり、互いに素は2つの数の組についての性質です。1は素数ではありませんが、1と任意の正整数は互いに素です。

図1のように、8と9はどちらも合成数ですが、共通する正の約数は1です。一方、8と14は共通の約数2を持つため、互いに素ではありません。どちらかが素数かどうかを調べるより、共通する約数を探すことが判定の目的に合っています。

図1の2組を比べると、合成数が含まれることと、共通の約数があることは別だとわかります。数が大きい場合には、素因数分解して共通の素因数があるかを調べても判定できます。1より大きい共通約数があれば、その約数には素因数があり、2数に共通するからです。

正整数 a、b の最大公約数を g とすると、g は両方の約数です。そこで正整数 u、v を使って次のように表せます。

a = gu
b = gv

このとき u と v は互いに素です。実際、もし u と v に1より大きい正の共通約数 d があれば、u = ds、v = dt と整数 s、t で表せます。すると a = gds、b = gdt ですから、gd は a と b の共通約数です。gd は g より大きく、g が最大公約数であることに反します。したがって共通約数は1に限られます。

逆向きも使えます。g、u、v が正整数で u と v が互いに素なら、gu と gv の最大公約数は g です。g は共通約数です。また、gu と gv の共通約数を素因数で調べると、u と v に共通する素因数はないので、共通部分は g の素因数の分を超えません。よって最大公約数は g です。共通因子を取り除く操作と、互いに素な組に同じ数を掛けて戻す操作は対応しています。

積の中から因子を取り出す

正整数 m、n が互いに素で、整数 k について m が nk を割り切るとします。このとき m は k を割り切ります。これはユークリッドの補題として使う関係です。条件を見落とさないよう、素因数に分けて理由を確かめます。

m の各素因数は n の素因数ではありません。nk が m の倍数になるには、m に必要な各素因数が必要な個数だけ積 nk に含まれますが、それらは n からは得られません。したがって必要な分はすべて k に含まれ、k は m の倍数です。k = 0 の場合も0は m の倍数なので成り立ち、k が負の場合は絶対値で同じように考えられます。

たとえば m と n が互いに素でなければ、この結論は使えません。m = 6、n = 3、k = 2 では nk は6で割り切れますが、k は6で割り切れません。共通因子が積の中で分担されるためです。割り切れるという結果だけを見て因子を消さず、互いに素という条件を明示します。

基本例題：共通部分を外して戻す

問題　正整数 56 と 75 のそれぞれを、最大公約数で割った商を求め、商が互いに素か答えてください。最大公約数と商は整数で答えてください。

まず素因数分解し、共通部分を調べます。

56 = 2³・7
75 = 3・5²

共通する素因数がないので、最大公約数は1です。したがって商は56と75です。両方とも合成数ですが、共通する素因数がないので互いに素です。最大公約数が1のとき、割っても数字が変わらない点が大切です。

図2のように、共通部分が1であることと、商の組が互いに素であることを対応させます。元の数に戻すと 1・56 = 56、1・75 = 75 です。商が元の条件に戻ることまで確かめられます。

図2では両方とも合成数であることにも注目してください。「互いに素だから素数」という判断では、この正しい組を除いてしまいます。最大公約数が1であるという定義へ戻れば、数そのものが素数かどうかを条件に加えずに済みます。

標準例題：共通の約数は差も割る

問題　n を0以上の整数とします。7n + 4 と 7n + 5 が互いに素であることを証明してください。

2つの数はどちらも正整数です。共通の正の約数を d とすると、整数 s、t を用いて次のように書けます。

7n + 4 = ds
7n + 5 = dt
(7n + 5) - (7n + 4) = dt - ds
1 = d(t - s)

したがって d は1を割り切る正整数なので、d = 1 です。1はもともと両方の約数ですから、最大公約数は1であり、2数は互いに素です。

たとえば n = 3 のとき、2数は25と26です。25と26の差は1であり、共通約数は1です。この代入は式の読み取りを確かめる例であって、任意の n についての証明は上の d を用いた説明が担っています。

差が2以上なら、同じ結論をそのまま出すことはできません。共通約数は差の約数に限られますが、1以外の候補を元の2数に戻して調べる必要があります。差の情報は候補を絞る道具であり、差が何であるかまで書いて初めて判定に使えます。

発展例題：積の割り切れ方を分解する

問題　a、b を正整数とし、最大公約数が7、a + b = 77 とします。さらに a が 28 の倍数であるとき、順序を区別して組 (a, b) をすべて整数で求めてください。

最大公約数で割った正整数を u、v とすると、先ほどの性質から u と v は互いに素です。

a = 7u
b = 7v
7u + 7v = 77
u + v = 11

また a が28の倍数なので、ある正整数 h を用いて次のように表せます。

7u = 28h
u = 4h

u と v は正で和が11ですから、u は11より小さい正の4の倍数です。候補は4と8です。それぞれ v = 11 − u に戻して確かめます。

u = 4 のとき v = 7
gcd(4, 7) = 1
u = 8 のとき v = 3
gcd(8, 3) = 1

どちらも互いに素なので、7を掛けて元の組を得ます。

(a, b) = (28, 49), (56, 21)

前者の和は77、後者の和も77です。a はそれぞれ28の倍数で、最大公約数はどちらも7です。u の範囲と4の倍数という条件から候補を尽くしたので、ほかの組はありません。和の条件だけで商の組を選ぶと、互いに素でない候補を含む場合があります。最後に最大公約数へ戻す確認が必要です。

誤答を直す：共通因子を残したまま消さない

整数 x について「6が 9x を割り切るなら、6が x を割り切る」とした答案を考えます。これは誤りです。x = 2 を代入すると 9x = 18 で6の倍数ですが、2は6の倍数ではありません。6と9は共通因子3を持つので、積の割り切れ方にユークリッドの補題をそのまま使えないことが原因です。

図3のように、まず両方に含まれる3を整理すると、条件は 6が9xを割ることから、2が3xを割ることに変わります。2と3は互いに素ですから、補題によって2は x を割り切ります。正しい結論は x が偶数ということです。

逆も確かめます。x = 2t と整数 t で書けるなら、9x = 18t = 6・3t なので、9x は6の倍数です。図3の整理後の条件は元の条件と同値です。必要な条件を求めた後、逆向きにも戻せるかを確かめると、答えの範囲が広すぎたり狭すぎたりする失敗を防げます。

自分で解く5問

次の問題の整数は、指定がなければ正整数です。答えは整数または指定された組で示してください。

1. 44 と 65 の最大公約数を求め、それで割った商の組と互いに素かどうかを答えてください。
2. n を0以上の整数とします。5n + 2 と 5n + 3 が互いに素であることを証明してください。
3. 正整数 a、b の最大公約数が5で、a = 35、b = 55 です。a = 5u、b = 5v としたときの整数 u、v を求め、互いに素か確かめてください。
4. 整数 x について、15が 10x を割り切るための必要十分条件を、x がある正整数の倍数であるという形で答えてください。
5. 正整数 a、b の最大公約数が3、a + b = 39 で、a は9の倍数です。順序を区別した組 (a, b) をすべて求めてください。

解答と考え方

1. 共通する素因数を調べる

44 = 2²・11
65 = 5・13

共通する素因数がないため、最大公約数は1、商の組は (44, 65) です。この商にも共通する素因数がないので互いに素です。1をそれぞれに掛けると元の44と65に戻ります。どちらも合成数であることは判定を妨げません。

2. 差が1であることを使う

共通の正の約数を d とすると、整数 s、t が存在して次が成り立ちます。

5n + 2 = ds
5n + 3 = dt
(5n + 3) - (5n + 2) = d(t - s)
1 = d(t - s)

正の約数 d は1に限られます。1は両方の約数なので最大公約数は1です。n が0以上なら2数は正であり、互いに素の定義を使えます。差の式は元の2つの式の引き算に戻して確認できます。

3. 最大公約数を掛けて戻す

u = 35 / 5 = 7
v = 55 / 5 = 11

7と11の最大公約数は1なので互いに素です。5・7 = 35、5・11 = 55 と元に戻り、35と55の最大公約数は5です。商を求める割り算と、元の条件を確かめる掛け算を対にします。

4. 共通因子を取り除く

15が10xを割り切ることは、整数 t があって次の式が成り立つことです。

10x = 15t
2x = 3t

よって3は2xを割り切ります。3と2は互いに素なので、3は x を割り切ります。逆に x = 3k と整数 k で表せれば、10x = 30k = 15・2k です。したがって必要十分条件は、x が3の倍数であることです。負の整数や0もこの形に含まれ、元の割り切れる条件に戻ります。

5. 商の候補を尽くす

最大公約数で割った正整数を u、v とすると、u と v は互いに素です。

a = 3u
b = 3v
3u + 3v = 39
u + v = 13

a が9の倍数なので u は3の倍数です。u は13より小さい正整数ですから、候補は3、6、9、12です。

(u, v) = (3, 10), (6, 7), (9, 4), (12, 1)

それぞれの最大公約数は1です。元の組は次の4組です。

(a, b) = (9, 30), (18, 21), (27, 12), (36, 3)

各組の和は39で、a は9の倍数です。各組の最大公約数は3であり、元の条件に戻ります。u の範囲の3の倍数をすべて調べたので、ほかの組はありません。

要点

最大公約数で2数を割ると、商は互いに素です。 互いに素は2数の関係であり、各数が素数である必要はありません。 共通約数は2数の差も割り切ります。 積から因子を取り出す前に、互いに素の条件を確かめます。

説明が止まったときの確認

商が互いに素である理由を聞かれたら、共通約数 d が残ると元の数に gd という共通約数ができる、と式で言えるかを確かめてみてください。単に「最大公約数で割ったから」と答えた場合は、d を仮定して元の2数へ掛け戻すところまで書くと、矛盾の位置が見えます。

個別指導では、差が1の場合と差が2の場合を並べ、共通約数がどちらを割るかを本人の言葉で説明してもらいます。積の問題では、どの2数の最大公約数が1かを指さして確認し、成り立たない例も代入します。条件と結論を結ぶ一歩が、互いに素の理解を支えます。