2: 2016-07-13 (水) 15:41:59 osinko |
3: 2016-07-15 (金) 00:27:31 osinko |
| TITLE:合同式 | | TITLE:合同式 |
| #jsmath | | #jsmath |
| + | **整数 [#nbd4f53e] |
| + | |
| + | -2以上の自然数\(\mathbb{N}\)はすべて素数(prime)と、その合成で出来ている。そして、その各々の数の合成に使う素数の構成は乗算する順番を除いて一意性を持っている&br;例:\(364={ 2 }^{ 2 }\times 7^{ 1 }\times 13^{ 1 }\) (4週間、7日、13ヵ月?) |
| + | -最大公約数が1の場合、「互いに素」の関係となる&br;例. 5と24は互いに素。 |
| + | |
| + | 最大公約数 gcd 、最小公倍数 lcm は素因数分解をすることで求めることが出来る。また「ユークリッドの互除法」を利用して最大公約数を求める事も出来るが元をたどった仕組み自体は素因数分解にある |
| + | |
| + | 例: 各素数の指数部の小さい方を掛け合わせると最大公約数に、大きい方を掛け合わせると最小公倍数になる |
| + | |
| + | \(84\quad =\quad { 2 }^{ 2 }\times 3^{ 1 }\times 5^{ 0 }\times 7^{ 1 }\times 11^{ 0 }\\ 550\quad ={ \quad 2 }^{ 1 }\times 3^{ 0 }\times 5^{ 2 }\times 7^{ 0 }\times 11^{ 1 }\) |
| + | |
| + | \(gcd\left( 84,50 \right) \quad =\quad { 2 }^{ 1 }\times 3^{ 0 }\times 5^{ 0 }\times 7^{ 0 }\times 11^{ 0 }\quad =\quad 2\\ lcm\left( 84,50 \right) \quad =\quad { 2 }^{ 2 }\times 3^{ 1 }\times 5^{ 2 }\times 7^{ 1 }\times 11^{ 1 }\quad =\quad 23100\) |
| + | |
| + | ユークリッドの互除法は商(quotient)と余り(remainder)を交互に書き換えながら計算して余りが0になるまで計算すると求められる |
| + | |
| + | (TODO) |
| + | |
| **合同式 [#e59589c1] | | **合同式 [#e59589c1] |
| | | |
| | | |
| のように表せる。つまり元の数から\(3\)引き算しないと\(9\)では割り切れない。3では割り切れる という事がこれで説明できる | | のように表せる。つまり元の数から\(3\)引き算しないと\(9\)では割り切れない。3では割り切れる という事がこれで説明できる |
| + | |
| + | **同値類 [#t36ac80e] |
| + | |
| + | <問題> |
| + | \(\mathbb{Z}/\left( 5 \right) \)の同値類 \(C\left( x \right) \quad \left( 0\le x\le 4 \right) \) の乗算表を作りなさい |
| + | |
| + | 整数の集合\(\mathbb{Z}\)に対して5で割り切れる0~4の余りを持つ同値類の集合を作る。その集合を表すと以下になる |
| + | |
| + | \(\mathbb{Z}/\left( 5 \right) \quad =\quad \left\{ C\left( 0 \right) ,C\left( 1 \right) ,C\left( 2 \right) ,C\left( 3 \right) ,C\left( 4 \right) \right\} \\ C\left( 0 \right) =\quad \left\{ 5k+0|k\in \mathbb{Z} \right\} \quad =\quad \left\{ \cdots ,-10,-5,0,5,10,15,\cdots \right\} \\ C\left( 1 \right) =\quad \left\{ 5k+1|k\in \mathbb{Z} \right\} \quad =\quad \left\{ \cdots ,-9,-4,1,6,11,16,\cdots \right\} \\ C\left( 2 \right) =\quad \left\{ 5k+2|k\in \mathbb{Z} \right\} \quad =\quad \left\{ \cdots ,-8,-3,2,7,12,17,\cdots \right\} \\ C\left( 3 \right) =\quad \left\{ 5k+3|k\in \mathbb{Z} \right\} \quad =\quad \left\{ \cdots ,-7,-2,3,8,13,18,\cdots \right\} \\ C\left( 4 \right) =\quad \left\{ 5k+4|k\in \mathbb{Z} \right\} \quad =\quad \left\{ \cdots ,-6,-1,4,9,14,19,\cdots \right\} \) |
| + | |
| + | 整数全体を「性質」により5つの集合に分け同値類としている。同値類を作るには3つの条件を満たす必要がある。反射性、対称性、推移性。これらを満たせば2項演算子(×とか+とかそういう演算子の事)により同値関係同士の演算が可能となる。ここでは条件はとりあえず飛ばして、乗算で同値類の計算結果の表を作ってみる |
| + | |
| + | *** \(\mathbb{Z}/\left( 5 \right) \)での積 [#y6313a24] |
| + | | |C(0)|C(1)|C(2)|C(4)|C(4)| |
| + | |C(0)|C(0)|C(0)|C(0)|C(0)|C(0)| |
| + | |C(1)|C(0)|C(1)|C(2)|C(3)|C(4)| |
| + | |C(2)|C(0)|C(2)|C(4)|C(1)|C(3)| |
| + | |C(3)|C(0)|C(3)|C(1)|C(4)|C(2)| |
| + | |C(4)|C(0)|C(4)|C(3)|C(2)|C(1)| |
| + | |
| + | <例> |
| + | 行C(2)、列C(3)の積を計算してみる |
| + | |
| + | C(2)の集合から合同式を作る |
| + | \(2\equiv 7\quad (mod5)\) |
| + | |
| + | C(3)の集合から合同式を作る |
| + | \(3\equiv 8\quad (mod5)\) |
| + | |
| + | \(C(2)\times C(3)\quad =\quad 2\times 3\equiv 7\times 8\quad (mod5)\) |
| + | \(\left\{ 6,56 \right\} \in C(1)\) なので積の計算の結果はC(1)の同値類となる事がわかる |