合同式とは、割り算の余りが等しいことを示した等式のことです。
合同式
合同式とは
合同式とは、割り算の余りが等しいことを示した等式のことです。
例えば、「\(9\) を \(4\) で割った余り」と「\(5\) を \(4\) 割った余り」は、
\(9\div 4=2\cdots 1\)
\(5\div 4=1\cdots 1\)
となり等しいので、
\(9\equiv 5\) (mod \(4\))
と書くことができて、読み方は「\(9\) 合同 \(5\) モッド \(4\)」となります。
これを一般的に書くと、\(a\) と \(b\) を \(n\) で割った余りが等しい時、
\(a\equiv b\) (mod \(n\))
と表すことができます。
「\(a\) と \(b\) を \(n\) で割った余りが等しいとき」という条件は、「\(a-b\) が \(n\) の倍数のとき」と言い換えることができます。
合同式の性質
\(a\equiv b\) (mod m), \(c\equiv d\) (mod m) のとき、次のことが成り立つ。
① \(a+c\equiv b+d\) (mod \(m\))
② \(a-c\equiv b-d\) (mod \(m\))
③ \(ac\equiv bd\) (mod \(m\))
④ 自然数 \(n\) に対し \(a^n\equiv b^n\) (mod \(m\))
① 合同式の和について
例えば、 mod \(3\) では
\(11\equiv 5\), \(5\equiv 2\) なので、辺々を足し算して
\(16\equiv 7\)
が成立します。
② 合同式の差について
例えば、 mod \(3\) では
\(11\equiv 5\), \(5\equiv 2\) なので、辺々を引き算して
\(6\equiv 3\)
が成立します。
③ 合同式の積について
例えば、 mod \(3\) では
\(11\equiv 5\), \(5\equiv 2\) なので、辺々を掛け算して
\(55\equiv 10\)
が成立します。
④ 合同式のべき乗について
例えば、 mod \(3\) では
\(11\equiv 5\) なので、辺々を \(2\) すると
\(121\equiv 25\)
が成立します。
合同式の問題
\(13^{100}\) を \(9\) で割った余を求めなさい。
＞＞詳細はこちらから
合同式の問題の解説
\(13^{100}\div 9=\) (商) \(\cdots\) (余り)
\(13^{100}=9\times\) (商) \(+\) (余り)
\(13^{100}-\) (余り) \(=9\times\) (商)
よって、
\(13^{100}\equiv\) (余り) (mod \(9\))
この形を目標にする。
「\(13^{100}\)」のままだと太刀打ちできないので、「\(13\)」という数字を使って合同式を作ってみる。
\(13\equiv4\) (mod \(9\))
公式より、
\(13^{100}\equiv 4^{100}\) (mod \(9\)) \(\cdots\) ①
ここで、
\(4^3\equiv 1\) (mod \(9\))
なので、
\((4^3)^{33}\equiv 1\) (mod \(9\))
\((4^3)^{33}\cdot 4\equiv 4\) (mod \(9\))
\(4^{100}\equiv 4\) (mod \(9\)) \(\cdots\) ②
①, ② より
\(13^{100}\equiv 4^{100}\equiv 4\) (mod \(9\))
したがって、
\(13^{100}\equiv 4\) (mod \(9\))
となり、余りは \(4\)
おわりに
さいごまで読んでいただきありがとうございました！
『統計の扉』で書いている記事
- 高校数学の解説
- 公務員試験の数学
- 統計学（統計検定2級レベル）
ぜひご覧ください！
数学でお困りの方は、コメントやXでご連絡ください。（Xはこちら）
私自身、数学が得意になれたのはただ運が良かったんだと思っています。たまたま親が通塾させることに積極的だったり、友達が入るって理由でそろばんに入れたり、他の科目が壊滅的だったおかげで数学が(相対的に)得意だと勘違いできたり。
”たまたま”得意になれたこの恩を、今数学の学習に困っている人に還元できたらなと思っています。お金は取りません。できる限り(何百人から連絡が来たら難しいかもですが…)真摯に向き合おうと思っていますのでオアシスだと思ってご連絡ください。