約数と倍数から整数論、暗号へ｜武蔵野個別指導塾

約数と倍数で見ていた割り切れる関係を、余りの計算へつなげます。互除法からRSA暗号まで小さな数でたどり、整数を学ぶ意味を自分の言葉で説明してみましょう。

約数と倍数から整数論、暗号へ

割り切れるかどうかを調べる先に

よくあるのは、部活帰りの教室で、素因数分解の枝をノートに書きながら「これができると、何に使えるのですか」と尋ねる場面です。計算の途中には小さな素数が並び、答えも整数のかけ算です。方程式のように未知の量が求まるわけでも、図形のように形が見えるわけでもなく、数を細かく分ける目的が見えにくいのかもしれません。

けれども、整数の学習には、数の大きさとは別の見方があります。「何で割り切れるか」「割った余りが同じか」という見方です。約数や倍数は、その入口に当たります。高校で学ぶ互除法や整数の方程式も、大学で扱う合同式や暗号の数学も、この問いを受け継いでいます。

暗号と聞くと、特別な機械だけが扱う難しい計算を想像するかもしれません。ここでは、手で追える整数を使い、計算して別の数に変えたものが、なぜ元に戻るのかを考えます。最初から仕組みの全部を覚える必要はありません。いま知っている割り算のどの部分が残り、どの部分が新しくなるかを追ってみてください。

中学では数を素数の積にほどく

正の整数aで正の整数bを割り切れるとき、aをbの約数、bをaの倍数といいます。たとえば、12=3×4なので、3は12の約数で、12は3の倍数です。約数と倍数は別々の暗記事項ではなく、同じ関係を両側から呼んだ名前です。「何の約数か」「何の倍数か」まで言うと、関係がはっきりします。

素数は、1より大きい整数で、正の約数が1と自分自身だけである数です。1は素数に含めません。素因数分解は、1より大きい整数を素数だけの積で表すことです。同じ数でも最初の分け方は変えられますが、最後まで素数に分けると、並べる順序を除いて同じ結果になります。この一意性が、素因数分解を数の比較に使える理由です。

具体的に、36と60を比べましょう。

36=2²×3²

60=2²×3×5

両方を割り切る正の整数を公約数、そのうち最も大きいものを最大公約数といいます。共通に取り出せる素因数は、2が2個と3が1個です。36には3がもう1個ありますが、60にはありません。したがって、最大公約数は2²×3=12です。

一方、両方の倍数になっている正の整数を公倍数、そのうち最も小さいものを最小公倍数といいます。こちらは36と60のどちらも割り切れるだけの素因数を用意します。2は2個、3は2個、5は1個必要なので、最小公倍数は2²×3²×5=180です。

最大公約数では各素因数の個数を少ない方に合わせ、最小公倍数では多い方に合わせました。これは答えを作る規則ですが、理由と一緒に覚えたいところです。前者は「両方から取り出せる」、後者は「両方を中に含められる」という条件の違いから決まります。5のように片方にない素因数も、ない側の個数を0と考えれば同じように整理できます。

36個の品物と60個の別の品物を、それぞれ余りなく同じ数の組に分けるなら、組の数は公約数です。組の数を最大にすると12組になり、各組にはそれぞれ3個と5個が入ります。逆に、36ずつでも60ずつでも数え終われる正の総数を探すなら、公倍数の問題です。数字だけで判別せず、何をそろえるのかを文章で確かめましょう。

この例では12×180=36×60も成り立ちます。一般に、2つの正の整数では、最大公約数と最小公倍数の積が元の2数の積に等しくなります。素因数ごとに見ると、少ない方の個数と多い方の個数を合わせれば、元の個数の合計になるからです。計算結果の点検にも使えますが、その背後に素因数の数え方があることが重要です。

整数では、割り算の結果がいつも整数になるわけではありません。そのため「割り切れる」という性質が区別を生みます。分数まで使えば簡単に割れる場面でも、整数だけという条件を置くと、約数を調べる意味が現れます。この条件への注意が、高校の整数問題につながります。

高校では余りを残して割り算する

高校で整数を考えるときは、割り切れなかった場合にも目を向けます。整数aを正の整数bで割ると、a=bq+r、0≦r<bを満たす整数qとrがただ1組定まります。qが商、rが余りです。余りの範囲まで決めることによって、同じ整数の表し方が1つに定まります。

この割り算を繰り返して最大公約数を求めるのが、ユークリッドの互除法です。252と198なら、次のように計算できます。

252=198×1+54

198=54×3+36

54=36×1+18

36=18×2+0

最後の0でない余り18が、最大公約数です。素因数分解をしていないのに、なぜ求まるのでしょうか。最初の式で、252と198の公約数は、その差である54も割り切ります。逆に198と54を割り切る数は、その和である252も割り切ります。つまり、252と198の公約数全体は、198と54の公約数全体と同じです。

