問1
を で割ったときの商と余りを求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
商 、余り （）
自己採点：
記録を読み込み中…
目次 ／ 整数の性質 ／ 数学A
第2章 ユークリッドの互除法
—— 割り算をくり返すだけで、最大公約数にたどり着く ——
第1章では素因数分解を使って最大公約数を求めましたが、大きな数では素因数を見つけるだけで一苦労です。この章では、まず割り算の商と余りを等式 $a = bq + r$ で表し、「$a$ と $b$ の最大公約数は、$b$ と余り $r$ の最大公約数に等しい」という性質を学びます。この性質をくり返し使うのが、2000年以上前から伝わる「ユークリッドの互除法」です。最後に、$n + 5$ と $2n + 3$ のように文字を含む式の最大公約数も、同じ考え方で求めます。
割り算の等式
第1章では、素因数分解を使って最大公約数を求めました。けれども と のような数だと、素因数を見つけるまでの試し割りがなかなか大変です。この章では、割り算をくり返すだけで最大公約数にたどり着く方法を学びます。まずは、その材料になる割り算を式で表すところから始めます。
公式1：割り算の等式
整数 と自然数 に対して
を満たす整数 ， がただ1組定まる。 を を で割ったときの商、 を余りという。 のとき、 は で割り切れる。
小学校で習った「 余り 」を式で書くと、 です。大切なのは、余りの範囲 です。 も等式としては正しいのですが、 は 以上なので、まだ をもう1回取れます。これは余りとは呼びません。この範囲の約束があるおかげで、商と余りがただ1組に決まります（厳密定義 定理1）。
割られる数 が負のときも、余りは 以上にそろえます。たとえば を で割ると
で、商は 、余りは です。 と書くと余りが負になってしまうので、この形は使いません。数直線に の倍数の目盛りを打って考えると分かりやすくなります。 以下にある目盛りのうち にいちばん近いものが で、そこから までの距離が余り です。 の左隣の目盛りは なので、余りは となります。
人の団体が、 人乗りのバスに乗り込む場面を考えます。 台を満席にすると 人が残るので、 です。もし残りが 人以上いたら、もう 台を満席にできます。だから「満席のバスの台数」を決めきったときの残りは、必ず 人以上 人以下になります。余りの範囲 は、「満席のバスをこれ以上増やせない」ということを表しているのです。
を で割るとは、 の形に、余り が 以上 未満になるように書き表すことだということです。
例題1：割り算の等式
(1) を で割ったときの商と余りを求めなさい。
(2) を割ると 余り、 を割ると 余る自然数をすべて求めなさい。
【解答】
(1) なので、 です。これでは余りが負なので、 をもう つ分引いて調整します。
なので、 です。
(2) 求める自然数を とします。 を で割ると 余るので、 は で割り切れます。同じように も で割り切れます。つまり は と の公約数です。
， より最大公約数は で、正の公約数はその約数の ，，，，， です。さらに、余りは割る数より小さいので でなければなりません。よって
です。たとえば ， となっています。 を入れてしまうと、 は で割り切れて余りが になるので、条件に合いません。
互除法の原理
第1章の実践問題 j19 では、「公約数は、2数を何倍かして足したり引いたりした数も割り切る」ことを使って、数を小さくしながら最大公約数を調べました。これを割り算の等式と組み合わせたのが、次の性質です。
公式2：互除法の原理
自然数 ， について、 を で割った余りを とする（）。このとき
と の最大公約数は、 と の最大公約数に等しい。
のときは、 と の最大公約数を と考える。
なぜ最大公約数が変わらないのでしょうか。理由は、公約数の顔ぶれがまったく同じだからです。
- が と の公約数なら、，（， は整数）と書けます。すると なので、 は も割り切ります。つまり は と の公約数です。
- 逆に が と の公約数なら、 も で割り切れるので、 は と の公約数です。
公約数の集まりが同じなら、その中で最大のものも同じです。たとえば で、 と の正の公約数も、 と の正の公約数も、どちらも ，，， です。 の場合は、 がどんな整数の倍数でもあることから、 と の公約数は の約数そのもので、最大のものは になります。
この理由の中では、 が「 以上 未満」であることを一度も使っていません。 という等式さえ成り立っていれば、 が本当の商でなくても、 が負の数でも、同じ結論が成り立ちます。この見方は、例題2と公式4で役に立ちます。
目盛りのない棒を1本持っていて、長さ の棒と長さ の棒を、どちらもちょうど何本分かで測りきれるとします。長いほうの棒から長さ を 回切り取った残り も、この棒でちょうど測れます。測れる長さから測れる長さを取り除いただけだからです。逆に と を測れる棒なら、それらをつないだ も測れます。「 と を測れる棒」と「 と を測れる棒」は同じ顔ぶれで、いちばん長いものも同じです。ユークリッドの『原論』でも、最大公約数は「最大の共通の尺度」として、まさにこの棒のことばで書かれています。
を で割った余りを とすると、， の公約数と ， の公約数は同じ顔ぶれになるので、最大公約数は小さいほうの組で求めてよいということです。
例題2：互除法の原理を使った証明
(1) を自然数とする。 と は互いに素であることを示しなさい。
(2) 自然数 ， が互いに素ならば、 と も互いに素であることを示しなさい。
【解答】
(1) なので、公式2より
です。よって と は互いに素です。（証明終）
のときは を で割った本当の余りは ですが、公式2のあとで確かめたとおり、等式 が成り立っていれば結論は変わりません。
(2) なので
です。よって と は互いに素です。（証明終）
(1) は「連続する2つの整数は必ず互いに素」ということです。ここでも、 が より大きいとは限らないので は本当の余りとは限りませんが、等式があれば公式2の理由がそのまま通用します。
ユークリッドの互除法
公式3：ユークリッドの互除法
2つの自然数 ，（）の最大公約数は、次の手順で求められる。
- を で割った余り を求める。
- なら、 が最大公約数である。 なら、 を に、 を におきかえて 1 にもどる。
余りが になったときの割る数が、最大公約数である。この方法をユークリッドの互除法という。
と で試してみます。
余りが になったときの割る数は なので、最大公約数は です。公式2を1行ごとに使うと
と、最大公約数を変えないまま組が小さくなっていき、最後の と の最大公約数が だ、というしくみです。割った数と余りが互いに入れかわりながら進むので「互除法」と呼ばれます。余りは必ず割る数より小さいので、割る数はどんどん小さくなり、いつかは必ず余りが になって終わります（厳密定義 定理3）。
この手順は、長方形の図で見ることもできます。
縦 、横 の長方形から、短い辺を1辺とする正方形をできるだけ多く切り取ります。1辺 の正方形が 枚取れて、縦 、横 の長方形が残ります。今度はそこから1辺 の正方形が 枚取れて、縦 、横 が残ります。最後に1辺 の正方形が 枚で、ちょうど残りなく切り取れます。切り取った枚数 ，， は互除法の商、残った長方形の辺 ， は余りです。最後の正方形の1辺 が最大公約数で、元の長方形は1辺 の正方形ですき間なく埋めつくせます。第1章の実践問題 j07 で「最大公約数を1辺とする正方形」を扱いましたが、互除法を使えば、その正方形を素因数分解なしで見つけられるわけです。
長方形のコピー用紙から折り紙用の正方形を作るときは、短い辺を長い辺に重ねるように斜めに折り、はみ出した細長い部分を切り落とします。その細長い紙からも、同じように正方形を折り取れます。これをくり返して、最後に細長い部分が残らなくなったときの正方形が、元の紙を同じ大きさの正方形で余りなく分けられる最大の大きさです。互除法は、この「正方形を折り取っては残りに移る」作業を、数の上で行っているのです。
互除法は、大きい数を小さい数で割って、割った数と余りの組に移ることを余りが になるまでくり返す方法で、最後の割る数が最大公約数だということです。
例題3：互除法で最大公約数を求める
(1) と の最大公約数を求めなさい。
(2) 分数 を約分した分数を求めなさい。
(3) と の最小公倍数を求めなさい。
【解答】
(1) 互除法を行います。
余りが になったときの割る数は なので、最大公約数は です。
(2) 分母と分子を最大公約数 で割ります。， なので
最大公約数で割ったので、 と は互いに素で、これ以上は約分できません。
(3) 第1章 公式6の を使います。
や が で割り切れることに試し割りで気づくのは大変ですが、互除法なら割り算5回で最大公約数が分かり、そこから最小公倍数も求められます。
文字を含む式の最大公約数
公式4：式を使った互除法
整数 ，， について
と の最大公約数は、 と の最大公約数に等しい。
， が文字 を含む式のときも、これをくり返して を消していけば、最大公約数を定数の約数にまでしぼりこめる。
理由は公式2と同じです。 が と の公約数なら も割り切り、 が と の公約数なら も割り切ります。 は好きな整数でよく、 が負になってもかまいません（符号を変えても約数は変わりません）。
を自然数として、 と の最大公約数を調べてみます。 の値が分からないので数の割り算はできませんが、 を消すように引き算することはできます。
なので、公式4より
です。 の正の約数は と だけなので、最大公約数は が の倍数なら 、そうでなければ です。表で確かめると、確かにそうなっています。
| 最大公約数 |
「4人分」と書かれたレシピは、4人で食べるときにしかそのまま使えません。けれども材料を「 人分なら小麦粉 グラム」のように人数の式で書いておけば、何人のときでも同じ手順で作れます。式を使った互除法もこれと同じで、数の代わりに の式のまま計算を進めておけば、1回の計算で、どの にも通用する答えが手に入ります。
一方から他方の何倍かを引いても最大公約数は変わらないので、 の式どうしでも を消すように引き算を重ねれば、最大公約数を定数の約数にしぼりこめるということです。
例題4： の式の最大公約数
を自然数とする。
(1) と は互いに素であることを示しなさい。
(2) と の最大公約数が となるような、 以下の自然数 の個数を求めなさい。
【解答】
(1) 公式4を使って、大きいほうから小さいほうを引いていきます。
最大公約数は各段で変わらないので、 と の最大公約数は、最後の と の最大公約数 に等しくなります。よって2数は互いに素です。（証明終）
第1章の実践問題 j19 のように、 と一気に を作る方法もあります。互除法の流れで引き算を重ねると、その係数 と を探し当てなくても、自然に にたどり着けます。
(2) を消すように引くと
なので、最大公約数は と の最大公約数に等しくなります。 は素数なので、これは が の倍数なら 、そうでなければ です。
（ は自然数）とすると で、 より 、つまり です。 の
です。たとえば なら ， で、最大公約数は です。
この章では、割り算をくり返すだけで最大公約数が求められることを学びました。互除法の割り算の式を下から逆にたどると、 のように、最大公約数を「」の形に書き表すこともできます（厳密定義 定理4）。次の第3章では、この性質を使って、 のような方程式の整数解を見つけます。
基礎確認問題（全5問）
まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。
問2
を で割ったときの商と余りを求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
商 、余り （）
自己採点：
記録を読み込み中…
問3
互除法を用いて、 と の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（，，）
自己採点：
記録を読み込み中…
問4
互除法を用いて、 と の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（，，，）
自己採点：
記録を読み込み中…
問5
分数 を約分した分数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（互除法で最大公約数は ：，，）
自己採点：
記録を読み込み中…
実践問題（全20問）
難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。
問1 ★
(1) を で割ったときの商と余りを求めなさい。
(2) を で割ったときの商と余りを求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) 商 、余り (2) 商 、余り
解説
(1) なので
なので、 です。
(2) (1) より ですが、余りが負です。 をもう つ分引いて
なので、 です。(1) の余り と (2) の余り を足すと、ちょうど割る数の になっています。
自己採点：
記録を読み込み中…
問2 ★
整数 を で割ると 余る。，， を で割った余りを、それぞれ求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
は 、 は 、 は
解説
（ は整数）とおきます。それぞれ「」の形に直します。
よって余りは です。
のままでは が 以上なので、余りとは言えません。 を1つくくり出して、 以上 未満にそろえるのがポイントです。
自己採点：
記録を読み込み中…
問3 ★
(1) ， (2) ，
上の (1)(2) のそれぞれについて、互除法を用いて2数の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) (2)
解説
(1)
よって最大公約数は です（，）。
(2)
よって最大公約数は です（，）。
自己採点：
記録を読み込み中…
問4 ★
分数 を約分した分数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
分母と分子の最大公約数を互除法で求めます。
最大公約数は で、， です。よって
自己採点：
記録を読み込み中…
問5 ★
と の最大公約数と最小公倍数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
最大公約数 、最小公倍数
解説
互除法より
なので、最大公約数は です。， なので、 より
よって、最大公約数は 、最小公倍数は です。
自己採点：
記録を読み込み中…
問6 ★
，， の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
3つの数の公約数は、「 と の公約数」のうち も割り切るものです。 と の公約数はすべて、その最大公約数の約数なので（第1章 公式5）、まず2数の最大公約数を求め、それと の最大公約数を求めればよいことになります。
より、 と の最大公約数は です。 なので、 と の最大公約数は です。
よって3つの数の最大公約数は です。
自己採点：
記録を読み込み中…
問7 ★
を割ると 余り、 を割ると 余る自然数のうち、最大のものを求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
求める数を とすると、 と はどちらも で割り切れます。また、余りは割る数より小さいので です。
と の公約数のうち最大のものは最大公約数です。互除法で
より、最大公約数は です。 なので条件を満たし、求める数は です。
（確かめ）， です。
自己採点：
記録を読み込み中…
問8 ★
縦 cm、横 cm の長方形の紙がある。この紙から、短いほうの辺を1辺とする正方形をできるだけ多く切り取り、残った長方形に対しても同じことをくり返す。紙がちょうどなくなるとき、最後に切り取った正方形の1辺の長さと、切り取った正方形の枚数の合計を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
1辺 cm、合計 枚
解説
本文の図のとおり、正方形を切り取る作業は互除法そのものです。各段の商が、その大きさの正方形の枚数になります。
上から順に、1辺 cm が 枚、1辺 cm が 枚、1辺 cm が 枚、1辺 cm が 枚です。
最後の正方形の1辺は と の最大公約数 cm で、枚数の合計は 枚です。
よって です。
自己採点：
記録を読み込み中…
問9 ★★
を自然数とする。 と は互いに素であることを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説を参照（引き算を重ねると と の組に行き着く）
解説
公式4（一方から他方の何倍かを引いても最大公約数は変わらない）をくり返します。
したがって
と組をおきかえても最大公約数は変わらず、最後の と の最大公約数は です。よって と の最大公約数は で、2数は互いに素です。（証明終）
まとめると で、2数の公約数は を割り切る、と言っても同じです。
自己採点：
記録を読み込み中…
問10 ★★
と の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
， です。互除法で
より、最大公約数は です。
で、 は と の最大公約数です。偶然ではなく、一般に と の最大公約数は、 と の最大公約数を として になります（実践問題 j17）。
自己採点：
記録を読み込み中…
問11 ★★
を自然数とする。
(1) と の最大公約数としてありうる値を、すべて求めなさい。
(2) (1) の最大公約数が より大きくなるような、 以下の自然数 の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) (2) 個
解説
(1) を の式で割るように変形します。
公式4で とすると、求める最大公約数は と の最大公約数に等しくなります。 は素数なので、 が の倍数なら 、そうでなければ です。どちらも起こるので（ で と 、 で と ）、ありうる値は です。
(2) 最大公約数が になるのは、 が の倍数のときです。 とすると で、 より です。 の です。
自己採点：
記録を読み込み中…
問12 ★★
自然数 ， が互いに素ならば、 と も互いに素であることを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説を参照（共通の素因数 があると仮定し、 が と の両方を割り切る矛盾を導く）
解説
と が互いに素でないと仮定します。最大公約数は 以上なので、その素因数を1つとって とすると、 は と の両方を割り切ります。
の素因数分解は、 の素因数分解と の素因数分解を並べたものです。素因数分解はただ1通りなので、 の素因数 は か の素因数です。
- が を割り切るとき： は も割り切ります。
- が を割り切るとき： は も割り切ります。
どちらの場合も は と の公約数になり、 と が互いに素であることに反します。よって と は互いに素です。（証明終）
たとえば ， なら、 と は互いに素です。
自己採点：
記録を読み込み中…
問13 ★★
2つの自然数 ，（）に互除法を行ったところ、割り算は3回で終わり、商は順に ，， であった。 と の最大公約数が であるとき、， を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，
解説
1回目と2回目の余りを ， とすると、互除法の式は
です。3回目で割り切れたので、最後の割る数 が最大公約数で、 です。下の式から順に
よって です。
（確かめ），， で、商は ，， です。
自己採点：
記録を読み込み中…
問14 ★★
自然数 を で割ったとき、商と余りが等しくなった。このような の個数と、そのすべての和を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
個、和
解説
商と余りを とすると
です。余りの範囲から は 以上 以下で、 は自然数なので です。よって で、 の 個です。和は
よって です。
とすると で、商は 、余りは になってしまいます。余りの範囲 を忘れないようにしましょう。
自己採点：
記録を読み込み中…
問15 ★★
分数 が約分できるような、2けたの自然数 の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
個
解説
約分できるのは、分子と分母の最大公約数が 以上のときです。 を消すように引くと
なので、最大公約数は と の最大公約数に等しくなります。 は素数なので、約分できるのは が の倍数のときです。
より で、この範囲の の倍数は （ から まで）です。よって です。
たとえば なら と約分できます。
自己採点：
記録を読み込み中…
問16 ★★
自然数 ， について、 と の最大公約数は、 と の最大公約数に等しいことを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説を参照（）
解説
公式4（一方から他方の何倍かを引いても最大公約数は変わらない）をくり返します。
なので、最大公約数を変えずに
と組をおきかえられます。よって と の最大公約数は、 と の最大公約数に等しくなります。（証明終）
たとえば ， なら、 と の最大公約数は で、 と の最大公約数 と一致します。
自己採点：
記録を読み込み中…
問17 ★★★
， を自然数とし、 を で割った余りを とする。
(1) を で割った余りは であることを示しなさい。
(2) と の最大公約数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) 解説を参照（ で、 は の倍数） (2)
解説
(1) （ は 以上の整数、）とおくと
です。 とおくと で、 のとき
が成り立ちます（右辺を展開すると、となりどうしが打ち消し合って だけが残ります）。よって は の倍数です（ のときは なのでやはり倍数です）。 とおくと
で、 より です。したがって を で割った余りは です。（証明終）
(2) (1) より、「 を で割る」ことは、指数だけを見れば「 を で割る」ことと同じ形で進みます。 と の互除法は
なので、公式2と (1) をくり返し使って
と最大公約数を変えずに組が移ります。最後は なので、最大公約数は です。
自己採点：
記録を読み込み中…
問18 ★★★
を自然数とし、 と の最大公約数を とする。
(1) としてありうる値を、すべて求めなさい。
(2) となるような、 以下の自然数 の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) (2) 個
解説
(1) から を引くと なので、 は と の最大公約数です。
次に を消すため、 を4倍して の式で表します。
は と を割り切るので、 も割り切ります。よって または です。 のとき と で 、 のとき と で となり、どちらも起こります。ありうる値は です。
(2) となる条件を調べます。 なら は を割り切ります。逆に （ は自然数）のとき
なので は を割り切ります。 は素因数 を含まないので、素因数分解の一意性から は を割り切ります。すると は と の公約数で を割り切り、 は か なので です。
よって です。 は奇数なので、 で、、つまり （ は自然数）です。 より 、 なので、 です。
自己採点：
記録を読み込み中…
問19 ★★★
2つの自然数 ，（）に互除法を行ったところ、余りが になるまでの割り算の回数がちょうど5回であった。このような の最小値と、そのときの を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
の最小値は 、そのとき
解説
余りを順に ，，，、商を ，……， とすると、5回の割り算は
で、 です。割る数より割られる数が大きいので、商はすべて 以上です。さらに最後の式で なので です。下から順に見積もると
となります。，，ほかの商をすべて とすると、，，，， で等号が成り立ちます。実際
でちょうど5回です。また のときは上の不等式がすべて等号なので、，， から に決まります。
よって、 の最小値は で、そのとき です。
は、前の2つを足して次の数を作るフィボナッチ数列です。互除法の回数がいちばん多くなるのは、フィボナッチ数列のとなり合う2項のときなのです（小話）。
自己採点：
記録を読み込み中…
問20 ★★★
自然数 ， が互いに素であるとき、 と の最大公約数は または であることを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説を参照（最大公約数は を割り切るので素因数は だけ、さらに では割り切れない）
解説
と の最大公約数を とします。
の素因数は だけ は
を割り切ります。 が素因数 をもつとすると、 は を割り切るので、素因数分解の一意性から か、 が を割り切るか、 が を割り切るかのどれかです。 が を割り切るなら、 は も割り切り、 と が互いに素であることに反します。 が を割り切るときも同じです。よって で、 は の累乗（ も含む）です。
は で割り切れない が で割り切れたとすると、 は偶数なので、 と は両方偶数か両方奇数です。両方偶数だと公約数 をもってしまうので、両方奇数です。，（， は 以上の整数）とおくと
で、 は で割り切れません。これは が を割り切ることに反します。
以上より、 は の累乗で で割り切れないので、 または です。（証明終）
実際、， では と で 、， では と で となり、どちらも起こります。
自己採点：
記録を読み込み中…
数学小話コーナー
2000年以上使われ続ける計算手順——『原論』と『九章算術』
ユークリッドの互除法は、紀元前300年ごろにまとめられた『原論』の第7巻に登場します。第7巻の最初の命題では、2つの数から「小さいほうを大きいほうからくり返し引いていく」ことで、2数が互いに素かどうかを判定しています。すぐ次の命題では、同じ操作で最大公約数（『原論』のことばでは「最大の共通の尺度」）を見つけています。割り算の代わりに引き算をくり返していますが、同じ数を何回も引くことは割り算と同じなので、中身は本文の互除法そのものです。もっとも、この方法はユークリッドより前から知られていて、『原論』はそれを整理して書き残したものだと考えられています（※諸説あり）。
遠く離れた中国にも、よく似た方法がありました。紀元1世紀ごろにまとめられたとされる数学書『九章算術』（※成立年代は諸説あり）には、分数を約分する手順として「分母と分子を並べ、多いほうから少ないほうを引く。これを互いにくり返し、2つが等しくなったらその数で約分する」と書かれています。この方法は「更相減損」（互いに引き減らす）と呼ばれました。たとえば なら、 と進んで が見つかり、 と約分できます。
アメリカの計算機科学者ドナルド・クヌースは、名著『The Art of Computer Programming』の中で、互除法を「今日まで生き残っている、自明でない最古のアルゴリズム」と呼び、「すべてのアルゴリズムのおじいさん」とたとえています。アルゴリズムとは、決まった手順をくり返せば必ず答えが出る計算方法のことです。実際いまでも、コンピュータで分数を約分するときや、数と式 第2章の小話で紹介した RSA 暗号の鍵を作るときに、互除法が使われています。
豆知識
互除法は、割り算を何回すれば終わるのでしょうか。1844年、フランスの数学者ラメは「割り算の回数は、小さいほうの数のけた数の5倍を超えない」ことを証明しました。たとえば小さいほうが3けたなら、多くても15回で終わります。回数がいちばん多くなるのは、 と のようなフィボナッチ数列のとなり合う2項のときで（実践問題 j19）、商がずっと ばかりになり、なかなか数が小さくなりません。計算の手間を数学的にきちんと見積もった、最も早い例の1つとされています（※諸説あり）。
うるう年の決め方と互除法
地球が太陽のまわりを1周して季節がひと回りするまでの時間は、約 日です。カレンダーの1年は整数の 日なので、毎年約 日ずつ季節とずれていきます。このずれを、ときどき1日足す「うるう年」で調整しています。問題は、 という端数を、どんな割合でうるう年を入れれば近似できるかです。
ここで互除法の出番です。 として、 と に互除法を行うと
と、商が ，，，，…… と並びます。この商を使うと、 は
という形に書けます。このような分数を連分数といいます。途中で打ち切ると、，，，，…… と、だんだん精度の上がる近似分数が得られます。
いちばん粗い は「4年に1回うるう年」で、古代ローマのユリウス暦のやり方です。1年あたり 日ずつ多すぎるので、約128年で1日ずれます。次の は「33年に8回」で、11世紀のペルシャで作られたジャラーリー暦がこの周期を使ったといわれます（※諸説あり）。計算の上では、約4500年で1日しかずれません。
いま世界で使われているグレゴリオ暦（1582年〜）は、「4で割り切れる年はうるう年、ただし100で割り切れる年は平年、さらに400で割り切れる年はうるう年」というルールで、400年に97回です。 は連分数の近似分数ではありませんが、「100年ごと」「400年ごと」という区切りが分かりやすく、それでも約3300年で1日のずれに収まります。
豆知識
連分数の近似分数は、「分母がそれ以下の分数の中で、いちばん近い」という性質をもっています。たとえば より分母が小さい分数で、 に より近いものはありません。円周率 を連分数にすると、 や が出てきます。 は、小数第6位まで と一致します。
引き算で勝負する——ユークリッドのゲーム
2人で遊ぶ、互除法そっくりのゲームがあります。1969年にイギリスの数学雑誌で紹介された「ユークリッドのゲーム」です（※紹介者・年は文献による）。
ルールはかんたんです。紙に2つの自然数を書きます。手番の人は、大きいほうの数から、小さいほうの数の「何倍か」を引きます。何倍を引くかは自由ですが、結果が負になってはいけません。引いた結果で大きいほうの数を書きかえ、相手に手番を渡します。どちらかの数を にした人の勝ちです。
と から、Aさんが先手で始めてみます。Aさんは から を引いて にするか、 を引いて にするかを選べます。
- にした場合：Bさんは から を引くしかなく、。Aさんも から を引くしかなく、。Bさんが から を引いて にし、Bさんの勝ちです。
- にした場合：Bさんは から にするしかなく、Aさんが から を引いて勝ちます。
ゲームの進み方は互除法そのもので、「商が 以上になる場面」でだけ選択肢が生まれます。商が 以上の場面を受け取った人は、「全部引く」か「1つ分だけ残す」かを選べるので、先の展開を読めば必ず勝てる側を選べるのです。商が の場面では、引き方が1通りしかないので運命に従うしかありません。
豆知識
実は、手番の人が勝てるかどうかは最初の2数を見るだけで判定できます。大きいほうが小さいほうの 倍（黄金比）より大きければ手番の人の勝ち、小さければ相手の勝ちです（2数が等しければ、すぐに にできるので手番の人の勝ち）。 なので、先手のAさんが正しく指せば勝てます。黄金比は、互除法の回数が最も多くなるフィボナッチ数列（小話1の豆知識）のとなり合う2項の比が近づいていく値でもあります。
厳密定義（発展）
※ここは発展ページです。本文では、割り算の商と余りがただ1組に決まることや、互除法がいつか必ず終わることを、当たり前のこととして使いました。ここではそれらを証明し、さらに互除法から「最大公約数は の形に書ける」という性質を導きます。最後に、第1章とは別の道すじで、素因数分解の一意性をもう一度証明します。
このページでは、とくに断らないかぎり文字は整数を表します。第1章の厳密定義で導入した整除の記号 （ は を割り切る）と、自然数の最小性をここでも使います。最小性は、 以上の整数の集まりについても同じように成り立ちます（，，，…… と小さい順に調べていけば、条件を満たす最初の数に行き当たるからです）。
割り算の定理
定理1：除法の定理
整数 と自然数 に対して
を満たす整数 ， がただ1組存在する。
証明 （存在）（ は整数）の形の数のうち、 以上のものを考える。 とすると、 より なので、そのような数は少なくとも1つある。その中で最小のものを とすると、 である。もし なら、 も 以上でこの形の数であり、 より小さい。これは の最小性に反するので、 である。
（一意性）（，）とすると、 である。右辺は を満たす。左辺は の倍数であり、 より大きく より小さい の倍数は だけなので、 であり、 より でもある。（証明終）
本文の「数直線で、 以下にある の倍数の目盛りのうち にいちばん近いもの」は、 となる のうち を最小にするもの、ということで、この証明の の選び方と同じです。
最大公約数と互除法の原理
定義1：公約数と最大公約数
少なくとも一方が でない整数 ， について、 と の両方を割り切る整数を と の公約数といい、公約数のうち最大のものを最大公約数という。最大公約数が であるとき、 と は互いに素であるという。
はいつでも公約数なので、公約数は必ずあります。また なら、 の約数の絶対値は 以下なので（第1章 定理1(3)）、公約数は有限個しかなく、最大のものが決まります。約数は符号を変えても約数なので、 と の最大公約数は と の最大公約数に等しくなります。さらに はどんな整数でも割り切れるので、 と の公約数は の約数そのもので、最大公約数は です。本文 公式2 の「 と の最大公約数を と考える」は、この定義から出てくることです。
定理2：互除法の原理
（ は整数）が成り立ち、 と の少なくとも一方が でないとする。このとき、 と の公約数全体と、 と の公約数全体は一致する。とくに、 と の最大公約数は と の最大公約数に等しい。
証明 かつ ならば、第1章 定理1(2) より 、すなわち である。逆に かつ ならば、同じく 、すなわち である。公約数全体が一致するので、最大のものも一致する。（証明終）
， の一方が でなければ、 より ， の一方も ではないので、両方の最大公約数が定義されています。この定理では ， が本当の商と余りである必要はありません。本文 公式4（ と の最大公約数は、 と の最大公約数に等しい）は、この定理で ， としたものです。
互除法は必ず終わる
定理3：ユークリッドの互除法
自然数 ， に対して ， とおき、 について
と、 を で割った余り を求めることを、余りが になるまでくり返す。この操作は 回以内に必ず終わり、 となったとき、 が と の最大公約数である。
証明 余りは割る数より小さいので
である。整数が1回ごとに 以上ずつ減るので であり、 以上の値をとれるのは の範囲に限られる。よって 回以内の割り算で余りが になる。 となったとすると、定理2 をくり返し使って
となる。（証明終）
のときは、1回目の割り算の商が 、余りが で、 と が入れかわるだけです。定理が保証するのは「 回以内」という大まかな回数ですが、実際にはずっと速く終わり、回数は のけた数の5倍以下であることが知られています（ラメの定理、小話1の豆知識）。
最大公約数は の形に書ける
定理4：最大公約数と一次式
自然数 ， の最大公約数を とすると
を満たす整数 ， が存在する。
証明 定理3 の ，，，……， が、どれも「」の形に書けることを示す。まず
である。， と書けているとすると
となり、 もこの形に書ける。これを と順に使えば、 もこの形に書ける。（証明終）
たとえば と では、本文の互除法の式を下から逆にたどって
となります。このような ， を手際よく見つける手順は、第3章で一次不定方程式を解くときに扱います。
定理4 から、すぐに次のことが分かります。
- と の公約数 は を割り切るので、公約数はすべて最大公約数の約数である。第1章 定理6 では素因数分解を使ってこれを示しましたが、ここでは素因数分解を使っていません。
- と が互いに素であることと、 を満たす整数 ， が存在することは同値である。（互いに素なら定理4 そのもの。逆に なら、公約数は を割り切るので しかありません。）
もう1つの道すじ——互除法から素因数分解の一意性へ
第1章では、素因数分解の一意性（第1章 定理3）を「最小の反例」で先に証明し、そこからユークリッドの補題（第1章 定理5）を導きました。教科書でよく見かけるのは逆の順序で、互除法から定理4 を作り、それを使って補題を示し、最後に一意性を導きます。ここでは、その道すじをたどります。
定理5：ユークリッドの補題（別証明）
，， を自然数とする。
(1) と が互いに素で、 ならば、 である。
(2) 素数 が を割り切るならば、 は または を割り切る。
証明 (1) 定理4 より、 を満たす整数 ， がある。両辺に をかけると
である。 であり、 より なので、第1章 定理1(2) より である。
(2) が を割り切らないとする。 の正の約数は と だけで、そのうち は を割り切らないので、 と の正の公約数は だけ、つまり と は互いに素である。(1) を ，， に使えば、 より である。（証明終）
主張は第1章 定理5(1)(2) とまったく同じです。第1章では （素因数 の個数）を使って示しましたが、ここでは素因数分解の一意性を一度も使っていません。そのため、これを使って一意性を証明しても、話が堂々めぐりになりません。
定理6：素因数分解の一意性（別証明）
以上の整数の素因数分解は、素数を並べる順序の違いを除いて、ただ1通りである。
証明 2通り以上に素因数分解できる 以上の整数があったとして、そのうち最小のものを とし
を、並べ方の違いでは説明できない異なる2つの素因数分解とする。
は を割り切るので、定理5(2) より は か を割り切る。後者なら同じ議論を に続ける。これをくり返すと、 はある を割り切ることが分かる。 は素数で、その 以上の約数は 自身だけなので、 である。
2つの並びから と を1つずつ取り除くと、どちらの残りも積が の素数の並びになる。一方の残りが空（積が ）なら、他方の積も なので空であり、元の2つの並びは だけの同じ並びだったことになって、仮定に反する。したがって両方の残りは空でなく、 は 以上 未満の整数である。元の2つの並びは異なるので、残りの2つの並びも異なり、 は2通りに素因数分解できる。これは の最小性に反する。（証明終）
こうして、第1章とは逆の順序でも同じ結論にたどり着きました。
素因数分解とは関係がなさそうな「割り算のくり返し」が、整数のいちばん基本的な性質を支えているのです。第3章では、定理4 の ， を実際に求める手順を身につけ、 の形の方程式の整数解をすべて求めます。
この章の学習が終わったら
学習完了テストを受ける