Wiki: Wiki がページ「合同式の意味と性質」を「合同式の基礎」に、リダイレクトを残さずに移動しました

2020-03-06T14:36:42Z

Wiki がページ「合同式の意味と性質」を「合同式の基礎」に、リダイレクトを残さずに移動しました

← 古い版		2020年3月6日 (金) 23:36時点における版
(相違点なし)

Wiki: ページの作成:「== 概要 == 合同式について、合同式の意味、6つの性質、合同式が何の役に立つのかを記載する。

== 合同式とは == 合…」

2020-03-06T13:32:29Z

ページの作成:「== 概要 == 合同式について、合同式の意味、6つの性質、合同式が何の役に立つのかを記載する。 == 合同式とは == 合…」

新規ページ

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

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

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

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

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

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

合同式の基礎 - 版の履歴

Wiki: Wiki がページ「合同式の意味と性質」を「合同式の基礎」に、リダイレクトを残さずに移動しました

Wiki: ページの作成:「== 概要 == 合同式について、合同式の意味、6つの性質、合同式が何の役に立つのかを記載する。 == 合同式とは == 合…」

Wiki: ページの作成:「== 概要 == 合同式について、合同式の意味、6つの性質、合同式が何の役に立つのかを記載する。

== 合同式とは == 合…」