合同式の定義と基本的性質

どうして合同式を学ぶのか

例えば, $231^{4000}$の1の位の数字を求めるような問題は素直に$231^{4000}$を計算していたのでは到底時間が足りません｡そこで, ｢1の位を求める｣ということを｢$10$で割った余りを求める｣のように言い換えると, これは余りの問題になります｡そして合同式の理論を用いると$231^{4000}$を直接計算するのに比べてはるかに少ない計算量で答えを求めることができます｡ (ちなみにこの問題の答えはこの記事を読んだらわかります｡)

素数判定や暗号の理論にも必須の合同式なのでしっかり理解しましょう｡

合同式の定義

$a, b$を整数, $n$を自然数としましょう｡ $a-b$が$n$で割り切れるときのとき \[a\equiv b \pmod n\] と書きます｡

modはmodulo(モジュロ)の略でモッドやモドなどと発音します｡ $a\equiv b \pmod n$は

$a$と$b$は法(ほう)を$n$として合同
$a$ 合同 $b$ モッド $n$ などと読んだりします｡

この等号(=)に似た記号($\equiv$)を使うのは理由があります｡以下でみるように合同($\equiv$)は等号のような性質をもっているのです｡まずは定義に従って次の例を見てみましょう｡

合同式の例

A. 次の合同式が正しいかどうか判断してみてください｡

$42 \equiv 36 \pmod 3$
$28 \equiv 6 \pmod {13}$
$4 \equiv -15 \pmod {19}$

B. 次の式を満たすような$x$を3つ見つけましょう｡ \[ x \equiv 7 \pmod 3 \]

例の解答

まずA1の問題は, $42-36=6$となり差$6$が法$3$で割り切れるので正しいことがわかります｡

問題A2は$28-6=22$を$13$が割り切らないので正しくありません｡このとき$28 \not \equiv 6 \pmod {13}$と書きます｡

問題A3は$4-(-15)=19$が$19$で割り切れるので正しい式です｡

問題Bは$x-7$が$3$で割り切れるような整数$x$を探し出します｡ $3\mid x-7$は$x-7=3n$ ($n$は整数)と同値です｡ここから$x=3n+7$と書けます｡例えば$n= 1, 2, 3$とした$x=10, 13, 16$が$x\equiv 7 \pmod 3$を満たします｡ (ここで$n$はどんな整数でもいいので無限に多くの正しい解答があります｡)

時計の計算

1から12までの数字が書かれているアナログ時計を思い浮かべてください｡ (もしくは部屋の時計を見てください｡) あなたは朝7時から完全数が無限個あることを証明しようと机に向かいました｡ご飯も食べず, 休憩もせずにずっと考えたり, 計算してみたりと机に座っていました｡ふと時計をみるとまだ針は7時を指しています｡どうしてでしょう?

色々な答えがあると思いますが, ありえそうなのは実は午後7時だった, または次の日の朝7時だった, などかと思います｡時計盤からは午前か午後かの情報が読み取れないのです｡午前7時から半日後(12時間後)が午後7時ですが時計の針は同じ場所｡それが一日後(24時間後)でも同じです｡午後7時のことを19時と言ったりします｡それは7時から12時間後なので$7+12=19$だからです｡でも時計では19時は7時と同じなのです｡同様に23時は時計では11時と同じです｡このように時計で時間を扱うときに私達は法12の計算をしているのです｡つまり, $19 \equiv 7 \pmod{12}$や$23\equiv 11 \pmod{12}$の計算をしているのです｡

実世界では時計には1から12までの数字が書かれていますが, $a \equiv b \pmod{n}$の合同式は1から$n$までの数字が書かれた時計で計算しているとも言えます｡

合同式の基本的な性質

定理: 合同式の同値な命題

$a, b$を整数, $n$を自然数としたとき次の2つは同値である｡

$a\equiv b \pmod n$
$a$を$n$で割った余りは$b$を$n$で割った余りに等しい｡

2つの命題Aと命題Bが同値とは, $A$が正しいならば$B$も正しい($A\implies B$)かつ$B$が正しいならば$A$がも正しい($B \implies A$)となっていることを言います｡

証明

まず1つ目の命題$a\equiv b \pmod n$を仮定します｡すると合同式の定義より, $n \mid a-b$であるから, とある整数$k$が存在して$a-b=kn$と書けます｡ $b$を移行して$a=kn+b$を得ます｡さて, $b$を$n$で割った商を$q$余りを$r$としましょう｡つまり$b=qn+r$とします｡この$b$を上で得た$a$の式に代入すると \[\begin{align*}
a &= kn + b\\
&=kn + qn+r\\
&=(k+q)n+r
\end{align*}\] となります｡最後の式は$a$を$n$で割った余りも$r$であることを示しています｡つまり2つ目の命題が導かれました｡

