【第3章】
(3)合同式の性質②(mod n)を略記する。
a≡b, c≡dのとき、
a+c≡b+d
a-c≡b-d
ac≡bd
(∵)
a≡bより、a-b=nt
c≡dより、c-d=ns
(a+c)-(b+c)=(a-b)+(c-d)=nt+ns=n(t+s)
よって、a+c≡b+d
(a-c)-(b-d)=(a-b)-(c-d)=nt-ns=n(t-s)
よって、a-c≡b-d
ac-bd=ac-bc+bc-bd=(a-b)c+(c-d)b
=ntc-nsb=n(tc-sb)
よって、ac≡bd
c=a, d=bとすると、a^2≡b^2
これを繰り返すと、
a≡bならば、a^n≡b^n
a≡b (mod n) ⇒ ma≡mb (mod mn)
a≡b (mod n)より、a-b=nt
ma-mb=m(a-b)=mnt
よって、ma≡mb (mod mn)
(例)x≡3 (mod 5) ⇒ 3x≡9 (mod 15)
pとqは互いに素のとき、
a≡b (mod pq)
⇔ a≡b (mod p)かつa≡b (mod q)
【証明】
→)a-b=pqtとする。
a-b=p(qt)より、a≡b (mod p)
a-b=q(pt)より、a≡b (mod q)
←)a-b=ps, a-b=qtとする。
ps=qt
p,qは互いに素だから、sはqの倍数である。s=qu
a-b=pquより、a≡b (mod pq)
【証明終】