回 3-1 分野 3 整数と余り
ユークリッドの互除法は、2 つ の数の大きい方を小さい方で割り、割った数と余りで同じことを繰り返して、余りが 0 になったときの割った数を最大公約数とする手順です。1071 と 1029 なら、余りは 42、21、0 と進み、3 回 の割り算で最大公約数 21 が出ます。約数を 1 つ ずつ試すより回数がずっと少なく、割り算の回数は小さい方の桁数のおよそ 5 倍までに収まります。
約数と素数と最大公約数をそろえ、互除法がなぜ速いのかを、割り算の回数を数えて確かめます。
文 ゆめさくコード編集部 公開 2026年10月30日 更新 2026年10月30日 出典を確かめた日 2026年10月30日
1071 / 1029 は、 分子と分母の最大公約数で割れば、それ以上は約分できない形になります。最大公約数 (2 つ の数の両方を割り切る数のうち一番大きい数) を速く求める手順が、ユークリッドの互除法です。
1071 と 1029 の両方を割り切る数を、1 から順に探すこともできます。1029 から 1 つ ずつ下げて試すと、21 に着くまでに 1009 回 の確かめが要ります。互除法なら 3 回 の割り算で済みます。数が 10 桁、100 桁と大きくなると、この差は試しきれないほどに広がります。
最大公約数は、分数の約分のほかにも、周期をそろえる計算、暗号の鍵の確かめ、競技プログラミングの問題に毎日のように出てきます。この回では、約数と素数をそろえてから、互除法の手順、正しい理由、割り算の回数を順に数えます。
約数、 言葉を 4 つ そろえます。
言葉 意味 12 と 約数 その数を 12 の 素数 約数が 2, 3, 5, 7, 11, 13 最大公約数 (gcd) 両方の 6 最小公倍数 (lcm) 両方の 36
2 つ の数の最大公約数が 1 のとき、2 つ は互いに素と言います。8 と 15 は、どちらも素数ではありませんが、互いに素です。
最大公約数と最小公倍数には、a × b = gcd(a, b) × lcm(a, b) の関係があります。12 × 18 = 216 で、6 × 36 = 216 です。ですから最小公倍数は、最大公約数を求めてから a × b ÷ gcd(a, b) で出せます。
約数を並べて重なりを探す求め方は、小さい数なら手で済みます。素因数分解 (素数の掛け算に分けること) で求める方法もあります。どちらも数が大きくなると、試す数が増えて重くなります。
ユークリッドの 互除法は、割り算を繰り返すだけの手順です。
大きい方の数 a を、小さい方の数 b で割り、余り r を出す r が 0 なら、b が最大公約数。ここで止まる r が 0 でなければ、a を b に、b を r に置き換えて、1 に戻る 1071 と 1029 で進めると、次の通りです。
回 割られる数 割る数 商 余り 1 1071 1029 1 42 2 1029 42 24 21 3 42 21 2 0
3 回 目で余りが 0 になったので、そのときの割る数 21 が最大公約数です。1071 = 21 × 51、1029 = 21 × 49 で、51 と 49 は互いに素なので、1071 / 1029 は 51 / 49 まで約分できます。
なぜ余りに a を b で割った余りを r とすると、a = b × q + r です。この式から、次の 2 つ が言えます。
a と b の両方を割り切る数は、r = a − b × q も割り切る b と r の両方を割り切る数は、a = b × q + r も割り切る ですから、a と b の公約数の集まりと、b と r の公約数の集まりは同じです。集まりが同じなら、一番大きい数も同じです。置き換えるたびに数は小さくなり、いつか余りが 0 になります。余りが 0 のときの b と 0 の最大公約数は b なので、そこで答えが出ます。
この手順は、紀元前 300 年 ごろのユークリッドの『原論』の第 7 巻、命題 2 に、大きい方から小さい方を引き続けて共通の量を探す形で書かれています。手順として書かれた最古のアルゴリズムの 1 つ と言われます。引き算を何回も繰り返す所を、割り算の余りで 1 回 にまとめたのが、今の互除法の形です。
動かして確かめる 1 本 目は、互除法の割り算を 1 回 ずつ出します。上の表と同じ数が出るかを見てください。
動かす 互除法の割り算を 1 回ずつ出す
実行すると、次の通りに出ます
1 1071 = 1029 * 1 + 42
2 1029 = 42 * 24 + 21
3 42 = 21 * 2 + 0
最大公約数 21
割り算の回数 3divmod(a, b) は、商と余りを組で返す 3 回 の割り算で 21 が出ました。出力の * は掛け算の印です。
2 本 目は、約数を大きい方から 1 つ ずつ試す求め方と、互除法の回数を比べます。数えるのは、割り切れるかを確かめた回数と、割り算の回数です。
動かす 1 つずつ試す求め方と回数を比べる
実行すると、次の通りに出ます
1071 1029 gcd 21 21
試す 1009
互除法 3
123456 7890 gcd 6 6
試す 7885
互除法 7
999983 999979 gcd 1 1
試す 999979
互除法 4
1000000 999999 gcd 1 1
試す 999999
互除法 2どの組も答えは同じで、回数がまるで違います。999983 と 999979 は互いに素なので、1 つ ずつ試すと 999979 回 確かめてやっと 1 に着きます。互除法は数回で終わります。
3 本 目は、互除法で一番手間がかかる組を見ます。隣り合うフィボナッチ数 (0, 1, 1, 2, 3, 5, 8 と、前の 2 つ を足していく数。0 を F0 と数える) の組は、最後の 1 回 を除いて商が 1 になり、数がゆっくりしか小さくなりません。
動かす 一番手間のかかる組と桁数
実行すると、次の通りに出ます
F10 桁 2 回数 8 桁*5 10
F20 桁 4 回数 18 桁*5 20
F30 桁 6 回数 28 桁*5 30
F40 桁 8 回数 38 桁*5 40隣り合うフィボナッチ数の組 (F40 は 102334155、F39 は 63245986) でも、割り算の回数は小さい方の 10 進の桁数の 5 倍を超えていません。どんな組でも回数がこの程度に収まることは、ラメの定理として知られています。計算量で言えば、桁数に比例する O(log n) です。
4 本 目は、最大公約数から最小公倍数を出し、Python に入っている math.gcd と math.lcm と照らします。
動かす 最小公倍数と math.gcd で照らす
実行すると、次の通りに出ます
12 18
自作 6 36
math 6 36
1071 1029
自作 21 52479
math 21 52479
8 15
自作 1 120
math 1 120自分で書いた関数と math の関数が同じ数を返しました。lcm は a × b を先に掛けずに、a ÷ gcd を先にしています。先に割る方が、途中の数が小さく済みます。
拡張した 互除法の途中の式を逆にたどると、1071x + 1029y = 21 となる整数 x と y が見つかります。これを拡張した互除法 (拡張ユークリッドの互除法) と呼びます。
動かす 拡張した互除法で x と y を出す
実行すると、次の通りに出ます
g 21 x -24 y 25
21
631071 × (−24) + 1029 × 25 = 21 です。右辺が 21 の倍数の 63 なら、x と y を 3 倍すれば解になります。右辺が 21 の倍数でない数、たとえば 10 なら、左辺はいつも 21 の倍数なので、整数の解はありません。
ax + by = c の形の式 (1 次不定方程式) に整数の解があるのは、c が gcd(a, b) の倍数のときだけです。解がある式は、拡張した互除法で 1 組を出し、それを倍にして求めます。
商を 互除法の割り算の商を順に並べると、分数を「整数 + 1 / (…)」の形に重ねて書いた連分数 (れんぶんすう) になります。1071 / 1029 の商は 1、24、2 だったので、1071 / 1029 = 1 + 1 / (24 + 1 / 2) です。
動かす 商を集めて連分数を作り、元に戻す
実行すると、次の通りに出ます
商 [1, 24, 2]
戻した数 51/49
約分した数 51/49商 [1, 24, 2] から組み直した数は 51/49 で、1071 / 1029 を約分した数と同じです。連分数は、分数や小数に近い簡単な分数を探すときに使います。
仕事と 最大公約数と互除法が出てくる場面は、次の通りです。
分数の約分。fractions.Fraction(1071, 1029) は、中で最大公約数で割り、51 / 49 として持つ 周期をそろえる。12 秒 ごとと 18 秒 ごとに動く 2 つ の処理が次に同時に動くのは、最小公倍数の 36 秒 後 画面の比。1920 × 1080 を最大公約数 120 で割ると、16 対 9 暗号の鍵の確かめ。RSA の鍵の決まりを書いた RFC 8017 は、公開の指数 e が λ(n) と互いに素 (最大公約数が 1) であることと、秘密の指数 d が e × d ≡ 1 (mod λ(n)) を満たすことを求めている。互いに素かは最大公約数で、d は拡張した互除法で出す 競技プログラミング。分数を約分して持つ、数の最大公約数を取る、互いに素かを数える、の形でよく出る Python では、pow(e, -1, m) で、e × d ≡ 1 (mod m) となる d を直に出せます (3.8 から)。中でしていることは、拡張した互除法と同じです。
動かす 小さな数で鍵の決まりを確かめる
実行すると、次の通りに出ます
λ(n) 780
gcd(e, λ) 1
d 413 e*d mod λ 1e = 17 と λ(n) = 780 の最大公約数は 1 なので、e は鍵に使えます。d = 413 で、17 × 413 を 780 で割った余りは 1 です。本物の鍵は数百桁ありますが、互除法の回数は桁数に比例するだけなので、一瞬で終わります。
互除法は 互除法そのものは短いですが、書くときにつまずく所が 3 つ あります。
0 と負の数 gcd(a, 0) は a です。0 はどの数でも割り切れるからです。上のコードは、b が 0 ならすぐに a を返すので、そのまま正しく動きます。gcd(0, 0) は、math.gcd の文書では、全部が 0 なら 0 を返すと決めています。負の数を入れるときは、math.gcd を使うか、絶対値にしてから割ります。math.gcd は、いつも 0 以上の数を返します。
小数で使う 0.6 と 0.4 の最大公約数を出そうとして、小数のまま % を使うと、0.6 % 0.4 は 0.19999999999999996 になります。小数は 2 進数で正確に表せないからです。小数は 10 倍や 100 倍して整数にしてから互除法にかけます。
先に lcm を a × b ÷ gcd の順に計算すると、a × b が先に大きくなります。Python の整数は桁あふれしませんが、C++ や 決まった大きさの整数では、途中で上限を超えて答えが壊れます。a ÷ gcd × b の順にすれば、途中の数は答えより大きくなりません。
よくある問い ユークリッドの 割り算の回数は、小さい方の数の 10 進の桁数のおよそ 5 倍までに収まります (ラメの定理)。上の 3 本 目のコードでは、一番手間のかかる隣り合うフィボナッチ数の組でも、小さい方が 8 桁の数 (F39) で 38 回 でした。計算量で書くと O(log n) です。
素因数分解で 大きな数では互除法がずっと速いです。素因数分解は、大きな数ほど割ってみる数が増えます。RSA の鍵に使う 2048 ビット (約 617 桁) の数は、今の計算機でも現実的な時間では分解できないとされています。RSA の暗号が安全なのは、この素因数分解の難しさに支えられているからです。互除法は素因数分解をせずに、割り算の余りだけで最大公約数に着きます。
3 つ以上の 2 つ ずつ順に取ります。gcd(a, b, c) は gcd(gcd(a, b), c) です。math.gcd は 3.9 から、いくつでも数を渡せます。
再帰と どちらでも同じ答えです。互除法の回数は少ないので、再帰でも深さの上限に届くことはまずありません。読む人に手順を見せたいときは while、拡張した互除法のように戻りながら値を組むときは再帰が書きやすいです。
確認クイズ 答えだと
1 問目
252 と 105 の最大公約数を互除法で求めます。割り算は何回で、最大公約数はいくつですか。
ア 2 回で 21 イ 3 回で 21 ウ 3 回で 7 エ 4 回で 21 2 問目
最大公約数が 6 で、2 つ の数の積が 216 です。最小公倍数はいくつですか。
3 問目
1071x + 1029y = 10 を満たす整数 x と y について、正しいのはどれですか。
ア x = −24、 イ 拡張した ウ 10 は エ x と 説明課題 「互除法で、(a, b) を (b, a を b で割った余り) に置き換えても、最大公約数が変わらないのはなぜか」を、3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
あなたの説明
模範解答 模範解答を開く 自分の
a を b で割った商を q、余りを r とすると、a = b × q + r と書ける。この式から、a と b の両方を割り切る数は r も割り切り、b と r の両方を割り切る数は a も割り切るので、2 つ の組の公約数の集まりは同じになる。集まりが同じなら一番大きい数も同じなので、置き換えても最大公約数は変わらない。
分数の1 行 で
もっと深く この
一次資料 どれも 2026年 10月 30日 に開いて、題と中身を確かめました。
次へ 次の回 3-2 余りと合同式 余りの 準備中
分野 3 整数と余りの回 3-1 最大公約数と互除法 約数、 この回
3-2 余りと合同式 余りの 準備中
3-3 素数を速く探す 試し割りは 準備中
分野 3 の頁へ戻る ほかの分野を見る
