剰余計算の復習

「代数学」で勉強したはずの剰余計算の復習です.


1. 記号の意味

a (mod n)とは,aをnで割ったときの余りのこと.たとえば,12(mod5)=2

2. 基本的な性質

@ a (mod n)<n

A a<n なら a (mod n)=a.

B a (mod n)=bなら適当なxによって,a=nx+bとなる.

C a (mod n)=bなら(a-b)はnで割り切れる.

D a*b*c (mod n)=(a (mod n)*(b (mod n)*(c (mod n)) (mod n).たとえば 53 (mod 4)=125 (mod4)={5 (mod 4) *5 (mod 4) *5 (mod 4)} (mod 4) ={1*1*1} (mod 4)=1 (mod 4)=1

E(a+b)(mod n)={(a(mod n)+b(mod n)}(mod n).たとえば(5+7)(mod 3)=12(mod 3)=0={5(mod 3)+7(mod 3)}(mod 3)={2+1}(mod 3)=0

3. Fermat(フェルマー)の定理

1<m<pを満たすmとpに対して,次の式が成立する.

Fermatの定理の証明