合同式ごうどうしきcongruenceと mod 演算えんざんoperation

合同式ごうどうしきを「余あまりが同おなじ」という計算けいさん規則きそくだけで見みると、何故なぜ足たし算ざんや掛かけ算ざんが正当化せいとうかされるのかが見みえにくい。抽象代数ちゅうしょうだいすうでは、合同式ごうどうしきを剰余類じょうよるいの等号とうごうとして見みる。

とは、

という意味いみであり、同時どうじに $$a$$a と $$b$$b が同おなじ剰余類じょうよるいに属ぞくするという意味いみでもある。

congruence合同式ごうどうしき and mod operation演算えんざん

If congruences合同式ごうどうしき are viewed only as the calculation rule "the remainders are the same," it is hard to see why addition and multiplication are justified. In abstract algebra抽象代数ちゅうしょうだいすう, a congruence合同式ごうどうしき is viewed as equality of residue classes剰余類じょうよるい.

means

and at the same time means that $$a$$a and $$b$$b belong to the same residue class.

1剰余類じょうよるい全体ぜんたい

$$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge 2 とする。整数全体せいすうぜんたいを $$n$$n で割わった余あまりによって分類ぶんるいすると、商集合しょうしゅうごう

が得えられる。この集合しゅうごうの元げんは整数せいすうではなく、整数せいすうの同値類どうちるいである。

ここでの商集合しょうしゅうごうとは、同おなじ余あまりを持もつ整数せいすうを一ひとつの類るいにまとめ、その類るいを元げんとして扱あつかう集合しゅうごうである。

1The set of residue classes

Let $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge 2. Classifying all integers by their remainders modulo $$n$$n gives the quotient set商集合しょうしゅうごう

The elements of this set are not integers themselves, but equivalence classes of integers.

Here the quotient set is the set obtained by grouping integers with the same remainder into one class and then treating those classes as the elements.

この講義こうぎでは法ほう $$n$$n を固定こていし、$$[a{]}_n$$[a]_n を $$\left[a\right]$$[a] と略記りゃくきする。法ほうを変かえると剰余類じょうよるいも変かわるので、複数ふくすうの法ほうを同時どうじに扱あつかうときは添字そえじを戻もどす。

Throughout this lecture the modulus $$n$$n is fixed, and $$\left[a\right]$$[a] abbreviates $$[a{]}_n$$[a]_n. Because changing the modulus changes the residue class, restore the subscript when several moduli are discussed at once.

2足たし算ざんと掛かけ算ざん

剰余類じょうよるいの加法かほうと乗法じょうほうを

で定義ていぎする。

ここで重要じゅうようなのは、右辺うへんが代表元だいひょうげんの選えらび方かたによらないことである。もし $$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv a'\pmod n、$$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$b\equiv b'\pmod n なら、

は $$n$$n の倍数ばいすうである。また、

も $$n$$n の倍数ばいすうである。したがって和わと積せきは代表元だいひょうげんによらず定さだまる（well-defined である）。

2Addition and multiplication

Define addition and multiplication of residue classes by

The important point is that the right-hand side does not depend on the choice of representatives. If $$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv a'\pmod n and $$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$b\equiv b'\pmod n, then

is a multiple of $$n$$n. Also,

is a multiple of $$n$$n. Therefore the sum and product are well-defined.

3加法かほうについて群ぐんになること

代表元だいひょうげんによらず和わが定さだまったので、$$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) の群ぐんの条件じょうけんを確認かくにんできる。閉包性へいほうせいは $$\left[a\right]+\left[b\right]=[a+b]\in \mathbb{Z}/n\mathbb{Z}$$[a]+[b]=[a+b]\in\mathbb Z/n\mathbb Z から従したがう。結合法則けつごうほうそくは

である。$$\left[0\right]$$[0] が単位元たんいげんであり、$$\left[a\right]$$[a] の逆元ぎゃくげんは $$[-a]$$[-a] である。さらに $$\left[a\right]+\left[b\right]=[a+b]=[b+a]=\left[b\right]+\left[a\right]$$[a]+[b]=[a+b]=[b+a]=[b]+[a] なので可換かかんである。したがって $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) は可換群かかんぐんである。

