もう一人のY君

主にiPhoneのショートカットアプリのレシピやTipsなどを書いています. たまに数学の記事も書きます.

もう一人のY君　MENU 　MENU

【数学】合同式の基本性質

数学

180128_12

　高校数学で合同式が採用されましたが, まだまだ「余り」から脱却できない節があります.

 

 

スポンサーリンク

 

 

合同式の基本性質

　と言うわけで今回は合同式で成り立つ性質を, 証明も合わせて見ていきたいと思います.

　その前に合同式の定義をおさらいしましょう.

 

[定義:合同式]

　整数 { \displaystyle a,b } の差 { \displaystyle a-b } が(一般に) { \displaystyle 1 } より大きい整数 { \displaystyle m } の倍数であるとき,

 

{ \displaystyle a\equiv b \pmod m }

 

と書き表して「{ \displaystyle a, b } は法 { \displaystyle m } に関して合同」と言う.

 

　「余り」でも構いませんがそれだと例えば { \displaystyle -1\equiv 2 \pmod 3 } などを説明できないことは当ブログでも何度も指摘した通りです.

　折角合同式として習う以上, 「余り」に執着し過ぎず素直に従いましょう.

 

　というわけでここでは定義に, またその時点で証明済みの事実に基づいて結論を得ることを目的とします.

 

　なお, 断りの無い限り法は { \displaystyle 1 } より大きい整数 { \displaystyle m } とします.

　また一般的な整数(整域)は既知とします.

 

 

反射律

{ \displaystyle a\equiv a \pmod m }

 

[証明]

{ \displaystyle a-a }
{ \displaystyle = 0 }
{ \displaystyle = 0×m }

 

　よって合同式の定義より { \displaystyle a\equiv a \pmod m. \square }

 

　上記から, 「{ \displaystyle 0 } の倍数」は嫌でも認めなければならないこともわかります.

 

 

対称律

{ \displaystyle a\equiv b \pmod m } { \displaystyle \Rightarrow b\equiv a \pmod m }

 

[証明]

　仮定より, ある整数 { \displaystyle q } を用いて

 

{ \displaystyle a-b=mq }

 

が成り立つので, 変形して

 

{ \displaystyle b-a=m(-q) }

 

, よって合同式の定義より{ \displaystyle b\equiv a\pmod m.\square }

 

 

推移律

{ \displaystyle a\equiv b \pmod m,\, b\equiv c\pmod m } { \displaystyle \Rightarrow a\equiv c \pmod m }

 

[証明]

