横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2022年11月1日

合同式とは? 余りに着目した関係式

 合同式とはどういったものでしょうか?
どういう性質があるのでしょうか?

 合同式とは、整数の余りの関係に着目した式です。
2つの整数A,Bをそれぞれ整数nで割ると
A÷n=arB÷n=br

または、別の形で
A=an+rB=bn+r
となるとき、どちらも余りがrで一致するので
AB (mod n)
と表すことができます。
読み方は「(A)合同(B)モッド(n)」や「(n)を法として(A)合同(B)」です。

 整数A,B,Cをそれぞれ整数nで割って
(1)A=an+r(2)B=bn+r(3)C=cn+rrr,0<r<n,0<r<n
であることをもちいると、合同式の性質は以下のようなものとなります。

整数と余り

 (1)が成り立つとき、合同式で
Ar (mod n)
が成り立ちます。
これはrnで割ると
r=0n+r
のように商が0rがそのまま余りとなるためです。

負の余り

 (1)が成り立つとき、合同式で
Arn (mod n)
が成り立ちます。
これは(1)を変形すると
A={(a+1)1}n+r=(a+1)nn+r=(a+1)n+(rn)
となるためです。
 さらに拡張すると整数kをもちいて
Arkn (mod n)
が成り立ちます。
これは同様に(1)を変形して
A={(a+k)k}n+r=(a+k)nkn+r=(a+1)n+(rkn)
となるためです。
このことから2つの整数A,Bの間にAB (mod n)が成り立つときBにはB=rknを満たす整数kが存在することがわかります。

和と差

 2つの整数A,Bの間に
AB (mod n)
が成り立つとき整数Cをもちいて
A±CB±C (mod n)
が成り立ちます。
これは(1)(3)の辺々を足して(引いて)
A±C=(an+r)±(cn+r)=(an±cn)+(r±r)(複号同順)=(a±c)n+(r±r)
(2)(3)の辺々を足して(引いて)
B±C=(bn+r)±(cn+r)=(bn±cn)+(r±r)(複号同順)=(b±c)n+(r±r)
となり、余りがどちらもr±rとなるためです。

 2つの整数A,Bの間に
AB (mod n)
が成り立つとき、整数Cをもちいて
ACBC (mod n)
が成り立ちます。
これは(1)(3)の辺々を掛けて
AC=(an+r)(cn+r)=acn2+(ar+cr)n+rr=(acn+ar+cr)n+rr
(2)(3)の辺々を掛けて
BC=(bn+r)(cn+r)=bcn2+(br+cr)n+rr=(bcn+br+cr)n+rr
となり、余りはどちらもrrから出てくるためです。

累乗

 2つの整数A,Bの間に
AB (mod n)
が成り立つとき、整数kをもちいて
AkBk (mod n)
が成り立ちます。
これは(1)の両辺をk乗して、二項定理より
Ak=(an+r)k=(an)k+k(an)k1r+kC2(an)k2r2++kCk2(an)2rk2+kanrk1+rk=(aknk1+kak1nk2r++kCk2a2nrk2+kark1)n+rk
同様に(2)の両辺をk乗して、
Bk=(bn+r)k=(bn)k+k(bn)k1r+kC2(bn)k2r2++kCk2(bn)2rk2+kbnrk1+rk=(bknk1+kbk1nk2r++kCk2b2nrk2+kbrk1)n+rk
となり、余りはどちらもrkから出てくるためです。

Share:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