この置き換えを続けても最大公約数は変わりません。しかも、0でない余りは割る数より小さくなります。正の整数を小さくし続ける操作はいつまでも続かないので、余りが0になって止まります。互除法には、答えが保たれる理由と、手順が終わる理由の両方があります。単に計算が速いという説明から、手続きの正しさを説明する段階へ進んでいるのです。

さらに、この計算を逆向きにたどると、最大公約数を元の2数の整数倍の和で表せます。

18=54−36=4×54−198=4×252−5×198

したがって、252x+198y=18を満たす整数の組として、x=4、y=−5が見つかります。未知数が複数あり、その整数解を求めるこのような方程式を不定方程式と呼びます。この場合は解が1組だけではありません。任意の整数tに対し、x=4+11t、y=−5−14tも解になります。代入すると、tを含む部分の2772tと−2772tが打ち消し合うためです。

右辺を1に変えた252x+198y=1には、整数解がありません。左辺はどんな整数x、yを入れても18の倍数ですが、1は18の倍数ではないからです。未知数を求め始める前に、そもそも解が存在するかを判断できる点に、約数の知識が生きています。

余りを使う別の表現が合同式です。正の整数mについて、a−bがmで割り切れるとき、aとbはmを法として合同であるといい、a≡b（mod m）と書きます。「法」は、何で割った余りを比べるかを示す数です。たとえば17≡2（mod 5）は、17と2の差が5の倍数であることを表します。

合同式は等号と同じではありません。17と2は異なる整数ですが、5で割った余りに注目すると同じ仲間です。高校の整数問題から一歩広げてこの表現を覚えると、桁の大きい整数そのものを追わずに、必要な余りだけを追えます。小さな数へ置き換えながら性質を保つという考え方は、互除法にも合同式にも共通しています。

大学では余りの世界に計算をつくる

大学の整数論では、合同を数どうしの関係として整理します。mで割った余りが同じ整数をすべてまとめた集まりを、mを法とする剰余類と呼びます。たとえば法が5なら、余り0、1、2、3、4に対応する5つの剰余類があります。各集まりには無限に多くの整数が入り、負の整数も含まれます。

ここで、整数どうしを計算する代わりに、剰余類どうしを足したりかけたりします。各集まりから代表の整数を選んで計算し、その結果が属する集まりを答えにします。代表を別の整数に替えても同じ集まりに着くことが必要ですが、合同ではこの性質が成り立ちます。a≡b、c≡dが同じ法で成り立てば、a+c≡b+d、ac≡bdも成り立つからです。

法が5のとき、17×8の余りは2×3の余りで求められ、答えは1です。大きな積を出してから割っても、先に余りへ置き換えてからかけても、同じ剰余類に到着します。これが、余りの世界で計算することの意味です。単なる計算の省略から、計算できる対象そのものを作る方向へ一般化しています。

ただし、割り算は注意が必要です。余りの世界でaによる割り算をするには、aにかけると1と合同になる整数を使います。これをaの逆元といいます。法5では2×3≡1なので、2の逆元は3です。一方、法6で2に何をかけても偶数なので、1と合同にはなりません。逆元が存在する条件は、aと法mの最大公約数が1であることです。この関係を「互いに素」といいます。

そこで素数が再び登場します。pが素数なら、1からp−1までの整数はすべてpと互いに素です。また、フェルマーの小定理は、素数pとpで割り切れない整数aに対して、aの(p−1)乗がpを法として1と合同になる、と述べます。素数であることと、aがpの倍数でないことが条件です。たとえばp=5、a=2なら、2の4乗は16であり、5で割ると1余ります。

この定理は、大きな累乗の余りが規則的に戻ることを教えます。RSA暗号は、こうした整数の性質を使う公開鍵暗号の一つです。公開鍵暗号では、暗号化に使う鍵を公開し、元に戻す復号の鍵を秘密にします。数を元に戻すための情報を、暗号化する側が持たなくてもよい仕組みです。

数学の動きを追うため、異なる素数5と11を選び、その積n=55を使います。さらに(5−1)×(11−1)=40を求め、40と互いに素な暗号化の指数e=3を選びます。復号の指数はd=27とします。3×27=81≡1（mod 40）だからです。公開する組はnとe、秘密にするのはdで、素因数5と11も秘密に保つ情報です。

メッセージを表す整数をM=7とすると、暗号化では7³を55で割った余りを求めます。

7³=343=55×6+13

暗号化された数Cは13です。復号では13の27乗を55で割った余りを求めると、7に戻ります。累乗の途中で繰り返し余りを取れるので、巨大な整数を最後までそのまま書き出す必要はありません。

戻る理由も確かめましょう。暗号化して復号する操作は、合同式の上ではMの81乗を求めることに対応します。Mが5で割り切れなければ、フェルマーの小定理からMの4乗は法5で1です。80は4の倍数なので、Mの81乗は法5でMに戻ります。Mが5で割り切れる場合も、両方の余りは0です。法11でも、80が10の倍数であることから、同じ結論が得られます。

つまり、Mの81乗とMの差は5でも11でも割り切れます。5と11は互いに素なので、その差は55で割り切れます。0から54までの数をメッセージと決めれば、復号で得る余りは元のMそのものです。中学の約数の関係が、元に戻ることの保証を支えています。

