合同式の基礎

概要

合同式について、合同式の意味、6つの性質、合同式が何の役に立つのかを記載する。

合同式とは

合同式とは、除算の余りに着目した等式のことである。

例えば、7と4は、どちらも3で除算した余りが1である。これを、合同式では、$7\equiv 4{\bmod {3}}$と記述する。
より一般に、aとbをnで除算した余りが等しいとき、合同式では、$a\equiv b{\bmod {n}}$

合同式の性質

合同式の性質を6つ記載する。特に4 - 6が重要である。

1. 合同式の和

$a\equiv b{\bmod {p}},c\equiv d{\bmod {p}}$のとき、$a+c\equiv b+d{\bmod {p}}$

例えば、${\bmod {3}}$では、$8\equiv 2{\bmod {3}},7\equiv 4{\bmod {3}}$なので、
$15\equiv 6{\bmod {3}}$が成立する。

2. 合同式の差

$a\equiv b{\bmod {p}},c\equiv d{\bmod {p}}$のとき、$a-c\equiv b-d{\bmod {p}}$

3. 合同式の積

$a\equiv b{\bmod {p}},c\equiv d{\bmod {p}}$のとき、$ac\equiv bd{\bmod {p}}$
特に、$ac\equiv bc{\bmod {p}}$をよく使用する。

4. 合同式の商

$ab\equiv ac{\bmod {p}}$で、aとpが互いに素ならば$b\equiv c{\bmod {p}}$が成立する。
合同式の両辺をaで除算できる条件は、aとpが互いに素である場合のみである。

合同式において、加算、減算、乗算は普通の等式と同様に行うことができるが、除算はaとpが互いに素という条件が付く。(重要)
証明は、互いに素の意味と関連する三つの定理の定理2を参照する。

5. 合同式のべき乗

$a\equiv b{\bmod {p}}$のとき、$a^{n}\equiv b^{n}{\bmod {p}}$

例 :
15¹⁰を4で除算した余りを求るとき、15¹⁰を計算するには時間が掛かるので、$15\equiv -1{\bmod {4}}$なので、
この性質を用いると、$15^{10}\equiv (-1)^{10}=1{\bmod {4}}$と簡単に求まる。

この合同式の性質の証明は、二項定理または$a^{n}-b^{n}$の因数分解により証明することができる。
→因数分解公式（n乗の和と差）

6. 合同式の多項式

$a\equiv b{\bmod {p}}$で、f(a)を整数係数多項式とするとき、$f(a)\equiv f(b){\bmod {p}}$
これは、合同式の性質1、3、5を組み合わせることで証明できる。

合同式を使うメリット

多くの整数問題の定理や性質は、合同式を用いることでスッキリとした形で記述することができる。

例 :
pが素数で、aがpと互いに素なとき、$a^{p-1}\equiv 1{\bmod {p}}$
→フェルマーの小定理の証明と例題

合同式を用いる難しい話題

合同式は、平方剰余、原始根、オイラーの定理、ウィルソンの定理、中国剰余定理など整数論の有名な定理の多くに登場する。