　仮定より, ある整数 { \displaystyle q,\,q' } を用いて

 

{ \displaystyle a-b=mq }
{ \displaystyle b-c=mq' }

 

が成り立つので, 2辺を足し合わせて整理すると

 

{ \displaystyle (a-b)+(b-c)=mq+mq' }
{ \displaystyle \Leftrightarrow a-c=m(q+q') }

 

　よって { \displaystyle a-c } は { \displaystyle m } の倍数なので合同式の定義より { \displaystyle a\equiv c \pmod m.\square }

 

 

加法

{ \displaystyle a\equiv b \pmod m ,\, c\equiv d \pmod m } { \displaystyle \Rightarrow a+c \equiv b+d \pmod m }

 

[証明]

　仮定より, ある整数 { \displaystyle q, q' } が存在して

 

{ \displaystyle a-b=mq,\, c-d=mq' }

 

が成り立ちます.

　2式を足し合わせて整理すると

 

{ \displaystyle (a-b)+(c-d)=mq+mq' }
{ \displaystyle \Leftrightarrow (a+c)-(b+d)=m(q+q') }

 

, つまり { \displaystyle a+c } と { \displaystyle b+d } の差が { \displaystyle m } の倍数になります.

　よって合同式の定義より { \displaystyle a+c\equiv b+d \pmod m,\, \square }

 

 

加法可換

{ \displaystyle a+b\equiv b+a \pmod m }

 

[証明]

{ \displaystyle (a+b)-(b+a) }
{ \displaystyle = 0 = 0\times m }

 

なので, 合同式の定義より { \displaystyle a+b\equiv b+a \pmod m .\, \square }

 

 

加法単位元(零元)

　単位元とは, ここでは任意の整数 { \displaystyle a } について

 

{ \displaystyle a+e\equiv e+a \equiv a \pmod m }

 

を満たす, (法 { \displaystyle m } において)ただ一つの整数を指します.

 

[証明]

　先程加法可換であることは証明したので例えば { \displaystyle a+e\equiv a \pmod m } について考えれば十分です.

　合同式の定義よりこれはある整数 { \displaystyle q } が存在して

 

{ \displaystyle (a+e)-a=mq }

 

が成り立つことを意味します.

　整理すると

 

{ \displaystyle e=mq }

 

ですから { \displaystyle e } は { \displaystyle m } の倍数ということです.

 

　なので剰余類を代表して例えば { \displaystyle e=0 } として構いません(厳密には { \displaystyle m } の倍数なら何でも良いので { \displaystyle e\equiv 0 \pmod m }).

　よって合同式の加法単位元は { \displaystyle 0 } になります. { \displaystyle \,\square }

 

 

乗法

{ \displaystyle a\equiv b \pmod m ,\, c\equiv d \pmod m } { \displaystyle \Rightarrow ac \equiv bd \pmod m }

 

[証明]

　仮定より, ある整数 { \displaystyle q,q' } が存在して

 

{ \displaystyle a-b=mq }
{ \displaystyle c-d=mq' }

 

が成り立ちます, これより

 

{ \displaystyle ac-bd }
{ \displaystyle = ac - bd -bc + bc }
{ \displaystyle = (a-b)c + (c-d)b }
{ \displaystyle = mqc + mq'b }
{ \displaystyle = m(qc + q'b) }

 

, よって { \displaystyle ac-bd } は { \displaystyle m } の倍数なので定義より { \displaystyle ac\equiv bd\pmod m.\,\square }

 

 

乗法可換

{ \displaystyle ab\equiv ba \pmod m }

 

[証明]

{ \displaystyle ab-ba }
{ \displaystyle = ab - ab }
{ \displaystyle = 0 = 0\times m }

 

なので, 合同式の定義より { \displaystyle ab\equiv ba \pmod m .\, \square }

 

 

乗法単位元

　ここでの単位元とは, 任意の整数 { \displaystyle a } について

 

{ \displaystyle ae\equiv ea \equiv a \pmod m }

 

を満たす, (法 { \displaystyle m } において)ただ一つの整数を指します.

 

[証明]

　先程乗法可換であることは証明したので例えば { \displaystyle ae\equiv a \pmod m } について考えれば十分です.

　合同式の定義よりこれはある整数 { \displaystyle q } が存在して

 

{ \displaystyle ae-a=mq }

 

が成り立つことを意味します.

　整理すると

 

{ \displaystyle a(e-1)=mq }

 

, つまり { \displaystyle a } または { \displaystyle e-1 } の少なくとも一方は { \displaystyle m } の倍数です.

 

　なので剰余類を代表して例えば { \displaystyle e=1 } として構いません(厳密には { \displaystyle m } の倍数なら何でも良いので { \displaystyle e\equiv 1 \pmod m }).

　加法可換の際は大して気にする必要はありませんでしたが, 単位元は「任意の元 { \displaystyle a } について」ただ一つ存在しますので, 例えば { \displaystyle a } がたまたま { \displaystyle m } の倍数であったとしても関係ありません.

　従ってここでは { \displaystyle e-1 } が { \displaystyle m } の倍数である必要があり, 代表して { \displaystyle e=1 } となります. { \displaystyle \square }

 

 

除法(簡約)

　{ \displaystyle 0 } でない整数 { \displaystyle c } について

 

{ \displaystyle ac\equiv bc\pmod m }

 

のとき, { \displaystyle \text{gcd}(c,m)=1 } ならば

 

{ \displaystyle a\equiv b \pmod m }

 

, { \displaystyle \text{gcd}(c,m)=d\gt 1 } なる { \displaystyle d } が存在するならば, { \displaystyle m=dm' } なる整数 { \displaystyle d' } について

 

{ \displaystyle a\equiv b\pmod {m'} }

 

が成り立つ.

 

[証明]

　仮定より, ある整数 { \displaystyle q } が存在して

 

{ \displaystyle ac-bc=mq }

 

, つまり { \displaystyle ac-bc=(a-b)c } は { \displaystyle m } の倍数です.

 

({ \displaystyle \text{gcd}(c,m)=1 } のとき)

　このとき { \displaystyle c } は { \displaystyle m } の倍数となりえないため { \displaystyle a-b } が { \displaystyle m } の倍数となります.

　よって合同式の定義より { \displaystyle a\equiv b\pmod m.\, \square }

 

({ \displaystyle \text{gcd}(c,m)=d\gt 1 } のとき)

　{ \displaystyle m=m'd,\, c=c'd } と置くことで { \displaystyle \text{gcd}(c', m')=1 } となります.

　このとき { \displaystyle (a-b)c' } は { \displaystyle m' } , 即ち { \displaystyle a-b } は { \displaystyle m' } の倍数となるのでやはり合同式の定義より { \displaystyle a\equiv b\pmod m'.\, \square }

 

 

指数

　正整数 { \displaystyle n } について,

 

{ \displaystyle a\equiv b \pmod m } { \displaystyle \Rightarrow a^n \equiv b^n \pmod m }

 

[証明]

　数学的帰納法を利用します.

　{ \displaystyle n=1 } のときは自明なので省略.

 

　{ \displaystyle n=k } のとき成り立つと仮定すると, 合同式の定義よりある整数 { \displaystyle q } が存在して

 

{ \displaystyle a-b=mq }
{ \displaystyle a^k-b^k=mq' }

 

が成り立ちます.

　下は変形して { \displaystyle b^k=a^k-mq' } ですね, よって

 

{ \displaystyle a^{k+1}-b^{k+1} }
{ \displaystyle = a^{k+1}-b\left( a^k-mq' \right) }
{ \displaystyle = a^{k+1}-a^kb+bmq' }
{ \displaystyle = a^k(a-b)+mq' }
{ \displaystyle =a^kmq+mq' }
{ \displaystyle = m\left( a^kq+q' \right) }

 

と, { \displaystyle a^{k+1}-b^{k+1} } が { \displaystyle m } の倍数になるので定義より { \displaystyle a^{k+1}\equiv b^{k+1}\pmod m } .

 

　従って数学的帰納法より証明されました. { \displaystyle \square }

 

 

〆

　このように, 通常の四則演算などと同じケースと違うケースが存在します.

 

blog.thetheorier.com

　対数に相当する指数は原始根を含め更に多くの文字数を要するので, 過去の記事を参考にしてください.

 

thetheorier