回 3-2 分野 3 整数と余り
合同式 a ≡ b (mod m) は、a と b を m で割った余りが等しいこと (a − b が m で割り切れること) を表す式です。足し算、引き算、掛け算、累乗は、途中で何度余りを取っても最後の余りが変わりません。この性質で、3^100 を 7 で割った余りは、3^100 を計算せずに 4 と出せます。割り算だけは、割る数と m が互いに素のときにしか使えません。
余りの足し算と掛け算の決まりを確かめてから、大きな累乗の余りを、掛け算の回数を数えながら速く出します。
文 ゆめさくコード編集部 公開 2026年10月30日 更新 2026年10月30日 出典を確かめた日 2026年10月30日
3^100 を 3^100 は 48 桁の数です。これを 7 で割った余りを知りたいとき、48 桁の数を作ってから割る必要はありません。掛け算のたびに 7 で割った余りだけを残しても、最後の余りは同じだからです。
その決まりを式で書いたのが合同式です。この回では、合同式の意味と性質をそろえ、どの計算なら途中で余りを取ってよいか、割り算はなぜ注意が要るかを確かめます。そのあと、掛け算の回数を 100 回 近くから 10 回 ほどに減らす繰り返し二乗法を、回数を数えて確かめます。
合同式とは 整数 a と b を m で割った余りが等しいとき、a と b は m を法として合同と言い、a ≡ b (mod m) と書きます。言い換えると、a − b が m で割り切れることです。
17 ≡ 5 (mod 12)。17 と 5 は、12 で割った余りがどちらも 5 100 ≡ 2 (mod 7)。100 = 7 × 14 + 2 −1 ≡ 6 (mod 7)。−1 − 6 = −7 は 7 で割り切れる 時計は mod 12 の世界です。10 時の 5 時間 後は 15 時ではなく 3 時で、15 ≡ 3 (mod 12) です。曜日は mod 7 で、今日から 100 日 後の曜日は、100 ≡ 2 (mod 7) なので 2 日 後と同じです。
mod は modulo (法) の略です。プログラムの a % m は「a を m で割った余り」を返す演算で、合同式の mod と考え方は同じです。
余りを a ≡ b (mod m) と c ≡ d (mod m) のとき、次が言えます。
計算 合同式 mod 7 の 足し算 a + c ≡ b + d 10 + 9 = 19 ≡ 5、 引き算 a − c ≡ b − d 10 − 9 = 1、 掛け算 a × c ≡ b × d 10 × 9 = 90 ≡ 6、 累乗 a^n ≡ b^n 10^2 = 100 ≡ 2、 多項式 f(a) ≡ f(b) 整数の
掛け算が成り立つ理由を見ます。a = b + km、c = d + lm と書けるので、ac = bd + (bl + dk + klm) m です。後ろの項は m の倍数なので、ac と bd は m で割った余りが同じです。累乗と多項式は、掛け算と足し算を繰り返した物なので、同じく成り立ちます。
割り算は、 6x ≡ 6 (mod 4) の両辺を 6 で割って x ≡ 1 (mod 4) とすると、答えを落とします。x = 3 でも 6 × 3 = 18 ≡ 2 ≡ 6 (mod 4) だからです。
両辺を c で割ってよいのは、c と m が互いに素 (最大公約数が 1) のときだけです。そのとき、c × c' ≡ 1 (mod m) となる数 c' (c の逆元) があり、割る代わりに c' を掛けます。逆元は 3-1 の回の拡張した互除法で出せ、pow(c, -1, m) で出せます。
c と m が互いに素でないときは、ac ≡ bc (mod m) から a ≡ b (mod m / g) までしか言えません。g は c と m の最大公約数です。6x ≡ 6 (mod 4) なら g = 2 で、x ≡ 1 (mod 2)、つまり x は奇数です。
フェルマーの小定理 p が素数で、a が p の倍数でないとき、a^(p−1) ≡ 1 (mod p) です。これをフェルマーの小定理と呼びます。
3^6 = 729 = 7 × 104 + 1 なので、3^6 ≡ 1 (mod 7) です。100 = 6 × 16 + 4 なので、3^100 = (3^6)^16 × 3^4 ≡ 1 × 81 ≡ 4 (mod 7) と出ます。3 の累乗を 7 で割った余りが、6 個 ごとに同じ並びを繰り返すのも、この定理から来ています。
動かして確かめる 1 本 目は、余りの性質を、たくさんの数で確かめます。途中で余りを取った答えと、取らない答えを比べます。
動かす 途中で余りを取っても同じか
実行すると、次の通りに出ます
+ 1000
- 1000
* 1000
2 6 31000 組の全部で、足し算、引き算、掛け算は、途中で余りを取っても同じ余りになりました。% は、割る数が正なら答えをいつも 0 以上で返します。−7 % 3 は 2、−1 % 7 は 6 です。
2 本 目は、3 の累乗を 7 で割った余りの並びと、7 の累乗の一の位 (10 で割った余り) の並びを見ます。
動かす 累乗の余りは周期で繰り返す
実行すると、次の通りに出ます
3^n mod 7
[3, 2, 6, 4, 5, 1]
[3, 2, 6, 4, 5, 1]
3^100 4
7^n の一の位
[7, 9, 3, 1, 7, 9, 3, 1]
7^2026 93^n を 7 で割った余りは 3、2、6、4、5、1 の 6 個 で 1 周します。100 を 6 で割った余りは 4 なので、3^100 の余りは 4 番 目の 4 です。7^n の一の位は 7、9、3、1 の 4 個 で回るので、7^2026 の一の位は、2026 を 4 で割った余り 2 から、2 番 目の 9 です。
3 本 目は、3^100 mod 7 を 3 つ の書き方で出し、掛け算の回数を数えます。繰り返し二乗法は、3、3^2、3^4、3^8 と 2 乗を重ね、100 を 2 進で書いた 1100100 の 1 の桁に当たる物だけを掛けます。
動かす 掛け算の回数を比べる
実行すると、次の通りに出ます
(4, 100, 48)
(4, 100)
(4, 10)
0b1100100
(719476260, 84)
719476260素直に 100 回 掛けると、途中の数は 48 桁まで育ちます。掛けるたびに余りを取ると、数は 7 より小さいままですが、掛け算は 100 回 のままです。繰り返し二乗法は、2 乗が 7 回 と、1 の桁の分の掛け算が 3 回 の、10 回 で済みました。
指数が 10^18 でも、繰り返し二乗法は 84 回 の掛け算で終わりました。10^18 は 2 進で 60 桁で、2 乗が 60 回 、1 の桁の分が 24 回 です。回数は指数の 2 進の桁数に比例し、log2 n の程度です。Python の pow(a, n, m) は、同じ考えで速く計算します。
4 本 目は、割り算の注意と、一次合同方程式と、連立の合同式を、全部の値を試して確かめます。
動かす 割り算、方程式、連立を確かめる
実行すると、次の通りに出ます
[1, 3]
逆元 5 1
x 6
[6]
[8, 23]
2
16x ≡ 6 (mod 4) の解は 1 と 3 で、6 で割ると 3 を落とします。6 と 4 の最大公約数は 2 で、互いに素ではありません。3 と 7 は互いに素なので、3 の逆元 5 (3 × 5 = 15 ≡ 1) を掛けて、3x ≡ 4 の解 x ≡ 6 が出せます。全部試した答えとも同じです。
連立の x ≡ 2 (mod 3)、x ≡ 3 (mod 5) を満たすのは、30 未満では 8 と 23 で、15 ごとに現れます。3 と 5 が互いに素なら、こうした連立の解は 15 を法としてちょうど 1 つ 決まります。これを中国剰余定理と呼びます。
5 本 目は、余りで分けて考える例です。平方数を 4 で割った余りと、9 の倍数の見分け方を確かめます。
動かす 平方数の余りと 9 の倍数
実行すると、次の通りに出ます
平方数 mod 4
[0, 1]
食い違い 0
0 0平方数を 4 で割った余りは 0 か 1 だけです。x を偶数と奇数に分けると、(2k)² = 4k²、(2k+1)² = 4(k² + k) + 1 だからです。ですから、4 で割って 3 余る数は平方数ではありません。
9 の倍数かどうかは、各桁の和が 9 の倍数かどうかと、10 万未満の数で食い違いが 0 でした。10 ≡ 1 (mod 9) なので、10^k ≡ 1 で、各桁にどの 10^k が掛かっていても余りは桁の和と同じになるからです。
余りの 負の -7 % 3 は 2 ですが、C や -7 % 3 は −1 です。Python は割る数と同じ符号に、C などは割られる数と同じ符号にそろえるからです。ほかの言語で 0 以上の余りが欲しいときは、((a % m) + m) % m と書きます。
割り算の 答えを 10^9+7 で割る問題で、(a × b ÷ c) を「a × b を余りにしてから c で割る」と、正しい答えになりません。割り算は、c の逆元を掛ける形に直します。10^9+7 は素数なので、c が 10^9+7 の倍数でなければ、逆元は c^(10^9+5) を 10^9+7 で割った余りとして、フェルマーの小定理から出せます。
桁あふれ C++ や Java の 64 ビットの整数では、10^9 程度の数どうしを掛けると約 10^18 で、上限の約 9.2 × 10^18 に近づきます。掛けるたびに余りを取らないと、数が上限を超えて答えが壊れます。Python の整数は桁があふれないので、この不具合は出ませんが、数が大きくなるほど計算は遅くなります。
仕事と 合同式と余りの計算が出てくる場面は、次の通りです。
答えを 10^9+7 で割る問題。組み合わせの数のように答えが巨大になる問題は、掛けるたびに余りを取り、割り算は逆元を掛ける ハッシュ。文字列を数に直し、表の大きさで割った余りを置き場所にする。文字列を、ある数の累乗を掛けて足した余りで比べるローリングハッシュは、比べる手間を減らす 暗号。RSA の暗号化と復号は、m^e を n で割った余りの計算で、繰り返し二乗法で速く出す。数は数百桁でも、掛け算は指数の桁数に比例する回数で済む 周期のある計算。曜日、時計、回す添字 (i % n) は、どれも余りの計算 確かめの数字。番号の打ち間違いを見つける確かめの数字は、余りを使って作られている物が多い よくある問い 合同式の a ≡ b (mod m) は「a と b は m を法として合同」と読みます。mod は modulo の略で、日本語では「モッド」や「モジュロ」と読むことが多いです。プログラムの % は、余りを返す演算子で、mod 演算とも呼ばれます。
合同式で 割る数と法が互いに素のときだけできます。そのときは、割る代わりに逆元を掛けます。互いに素でないときに割ると、6x ≡ 6 (mod 4) の x = 3 のように、答えを落とします。
繰り返し二乗法とは何ですか a^n を、a、a^2、a^4、a^8 と 2 乗を重ねた物の積に分けて求める手です。n を 2 進で書いたときの 1 の桁の物だけを掛けるので、掛け算は n 回ではなく、多くても 2 log2 n 回ほどで済みます。余りを取りながら行えば、数も大きくなりません。
剰余と 同じものを指します。剰余は割り算の余りのことで、剰余演算は余りを出す演算 (%) のことです。負の数の余りの決め方は言語によって違うので、負の数を割るときは確かめが要ります。
確認クイズ 答えだと
1 問目
3^100 を 7 で割った余りはどれですか。
2 問目
print(-7 % 3) を実行すると何が出ますか。
3 問目
合同式について、いつも正しいとは言えないのはどれですか。m は 2 以上の整数です。
ア a ≡ b (mod m) なら イ a ≡ b (mod m) なら ウ 2a ≡ 2b (mod m) なら エ a ≡ b (mod m) なら 説明課題 「a ≡ b (mod m) と c ≡ d (mod m) なら ac ≡ bd (mod m)」が成り立つ理由を、a = b + km の形を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
あなたの説明
模範解答 模範解答を開く 自分の
a と b は m で割った余りが同じなので、整数 k と l を使って a = b + km、c = d + lm と書ける。掛けると ac = bd + (bl + dk + klm) m となり、ac と bd の差は m の倍数である。差が m で割り切れるので、ac と bd は m で割った余りが同じで、ac ≡ bd (mod m) が成り立つ。
余りを
もっと深く この
一次資料 どれも 2026年 10月 30日 に開いて、題と中身を確かめました。