逆に今度は命題2を仮定します｡ $n$で$a, b$を割った余りを$r$としましょう｡ (余りが同じなので両方とも$r$｡) 商をそれぞれ$p, q$とすると \[ a = pn + r, b = qn + r\] と書けます｡これらの差を計算すると \[ a – b = (pn+r)-(qn+r) = (p-q)n\] となり, $n \mid a-b$となることがわかります｡つまり$a \equiv b \pmod n$が成立しています｡ゆえに命題1も正しいことになります｡

以上で証明を終わりにしたいと思います｡

等号$=$のような合同式$\equiv$

これから通常の$=$で成立している事実の多くが$\equiv$に置き換えても成立することをみていきます｡

定理: 合同式の同値関係

$a, b, c \in \Z$, また$n\in \N$とします｡すると次が成り立ちます｡

(反射律) $a \equiv a \pmod n$
(対称律) $a \equiv b \pmod n$ ならば $b \equiv a \pmod n$
(推移律) $a \equiv b \pmod n$ かつ $b \equiv c \pmod n$ ならば $a \equiv c \pmod n$

これら3つの関係のことを同値関係という｡

同値関係は等号$=$が満たす, もっとも基礎的な性質です｡

証明

どれも合同式の定義を使うことで証明できます｡まずは定義の理解を試すのを兼ねて, ご自分で挑戦してみてください｡

反射律の証明｡これは$a-a=0$を$n$が割り切ることから従います｡

対称律の証明｡ $a \equiv b \pmod n$ならば$n \mid a – b$であるから$a-b=kn$となる整数$k$が存在します｡両辺に$-1$を掛けると$b-a=(-k)n$となり$n\mid b-a$が成立することから$b\equiv a \pmod n$を得ます｡

推移律の証明｡ $a \equiv b \pmod n$ と $b \equiv c \pmod n$ を仮定します｡つまり$n \mid a-b$ と $n\mid b-c$が成り立っています｡すると$a-b = sn$, $b-c = tn$となるような整数$s, t$が存在します｡ここから \[ a-c = (a -b) + (b -c) =sn+tn=(s+t)n\] を得るので$n \mid a-c$, つまり$a\equiv c \pmod n$が成立します｡

これで証明を終わりにしたいと思います｡

合同式を使った演算

通常の等号$=$では様々な計算を行えます｡例えば, 両辺に同じ数を足したり掛けたり｡合同式でも同じような計算が行えることを証明していきます｡

定理: 合同式の和と積

$a, b, c, d\in \Z$, また$n\in \N$とします｡もし$a\equiv b \pmod n$と$c\equiv d \pmod n$が成り立つなら

$a+c \equiv b +d \pmod n$
$ac \equiv bd \pmod n$

が成り立つ｡

証明

$a\equiv b \pmod n$と$c\equiv d \pmod n$を仮定すると$a-b=sn$と$c-d=tn$となる整数$s, t$が存在する｡ $b, d$をそれぞれ移行して \[ a=b+sn, c= d+tn\] を得る｡これらを足し合わせると \[ a + c = (b+sn)+(d+tn) =b+d + (s+t)n \] となり, ここから \[ (a+c)-(b+d)=(s+t)n\] となるから1つ目の式$a+c \equiv b +d \pmod n$を得ることができます｡

今度は上記の$a$と$b$の式を掛け合わせます｡すると \[\begin{align*}
ac &=(b+sn)(d+tn)\\
&=bd + btn + dsn +stn^2\\
&=bd + (bt+sd+stn)n
\end{align*}\] となることから \[ac – bd =(bt+sd+stn)n\] となり, 二番目の式$ac \equiv bd \pmod n$を得ることができます｡

これで証明を終わりにしたいと思います｡

練習問題

次の数を10で割った余りを求めてみましょう｡

$23 + 5711 + 1317$
$23 \cdot 5711 \cdot 1317$

練習問題の解答

直接足し算や掛け算を計算してから10で割って余りを求めてもいいのですが, ここでは数字がもっと大きくなっても使える方法で解いてみましょう｡ポイントは上の定理です｡

まず自然数$n$を$10$で割った余りというのは$n \equiv x \pmod{10}$となる$0\leq x <10$を求めることと同じです｡

では一問目から解いていきましょう｡ここでは足し算を先に行うのではなく, まずそれぞれの数のmod 10を計算していきます｡

