合同式の基礎のソースを表示

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

== 合同式とは ==
合同式とは、除算の余りに着目した等式のことである。<br>
<br>
例えば、7と4は、どちらも3で除算した余りが1である。これを、合同式では、<math>7 \equiv 4 \bmod 3</math>と記述する。<br>
より一般に、aとbをnで除算した余りが等しいとき、合同式では、<math>a \equiv b \bmod n</math><br>
<br><br>

== 合同式の性質 ==
合同式の性質を6つ記載する。特に4 - 6が重要である。<br>
<br>
===== 1. 合同式の和 =====
<math>a \equiv b \bmod p, c \equiv d \bmod p</math>のとき、<math>a + c \equiv b + d \bmod p</math><br>
<br>
例えば、<math>\bmod 3</math>では、<math>8 \equiv 2 \bmod 3,  7 \equiv 4 \bmod 3</math>なので、<br>
<math>15 \equiv 6 \bmod 3</math>が成立する。<br>
<br>
===== 2. 合同式の差 =====
<math>a \equiv b \bmod p, c \equiv d \bmod p</math>のとき、<math>a - c \equiv b - d \bmod p</math><br>
<br>
===== 3. 合同式の積 =====
<math>a \equiv b \bmod p, c \equiv d \bmod p</math>のとき、<math>ac \equiv bd \bmod p</math><br>
特に、<math>ac \equiv bc \bmod p</math>をよく使用する。<br>
<br>
===== 4. 合同式の商 =====
<math>ab \equiv ac \bmod p</math>で、<u>'''aとpが互いに素'''</u>ならば<math>b \equiv c \bmod p</math>が成立する。<br>
合同式の両辺をaで除算できる条件は、aとpが互いに素である場合のみである。<br>
<br>
合同式において、加算、減算、乗算は普通の等式と同様に行うことができるが、除算はaとpが互いに素という条件が付く。(重要)<br>
証明は、互いに素の意味と関連する三つの定理の定理2を参照する。<br>
<br>
===== 5. 合同式のべき乗 =====
<math>a \equiv b \bmod p</math>のとき、<math>a^n \equiv b^n \bmod p</math><br>
<br>
例 :<br>
15<sup>10</sup>を4で除算した余りを求るとき、15<sup>10</sup>を計算するには時間が掛かるので、<math>15 \equiv -1 \bmod 4</math>なので、<br>
この性質を用いると、<math>15^{10} \equiv (-1)^{10} = 1 \bmod 4</math>と簡単に求まる。<br>
<br>
この合同式の性質の証明は、二項定理または<math>a^n - b^n</math>の因数分解により証明することができる。<br>
→因数分解公式（n乗の和と差）<br>
<br>
===== 6. 合同式の多項式 =====
<math>a \equiv b \bmod p</math>で、f(a)を整数係数多項式とするとき、<math>f(a) \equiv f(b)\bmod p</math><br>
これは、合同式の性質1、3、5を組み合わせることで証明できる。<br>
<br><br>

== 合同式を使うメリット ==
多くの整数問題の定理や性質は、合同式を用いることでスッキリとした形で記述することができる。<br>
<br>
例 :<br>
pが素数で、aがpと互いに素なとき、<math>a^{p - 1} \equiv 1 \bmod p</math><br>
→フェルマーの小定理の証明と例題<br>
<br><br>

== 合同式を用いる難しい話題 ==
合同式は、平方剰余、原始根、オイラーの定理、ウィルソンの定理、中国剰余定理など整数論の有名な定理の多くに登場する。<br>
<br><br>

__FORCETOC__
[[カテゴリ:暗号理論]]