乗法じょうほうについても、整数せいすうの法則ほうそくを剰余類じょうよるいへ移うつせる。たとえば結合法則けつごうほうそくと左分配法則ひだりぶんぱいほうそくは

である。同様どうように乗法じょうほうの可換性かかんせいと右分配法則みぎぶんぱいほうそくも従したがい、$$\left[1\right]$$[1] は乗法じょうほうの単位元たんいげんである。ただし、すべての元げんが乗法逆元じょうほうぎゃくげんを持もつわけではない。この加法かほうと乗法じょうほうの構造こうぞうは、後あとで環かんの公理こうりとして整理せいりする。

3The additive group structure

Now that addition is independent of representatives, we can verify the group axioms for $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+). Closure follows from $$\left[a\right]+\left[b\right]=[a+b]\in \mathbb{Z}/n\mathbb{Z}$$[a]+[b]=[a+b]\in\mathbb Z/n\mathbb Z. Associativity follows from

The identity is $$\left[0\right]$$[0], and the inverse of $$\left[a\right]$$[a] is $$[-a]$$[-a]. Moreover, $$\left[a\right]+\left[b\right]=[a+b]=[b+a]=\left[b\right]+\left[a\right]$$[a]+[b]=[a+b]=[b+a]=[b]+[a], so addition is commutative. Therefore $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) is an abelian group.

The integer laws similarly pass to multiplication of residue classes. For example, associativity and left distributivity are

Commutativity and right distributivity follow in the same way, and $$\left[1\right]$$[1] is the multiplicative identity. Not every element has a multiplicative inverse. These addition and multiplication laws will later be organized as the ring axioms.

4逆元ぎゃくげんがある条件じょうけん

剰余類じょうよるい $$\left[a\right]$$[a] が乗法逆元じょうほうぎゃくげんを持もつとは、ある $$\left[x\right]$$[x] が存在そんざいして

となることである。これは

と同おなじである。

この合同式ごうどうしきが解かいを持もつための必要十分条件ひつようじゅうぶんじょうけんは

である。実際じっさい、$$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n なら $$ax-1=kn$$ax-1=kn となる整数せいすう $$k$$k がある。$$a$$a と $$n$$n の公約数こうやくすうは $$ax-kn=1$$ax-kn=1 も割わるので、$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 である。逆ぎゃくに $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 なら、ベズーの等式とうしきにより整数せいすう $$x,y$$x,y が存在そんざいして

となる。したがって $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n であり、$$\left[x\right]$$[x] が $$\left[a\right]$$[a] の逆元ぎゃくげんになる。