\[\begin{align*}
23 &\equiv 3 \pmod{10}\\
5711 &\equiv 1 \pmod{10}\\
1317 &\equiv 7 \pmod{10}
\end{align*}\]

10で割った余りは数字の一桁目ということを使いました｡ではこれらと上の定理を使って計算しましょう｡

\[\begin{align*}
23 + 5711 + 1317 &\equiv 3 + 1 + 7 \pmod{10} &&\text{ここで定理を使いました}\\
&\equiv 11 \pmod {10}\\
&\equiv 1 \pmod {10}
\end{align*}\]

ゆえに余りが1であることがわかりました｡

同様に二番目の余りも求めると \[\begin{align*}
23 +\cdot 5711 \cdot 1317 &\equiv 3 \cdot 1 \cdot 7 \pmod{10} &&\text{ここで定理を使いました}\\
&\equiv 21 \pmod {10}\\
&\equiv 1 \pmod {10}
\end{align*}\] となり, こちらも余りが1になることがわかりました｡

このように与えられた式を計算することなく余りの計算ができるようになるのが上記の定理のいいところです｡

合同式のべき乗

定理: 合同式のべき乗

$a, b\in \Z$と$n\in \N$とすし$a\equiv b \pmod n$が成立しているとする｡このとき$a^k\equiv b^k \pmod n$が任意の自然数$k$で成立する｡

証明

$k$に関する数学的帰納法で証明します｡ $k=1$のときは仮定よりすでに成り立っています｡

次に$k=m$のときに成り立つと仮定して$k=m+1$でも成り立つことを証明しましょう｡ $k=m$の仮定から$a^m\equiv b^m \pmod n$が成立しています｡もともとの仮定から$a\equiv b \pmod{n}$も成り立っています｡これらを掛け合わすと先ほどの定理より \[ a^m\cdot a \equiv b^m \cdot b \pmod{n}\] を得ます｡これはつまり$a^{m+1}\equiv b^{m+1} \pmod n$と同値なので$k=m+1$の場合も成立することがわかりました｡ゆえに数学的帰納法よりすべての自然数$k$で$a^k \equiv b^k \pmod n$が成立することが証明されました｡以上で証明を終わりにしたいと思います｡

練習問題

$231^{4000}$を10で割った余りを求めてください｡

練習問題の解答

$231^{4000}$を計算してから10で割ろうとすると, とてつもなく計算が大変です｡そこで今証明した定理を利用しましょう｡ $231\equiv 1 \pmod{10}$の両辺を$4000$乗すると \[ 231^{4000} \equiv 1^{4000} \equiv 1 \pmod{10}\] となり余りが1となることがわかりました｡

$3$の倍数かどうかをチェックする方法

自然数が与えられたときに, それが3の倍数かどうかをどうやって判断しますか? ｢各桁を足した数が3の倍数であればもとの数も3の倍数｣という判断方法を知っているかもしれません｡例えば, 4092の場合には$4+9+2=15$で$3\mid 15$より$4092$も3の倍数ということがわかります｡ではどうしてこの方法で判断できるのか見ていきましょう｡

自然数$n$が3の倍数とは$n\equiv 0 \pmod 3$と同値です｡私たちが普段使っている数字は10進法と呼ばれてる表記を使っています｡これはどんな自然数$n$も \[ n = a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1} +\cdots + a_2\cdot 10^2 + a_1 \cdot 10 + a_0\] と書くことができ, これら$a_k, a_{k-1}, \cdots, a_2, a_1, a_0$を並べたものが$n=a_ka_{k-1}\cdots a_2a_1a_0$となっています｡ (ここで右辺は掛け算ではなく数字を横に並べただけです｡ )つまり$a_i$たちは$n$の各桁に現れる数です｡例えば$4092= 4\cdot 10^3+0\cdot 10^2+9\cdot 10 +2$となっているので$a_3=4, a_2=0, a_1=9, a_0=2$です｡

では, 自然数$n$が3の倍数であるには$n$の各桁の合計が3の倍数であればよいことを証明します｡ \[ n = a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1} +\cdots + a_2\cdot 10^2 + a_1 \cdot 10 + a_0\] と書きましょう｡つまり, $a_i$が$n$の各桁の数字です｡ $10 \equiv 1 \pmod 3$だから先ほどの定理を使うと$10^i\equiv 1^i \equiv 1 \pmod 3$が任意の自然数$i$に対して成り立っています｡これを使うと

\[\begin{align*}
n &= a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1} +\cdots + a_2\cdot 10^2 + a_1 \cdot 10 + a_0 \\
&\equiv a_k\cdot 1+a_{k-1}\cdot 1 +\cdots + a_2\cdot 1 + a_1 \cdot 1 + a_0 \pmod 3\\
&\equiv a_k+a_{k-1} +\cdots +a_2 + a_1 + a_0 \pmod 3
\end{align*}\]