もちろん55はすぐ素因数分解できるので、この数に秘密を守る力はありません。ここでの計算はRSAの数学的な骨組みであり、実際の暗号には、十分に大きな数やメッセージの加工を含む設計が必要です。素因数がわかれば秘密の指数を求める手掛かりが得られることと、元に戻る計算が正しいことは、区別して考えます。

三つの段階を結ぶのは割り切れる関係

中学では整数を素数の積に分け、数の内部を比べました。高校では割った余りを残し、公約数を保ったまま数を小さくしました。大学では同じ余りの整数をまとめ、その集まりの間に計算を定めました。扱う対象は変わっても、中心にあるのは「ある数が別の数を割り切る」という関係です。

合同式の定義も、差が法で割り切れるという言い方でした。逆元の存在にも、最大公約数が1という条件が現れました。RSAの復号でも、2つの素数で割り切れる差が、その積で割り切れることを使いました。離れた単元に見える用語が、同じ関係を別の角度から見ています。

もう一つ変わらないのは、必要な性質を残して対象を扱いやすくする姿勢です。互除法では公約数全体を残し、合同式では余りを残します。何を変えてよく、何を変えてはいけないかを判断しているのです。ただ数を小さくしたから便利なのではなく、問いの答えに必要な情報が失われていないから使えます。

暗号の話まで一度に理解する必要はありません。最大公約数の計算で「共通に取り出せるのはなぜここまでか」と説明できれば、その問い方は先でも使えます。計算の手順に理由を添えることが、抽象的な定義を読むための足場になります。

つながりを使った学び方

最初の手順は、問題文の条件を短い言葉に直すことです。「両方を割り切る数を探す」「両方の倍数を探す」「余りだけを求める」のどれなのかを、式の前に書きます。同じ整数が並んでいても、求める関係が違えば使う道具は変わります。計算が止まったときは、まずこの一行に戻りましょう。

次の手順は、答えから元の条件へ戻って確かめることです。最大公約数なら両方を割り切るか、不定方程式なら見つけた整数を代入して左右が一致するか、合同式なら差が法の倍数かを点検します。答え合わせを記号の一致だけで済ませず、問題が求めていた性質を自分で検査します。

続いて、使った規則の条件を言葉で添えます。フェルマーの小定理なら「法は素数か」「底はその素数で割り切れないか」を見ます。逆元なら「法と互いに素か」です。条件を省いた公式は、使えない場面にも適用してしまいます。学んだ直後ほど、式の隣に短い条件を残しておくと、自分の判断をたどれます。

最後に、同じ問いを別の方法で眺めます。最大公約数を素因数分解で求めたら、互除法でも確かめます。両者の途中計算は異なりますが、答えは一致します。「何を共通に見ているのか」を説明すると、方法ごとの役割が整理できます。新しい方法を学んだ際に、以前の方法との接点を探す練習です。

塾の授業で担うのは、途中式を見て、どの条件の読み取りで止まったかを絞ることです。素因数分解は正しいのに最大公約数を誤った場合と、整数解という条件を見落とした場合では、戻る場所が違います。解説の後には、生徒本人の言葉で規則の理由を確かめ、次の問題でその判断ができるかを見ます。

家庭では、お子さまが説明を試せる時間を持つことが支えになります。「なぜその数で割ったのか」「求めた数は元の条件に合うか」と、ノートの一部分を尋ねる程度で十分です。説明が途切れた箇所は、次の授業に持っていく問いになります。先の専門用語を覚えさせるより、いま使った計算の意味に耳を傾けてください。

よくある質問

素因数分解が苦手だと整数論には進めませんか

素数の意味と、積に戻して確かめる習慣から整えれば進めます。最大公約数には互除法という別の求め方もあります。ただし、分解の意味を理解すると、最小公倍数の作り方や素数の役割が読みやすくなります。速さだけを目標にせず、どの因数が共通しているかを説明してみましょう。

合同式では等式と同じように約分できますか

いつでもできるわけではありません。法6で2×1≡2×4ですが、1と4は法6で合同ではありません。共通の2を消すと誤りになります。同じ法のまま共通の因数を消せるのは、その因数が法と互いに素である場合です。大学で学ぶ逆元の存在が、この操作を支えています。

暗号を学ぶなら小さな数の計算にも意味がありますか

あります。小さな数なら、公開する情報、秘密にする情報、暗号化と復号の順序を追えます。ただし、手で仕組みを確かめることと、安全な暗号を作ることは別の課題です。まずは元に戻る理由を合同式で説明できるところを目指しましょう。

部活帰りの教室で書いた素因数分解の枝は、数を細かくして終わる図ではありません。何が共通し、何が違うかを読むための図です。その読み方が、余りを使う計算へ、さらに情報を変換して戻す数学へ続きます。「答えは合ったけれど、ここが腑に落ちない」という一行にも、武蔵野個別指導塾の授業には話し合う席があります。