この条件じょうけんは代表元だいひょうげんにもよらない。$$a^{\prime }=a+kn$$a'=a+kn なら、$$a$$a と $$n$$n の公約数こうやくすうは $$a^{\prime }$$a' も割わり、$$a^{\prime }$$a' と $$n$$n の公約数こうやくすうは $$a=a^{\prime }-kn$$a=a'-kn も割わる。したがって $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a^{\prime },n)$$\gcd(a,n)=\gcd(a',n) である。

ここでは文字もじで割わり算ざんをするのではなく、最大公約数さいだいこうやくすうが 1 であることから逆元ぎゃくげんの存在そんざいを示しめしている。したがって、割わる操作そうさを行おこなう場面ばめんでは、逆元ぎゃくげんが存在そんざいする条件じょうけんを先さきに確認かくにんする必要ひつようがある。

4The condition for an inverse

A residue class $$\left[a\right]$$[a] has a multiplicative inverse if there exists a class $$\left[x\right]$$[x] such that

This is the same as

The necessary and sufficient condition for this congruence to have a solution is

Indeed, if $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n, then $$ax-1=kn$$ax-1=kn for some integer $$k$$k. Every common divisor of $$a$$a and $$n$$n divides $$ax-kn=1$$ax-kn=1, so $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1. Conversely, if $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1, Bezout's identity gives integers $$x,y$$x,y such that

Reducing this equality modulo $$n$$n gives $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n, so $$\left[x\right]$$[x] is the inverse of $$\left[a\right]$$[a].

This condition is also independent of the representative. If $$a^{\prime }=a+kn$$a'=a+kn, every common divisor of $$a$$a and $$n$$n divides $$a^{\prime }$$a', while every common divisor of $$a^{\prime }$$a' and $$n$$n divides $$a=a^{\prime }-kn$$a=a'-kn. Hence $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a^{\prime },n)$$\gcd(a,n)=\gcd(a',n).

Here we are not dividing by a symbol; we are proving the existence of an inverse from the fact that the greatest common divisor is 1. Therefore, whenever a division-like operation is used, one must first check the condition that an inverse exists.

5合同式ごうどうしきでは常つねに約分やくぶんできるとは限かぎらない

は成立せいりつするが、$$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6 である。したがって整数せいすうの等式とうしきのように 2 を無条件むじょうけんに約分やくぶんすることはできない。

一般いっぱんに $$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ca\equiv cb\pmod n で $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 なら、$$\left[c\right]$$[c] は乗法逆元じょうほうぎゃくげんを持もつ。両辺りょうへんに $$[c{]}^{-1}$$[c]^{-1} を掛かければ $$\left[a\right]=\left[b\right]$$[a]=[b]、すなわち $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n を得える。したがって $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 は、$$c$$c による約分やくぶんを正当化せいとうかする十分じゅうぶんな条件じょうけんである。

5Cancellation is not always valid in congruences

The congruence

holds, but $$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6. Thus the factor 2 cannot be cancelled unconditionally as it could in an equality of integers.

In general, if $$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ca\equiv cb\pmod n and $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1, then $$\left[c\right]$$[c] has a multiplicative inverse. Multiplying both sides by $$[c{]}^{-1}$$[c]^{-1} gives $$\left[a\right]=\left[b\right]$$[a]=[b], or $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n. Thus $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 is a sufficient condition for cancellation by $$c$$c.

6フェルマーの小定理しょうていりへの接続せつぞく

$$p$$p が素数そすうなら、0 でない剰余類じょうよるいは全すべて逆元ぎゃくげんを持もつ。0 でない剰余類じょうよるい全体ぜんたいを

と書かく。この集合しゅうごうには $$\left[1\right],\dots ,[p-1]$$[1],\ldots,[p-1] の $$p-1$$p-1 個この元げんがある。上うえで示しめしたように、0 でない各元かくげんは逆元ぎゃくげんを持もつ。0 でない $$\left[a\right],\left[b\right]$$[a],[b] の積せきが $$\left[0\right]$$[0] だとすると、両辺りょうへんに $$[a{]}^{-1}$$[a]^{-1} を掛かけて $$\left[b\right]=\left[0\right]$$[b]=[0] となり矛盾むじゅんする。したがって乗法じょうほうで閉とじている。結合法則けつごうほうそくは整数せいすうの乗法じょうほうから従したがい、$$\left[1\right]$$[1] が単位元たんいげんである。よってこれは位数いすう $$p-1$$p-1 の群ぐんである。ここに後あとで学まなぶラグランジュの定理ていりを適用てきようすると、$$p\nmid a$$p\nmid a のとき $$[a{]}^{p-1}=[1]$$[a]^{p-1}=[1]、すなわち

が導みちびかれる。これがフェルマーの小定理しょうていりである。

この節せつは後あとの群ぐんとラグランジュの定理ていりへの見通みとおしである。このページの本流ほんりゅうでは、剰余類じょうよるいの演算えんざんが well-defined であることと、逆元ぎゃくげんの存在条件そんざいじょうけんだけを使つかう。

6Connection to Fermat's little theorem

If $$p$$p is prime, every nonzero residue class has an inverse. Write the set of all nonzero residue classes as

This set has the $$p-1$$p-1 elements $$\left[1\right],\dots ,[p-1]$$[1],\ldots,[p-1], and every element has an inverse by the criterion proved above. If the product of nonzero $$\left[a\right]$$[a] and $$\left[b\right]$$[b] were $$\left[0\right]$$[0], multiplication by $$[a{]}^{-1}$$[a]^{-1} would give $$\left[b\right]=\left[0\right]$$[b]=[0], a contradiction. Thus it is closed under multiplication. Associativity follows from integer multiplication, and $$\left[1\right]$$[1] is the identity. It is therefore a group of order $$p-1$$p-1. Lagrange's theorem, studied later, gives $$[a{]}^{p-1}=[1]$$[a]^{p-1}=[1] whenever $$p\nmid a$$p\nmid a, or equivalently

This is Fermat's little theorem.

This section is a preview of later material on groups and Lagrange's theorem. The main thread of this page uses only the well-definedness of residue-class operations and the condition for inverses to exist.

7証明しょうめい補足ほそく：合同式ごうどうしきが加法かほうと乗法じょうほうで保存ほぞんされる理由りゆう

$n$n を正せいの整数せいすうとする。合同式ごうどうしき

が成立せいりつするなら、

である。

加法かほうについて証明しょうめいする。$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a\equiv b\pmod n は $n\mid (a-b)$n\mid(a-b)、$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$c\equiv d\pmod n は $n\mid (c-d)$n\mid(c-d) という意味いみである。したがって

も $n$n で割わり切きれる。よって $a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a+c\equiv b+d\pmod n である。

乗法じょうほうについては

と変形へんけいする。$n\mid (a-b)$n\mid(a-b) かつ $n\mid (c-d)$n\mid(c-d) なので、右辺うへんの二ふたつの項こうはどちらも $n$n で割わり切きれる。したがって $n\mid (ac-bd)$n\mid(ac-bd) であり、$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ac\equiv bd\pmod n である。

ここでは $n$n で割わるのではなく、$n$n が差さを割わり切きることを使つかっている。したがって文字式もじしきの除算じょざんに伴ともなう 0 除算じょざんの問題もんだいは生しょうじない。ただし、$\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$\pmod n の記法きほうでは $n$n を正せいの整数せいすうとして固定こていしている。

7Proof supplement: why congruence合同式ごうどうしき is preserved by addition and multiplication

Let $$n$$n be a positive integer. If the congruences合同式ごうどうしき

hold, then

also hold.

First prove the statement for addition. The congruence合同式ごうどうしき $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n means $$n\mid (a-b)$$n\mid(a-b), and $$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$c\equiv d\pmod n means $$n\mid (c-d)$$n\mid(c-d). Therefore

is also divisible by $$n$$n. Hence $$a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a+c\equiv b+d\pmod n.

For multiplication, rewrite

Since $$n\mid (a-b)$$n\mid(a-b) and $$n\mid (c-d)$$n\mid(c-d), both terms on the right are divisible by $$n$$n. Hence $$n\mid (ac-bd)$$n\mid(ac-bd), so $$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ac\equiv bd\pmod n.

This proof証明しょうめい does not divide by $$n$$n; it uses the fact that $$n$$n divides a difference. Therefore no issue of division by zero in symbolic division arises. However, in the notation $$\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$\pmod n, the modulus $$n$$n is fixed as a positive integer.

8演習えんしゅうリンク

8Exercise link

9まとめ

合同式ごうどうしきは、剰余類じょうよるいの等号とうごうである。mod 演算えんざんが正当化せいとうかされるのは、剰余類じょうよるい上じょうの加法かほうと乗法じょうほうが代表元だいひょうげんによらず定さだまるからである。$$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) は可換群かかんぐんである。乗法逆元じょうほうぎゃくげんは常つねにあるわけではなく、$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 が必要十分条件ひつようじゅうぶんじょうけんである。

9Summary

A congruence合同式ごうどうしき is equality of residue classes. Mod operations are justified because addition and multiplication on residue classes are determined independently of representatives. The additive structure $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) is an abelian group. Multiplicative inverses do not always exist; the condition $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 is necessary and sufficient.