整数aとbの差が正の整数nで割り切れるとき、nを法としてaとbは合同であるといい、
\( a \equiv b \ (mod \ n) \)
と表す。
aをnで割ったときの余りr1と、bをnで割ったときの余りr2が等しいということ。
(r1, r2 >= 0)
\( 10 \equiv 0 \ (mod \ 5) \) 10は5で割ると0余る(割り切れる)。
\( 10 \equiv 1 \ (mod \ 3) \) 10を3で割ると1余る。
反射律
\( a \equiv a \ (mod \ n) \)
対象律
\( a \equiv b \ (mod \ n) \ \Longleftrightarrow \ b \equiv a \ (mod \ n) \)
推移律
\( a \equiv b, \ b \equiv c \ (mod \ n) \ \Longrightarrow \ a \equiv c \ (mod \ n) \)
\( a \equiv b \ (mod \ n) \ \ AND \ \ c \equiv d \ (mod \ n) \ \Longrightarrow \ a + c \equiv b + d \ (mod \ n) \)
\( a \equiv b \ (mod \ n) \ \ AND \ \ c \equiv d \ (mod \ n) \ \Longrightarrow \ a – c \equiv b – d \ (mod \ n) \)
\( a \equiv b \ (mod \ n) \ \ AND \ \ c \equiv d \ (mod \ n) \ \Longrightarrow \ ac \equiv bd \ (mod \ n) \)
\( d = c \)とすれば、同じ数を両辺に加算、減算、乗算しても合同
\( a \equiv b \ (mod \ n) \ \ \Longrightarrow \ a + c \equiv b + c \ (mod \ n) \)
\( a \equiv b \ (mod \ n) \ \ \Longrightarrow \ a – c \equiv b – c \ (mod \ n) \)
\( a \equiv b \ (mod \ n) \ \ \Longrightarrow \ ac \equiv bc \ (mod \ n) \)
両辺をx乗しても合同
\( a \equiv b \ (mod \ n) \ \Longrightarrow \ a^x \equiv b^x \ (mod \ n) \)
\( ab \equiv ac (mod \ n) \) のとき、aとnが互いに素であれば \( b \equiv c \)。