その五 合同式の話

 その一でいきなりややこしい話を展開してしまったがここで用いた「合同式」とは数の性質を理解していれば中学生でも飲み込めてしかもいろいろと役に立つのでここで少しだけ扱ってみる.

 まずは定義から.
定義:a≡b (mod c)⇔a-bがcで割り切れること
(「cを法としてaとbが合同」「mod c(modulo c)でaとbが合同」という.)
たとえば
10≡0 (mod 5)
14≡5 (mod 3)
13≡-3 (mod 2)

などなど.
a-bがcで割り切れるので,
a-b=sc
a=b+sc (sは整数)

と書ける.(以下,各文字は断りなく整数として扱う.)


 合同式の性質として次のようなことが分かる.

(ア)aをcで割った商をq,あまりをrとすればa≡r (mod c)
a=qc+rと書けるので
左辺-右辺=a-r=qc+r-r=qcとなってcで割り切れる.


(イ)a≡b (mod c)⇔任意のdに対しa+d≡b+d (mod c)

a-b=scとすれば,
左辺-右辺=(a+d)-(b+d)=a-b=scとなってcで割り切れる.

左辺-右辺=a-b=a-b+d-d=a+d-b-d=(a+d)-(b+d)となってcで割り切れる.

(ウ)a≡b (mod c),d≡e (mod c)ならばa+d≡b+e (mod c)
(イ)より
a+d≡b+d≡b+e (mod c).


(エ)a≡b (mod c)ならば,任意のdに対しad≡bd (mod c)
a-b=scとすれば,
左辺-右辺=ad-bd=d(a-b)=dscとなってcで割り切れる.


(オ)a≡b (mod c),d≡e (mod c)ならばad≡be (mod c)
(エ)より
ad≡bd≡be (mod c).


(カ)a≡0 (mod c)で,pがaの約数でcと互いに素ならばa/p≡0 (mod c),a/c≡0 (mod p)
a=sc=kpとするとcとpが互いに素なのでpの素因数はすべてsに含まれてs=prと書ける.したがってa=sc=prcとなってa/p=rcとなってcで割り切れ,a/c=rpとなってpで割り切れる.

(キ)a≡b (mod c)で,pがaとbの公約数でcと互いに素ならばa/p≡b/p (mod c)
a-b≡0 (mod c)でpはa-bの約数なので(カ)に帰着される.

(ク)aとcが互いに素ならばax≡b (mod c)を満たすxが,mod cで唯一に決まる
aに1からcまでの数をかけた物を元とする集合{n|n=ak,1≦k≦c}={a1,a2,…,ac}の元は,どの二つもmod cで合同でない事を示そう.
この集合のどれか二つがmod cで合同であるとする.それをai,ajとする(1≦i<j≦c)と
ai≡aj (mod c)
aはcと互いに素なので(キ)より
i≡j (mod c)
iとjの差がcの倍数になるが1≦i<j≦cだったのでそれは不合理だ.したがってこのような二数ai,ajは存在せず,この集合のどの二つの元もmod cで合同でなく,cで割ったあまりの種類すべてがこの集合にそろう.その中にbと合同なものがただ一つ存在する.それがxだ.x≡y (mod c)ならば(エ)よりax≡ay≡b (mod c)となり一般解は無数にあるがそれらはmod cですべて合同なのでmod cで唯一に決まるのである.


(ケ)a≡b (mod c)⇔ad≡bd (mod cd)

a-b=scと書けるので左辺-右辺=ad-bd=d(a-b)=dscとなりcdで割り切れる.

ad-bd=ecdと書けるので両辺をdで割ってa-b=ecとなりcで割り切れる.


(コ)a≡b (mod cd)→a≡b (mod c),a≡b (mod d).cとdが互いに素ならa≡b (mod cd)⇔a≡b (mod c),a≡b (mod d)
a-b=scdよりcでもdでも割り切れる.
またa-bがcの倍数,かつdの倍数ならa-bはcとdの公倍数,cとdが互いに素ならa-bはcdの倍数.

(サ)bとcが互いに素でa≡e (mod b),a≡f (mod c)なら,gc≡1 (mod b),hb≡1 (mod c)なるg,hを用いてa≡fhb+egc (mod bc)となり,mod bcで一意に決まる
gとhの存在は(ク)によって保証される.
a≡e (mod b)からa≡fhb+e (mod b),gc≡1 (mod b)なのでa≡fhb+egc (mod b).
同様にa≡f (mod c)からa≡f+egc (mod c),hb≡1 (mod c)なのでa≡fhb+egc (mod c).
bとcは互いに素なので(コ)の後半よりa≡fhb+egc (mod b)かつa≡fhb+egc (mod c)からa≡fhb+egc (mod bc)といえる.
また1≦d<d'≦bcなるd,d'がd,d'≡e (mod b),d,d'≡f (mod c)を満たすとするとd≡d' (mod b),d≡d' (mod c)となるがbとcが互いに素なので(コ)の後半よりd≡d' (mod bc).d<d'だったのでd'-d≧bc.これは1≦d<d'≦bcに反する.したがってこのようなd,d'の組は存在せず,aはmod bcで一意に決まる.

一般に,どの二つも互いに素なp1,p2,…,pnと,任意の数の組a1,a2,…,anに対し,x≡ak (mod pk) (1≦k≦n)を満たすxがp1p2…pnを法として一意に求まる.これを「中国剰余定理」という.


 具体的に問題を解くと有用性が分かると思うのでやってみよう.
百の位がa,十の位がb,一の位がcの整数100a+10b+cが11で割り切れるなら,a-b+cは11の倍数であることを示せ.
中学生の時に出会うと思われる典型的整数問題だ.100=99+1,10=11-1と分けて100a+10b+c=99a+11b+a-b+cと変形して示すのだが,合同式を使うと
100≡1 (mod 11)なので100a≡a …(ア),(エ)より.
11≡0 (mod 11)より10≡-1,10b≡-b …(ア),(イ),(エ)より.
したがって(ウ)より,
100a+10b+c≡a-b+c≡0 (mod 11).

とできたりする.

では次はどうか.
自然数Nの平方を17で割ったあまりが1のときNを17で割ったときのあまりは何か.
普通はN=17a+bと置いてN2=289a2+34ab+b2と展開,bについて場合わけという面倒な問題.合同式を使うと,
N2≡1 (mod 17)なので
N2-1≡0 (mod 17) …(イ)より.
(N-1)(N+1)≡0 (mod 17)
N-1≡0またはN+1≡0 (mod 17) …(カ)より.
したがって
N≡1,-1 (mod 17)
となってあまりは1または16.

いかが?

もう一つ.
私の年齢は,3で割ると1あまり,5で割ると2あまり,7で割ると3余る.私は何歳か.
中国剰余定理を使う問題のうち,百五減算と名が付くものらしい.
年齢をNとすると
N≡1 (mod 3)
N≡2 (mod 5)
N≡3 (mod 7)
(ク)より
5・7・2≡1 (mod 3)
7・3・1≡1 (mod 5)
3・5・1≡1 (mod 7)
を求めて,(サ)より,
N≡1・35・2+2・21・1+3・15・1≡157≡52 (mod 105)
したがって52歳.

ちなみに私はこんな歳ではありません.半分くらいです.


 合同式は今後も頻繁に使いそうなのでよろしくお願いします.

戻る