となります｡ここで最後の右辺$a_k+a_{k-1} +\cdots +a_2 + a_1 + a_0$は$n$の各桁の数字の合計です｡これが3の倍数ならばこれが$\equiv 0 \pmod 3$となります｡そして上の等式により, $n\equiv 0 \pmod 3$となることから$n$も3の倍数になることが証明されました｡

9の倍数の判定法

今見た3の倍数の判定と同様に9の倍数の判定法もあります｡これはの練習問題としますので, ぜひどんな判定法になるか, またその判定法でなぜうまくいくか考えてみてください｡

11の倍数の判定法

11の倍数を判定する方法もあります｡こちらは3の倍数のときとは少し違いますが, 考え方は同じです｡法を11として考えて見ましょう｡

まず$10 \equiv -1\pmod {11}$となっています｡次は$10^2\equiv 1 \pmod{11}$です｡これらを掛け合わせると$10^3\equiv -1 \pmod {11}$となり, さらに次は$10^4 \equiv 1 \pmod{11}$となります｡このように10の指数が奇数の場合は$-1$, 偶数の場合は$1$と合同になります｡つまり$10^i\equiv (-1)^i \pmod {11}$となっています｡

以前と同様に, $n$の各桁を$a_i$で表すと \[\begin{align*}
n &= a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1} +\cdots + a_2\cdots 10^2 + a_1 \cdot 10 + a_0 \\
&\equiv a_k\cdot (-1)^k+a_{k-1}\cdot (-1)^{k-1} +\cdots + a_2\cdot 1 a_1 \cdot (-1) + a_0 \pmod {11}
\end{align*}\]

よって, $n$の各桁の交互に符号が変わる和が$11$で割り切れれば$n$も$11$で割り切れることになります｡

もうひとつ付け加えると符号$\pm$がプラスかマイナスのどちらから始まっても構いません｡これは$a\equiv 0 \pmod{n}$なら$-a\equiv 0 \pmod{n}$であることから従います｡

11の倍数の判定法の例

では$38291$が$11$の倍数であることを確かめてみます｡各桁の符号を交互にした和は$3-8+2-9+1=-11$で, これは$11$で割り切れるので$38291$も$11$で割り切れることがわかりました｡

Pythonで倍数の判定法を書いてみよう

さて, これら倍数の判定法をPythonで書いてみましょう｡どの判定法も与えられた自然数の桁の数字を使う必要があるので, まずはそれを出力する関数を作ることから始めてみよう｡

def digits_of (n): # nの桁の数字のリストを出力する関数｡ nは自然数
    digits = [] # nの桁の数字を入れるリスト
    while n != 0:
        r = n % 10 # 10で割った余り
        digits.append(r) # リストに加える
        n = n // 10 # nを10で割った整数に置き換える
    return digits

試しに$n=12345$で動かしてみると

digits_of(12345)

結果は[5, 4, 3, 2, 1]と一のくらいの数字からリストされて出てきます｡これでも問題ないのですが, 逆順のリストが欲しい場合は.reverse()をリストの後ろにつければOKです｡

def digits_of2 (n):
    digits = []
    while n != 0:
        r = n % 10
        digits.append(r)
        n = n // 10
    digits.reverse() # リストを逆順にする
    return digits

さて, この関数(どちらのバージョンでもOK)を使って3の倍数の判定法を書いてみよう｡

3の倍数の判定法 in Python

def is_multiple_of_3 (n): # nは自然数
    sum = 0 # 各桁の数字の合計をもとめる
    for i in digits_of (n):
        sum += i
    if sum % 3 == 0: # もし合計が3の倍数ならTrue
        return True
    else:
        return False

このコードのif文ですが, 条件のsum % 3 == 0の結果をそのまま返しているので, もっとシンプルにreturn sum % 3 == 0とできます｡よって上のコードを書き換えると

def is_multiple_of_3 (n): # nは自然数
    sum = 0 # 各桁の数字の合計をもとめる
    for i in digits_of (n):
        sum += i
    return sum % 3 == 0 # もし合計が3の倍数ならTrue, そうでないならFalse

となります｡

11の倍数の判定法 in Python

次は11の倍数の判定法を書いてみます｡符号を交互に変えて各桁の数字の合計を求めるところが3の倍数の判定法との違いでした｡いくつか方法がありますが, 一例を書きたいと思います｡

def is_multiple_of_11 (n): # nは自然数
    sum = 0 # 各桁の交互和を求める
    exp = 0 # 符号を交互にするための指数
    for i in digits_of (n):
        sum += (-1) ** exp * i
        exp += 1 # 指数を1増やす=符号を変える
    return sum % 11 == 0  # 交互和が11で割り切れるならTrue, そうでないならFalse

合同式の割り算はちょっと気をつけて

合同式の計算において, 通常の等号$=$を使ったように足し算(と引き算)や掛け算がうまくいくことをみました｡ただ, 割り算だけは一筋縄ではいかないのです｡例を見てみましょう｡

例えば, $72 \equiv 12 \pmod {15}$は正しい式です｡また, 両辺を$4$で割った$18 \equiv 3 \pmod {15}$も正しい式です｡ここからさらに両辺を$3$で割ってみると$6 \equiv 1 \pmod {15}$となりそうですが, $15\nmid 6-1$なので間違っています｡

ここから$a \equiv b \pmod n$の式で$a$と$b$が同じ数$c$で割り切れるからと言って必ずしも両辺を$c$で割っていいとは限らないということです｡ではいつ両辺を割っていいのでしょう｡答えは次の定理で与えられています｡

定理: 合同式の除算に関する条件

$a, b, c \in Z$と$n\in \N$が$ac \equiv bc \pmod n$を満たすとします｡このとき, もし$\gcd(c, n)=1$ならば$a \equiv b \pmod n$となる｡

$\gcd(c, n)$は$c$と$n$の最大公約数でしたね｡このように最大公約数が1のとき, 2つの整数は互いに素といいます｡証明の前に先ほどの例を振り返ると, 最初に$4$で割れたのは$\gcd(4, 15)=1$となっているからでした｡ 2つ目の$3$で割ることができなかったのでは$\gcd(3,15)=3 \neq 1$で$3$と$15$が互いに素ではなかったからだと定理からわかります｡

証明

与えられた合同式$ac \equiv bc \pmod n$から$n \mid ac -bc$, つまり, $n \mid (a-b)c$を得ます｡ここで$\gcd(c, n)=1$と仮定すると$n\mid a-b$となります｡ (ここをもう少し知りたい方は後述の補題を読んでください｡) よって$a \equiv b \pmod n$が成立します｡これで証明を終わりにしたいと思います｡

補題とその証明

それでは上の証明に使った事実を補題として証明したいと思います｡

補題

$a, b\in \Z$と$n\in \N$が$n \mid ab$かつ$\gcd(b, n)=1$を満たしているとする｡すると$n \mid a$が成り立つ｡

証明

補題の証明には算術の基本定理(素因数分解の存在と一意性)を用います｡

$n$の素因数分解を$n=\prod_{i=1}^kp_i^{\alpha_i}$と書きましょう｡では仮に$n \nmid a$としてみましょう｡すると$a$の素因数分解の中に$p_i$が$\alpha_i$個より少ないような$i$が存在します｡ (そのような$i$がなければ$n \mid a$となります｡) しかし$n\mid ab$であるから, 不足分の$p_i$は$b$の素因数解から補わなくてはなりません｡つまり$p_i \mid b$となり, $p_i$が$n$と$b$の両方を割ることになり$\gcd(b,n)=1$であることに矛盾します｡ゆえに$n \mid a$となります｡以上で証明を終わりにしたいと思います｡

次回は合同数を完全数に応用します

今回は合同式の基礎を学びました｡足し算, 引き算, 掛け算は通常の等号に似た計算ができること, また割り算は割る数と法が互いに素のときには可能なことを学びました｡次回は合同数を応用して完全数の1桁目の謎を解明したいと思います｡

合同式の定義と基本的性質

どうして合同式を学ぶのか

合同式の定義

合同式の例

例の解答

時計の計算

合同式の基本的な性質

証明

等号\(=\)のような合同式\(\equiv\)

証明

合同式を使った演算

証明

練習問題

練習問題の解答

合同式のべき乗

証明

練習問題

練習問題の解答

\(3\)の倍数かどうかをチェックする方法

9の倍数の判定法

11の倍数の判定法

11の倍数の判定法の例

Pythonで倍数の判定法を書いてみよう

3の倍数の判定法 in Python

11の倍数の判定法 in Python

合同式の割り算はちょっと気をつけて

証明

補題とその証明

証明

次回は合同数を完全数に応用します

練習問題で実力をつけましょう｡

前のトピック

メルセンヌ素数について

次のトピック

偶数完全数の一の位の数

これまでのトピック

完全数の性質と未解決問題

Pythonモジュール｢SymPy｣の数論に関する関数の使い方

Pythonのモジュールを使おう

Pythonの基礎をマスターしよう