合同式
合同式を用いると，整数に関する種々の問題が簡単に解ける場合がある．以下，定理等の証明は省略する．
☆合同式の定義☆
定義：整数aとbを整数mで割ったときの余りが等しいとき，すなわち，a-bがmで割り切れるとき,aとbはmを法として合同であるといい，
a≡b (mod m)
と書く．
合同式⇔等式の「翻訳」：
a≡b (mod m) ⇔ a-b=mk となる整数kがある(a-bがmで割り切れる) ⇔ a=b+mk となる整数kがある
☆合同式の性質☆
定理1：次が成り立つ．
a≡a (mod m) ･･･反射律
a≡b (mod m) ⇒ b≡a (mod m) ･･･ 対称律
a≡b (mod m)，b≡c (mod m) ⇒ a≡c (mod m) ･･･ 推移律
定理2：a≡b (mod m)，c≡d (mod m) ⇒次が成り立つ．
a+c≡b+d (mod m)，a-c≡b-d (mod m)
ac≡bd (mod m)
自然数nに対し，an≡bn (mod m)
系1：a+b≡c (mod m) ⇒ a≡c-b (mod m) が成り立つ．すなわち，移項が可能である．
定理3：加算，乗算について交換法則および結合法則が，また分配法則 a(b+c)≡ab+ac が成り立つ．
定理４：ac≡bc (mod m)，cとmは互いに素 ⇒ a≡b (mod m) ･･･ 両辺をcで割ることができる
定理５：ac≡bc (mod mc) ，cとmは互いに素⇔ a≡b (mod m) ･･･ 法も含めて両辺をcで割ることができる
☆１次合同方程式☆
定理4：aはmで割り切れないとき，1次合同方程式
ax≡b (mod m)
で，aとmの最大公約数をdと置くとき，次が成り立つ．
d=1 ⇒ 1個の解を持つ
d>1，bがdで割り切れる ⇒ d個の解を持つ
bがdで割り切れない ⇒ 解を持たない
例：(1) 3x≡5 (mod 7) を解け．
(2) 18x≡8 (mod 14) を解け．
解：(1) 5≡12 なので，3x≡12．従って x≡4．
(2) 両辺を2で割って，9x≡4 (mod 7) → 7x≡7なので，9x-7x≡4-7
→ 9x-7x≡-3 → 2x≡4 (mod 7) → 両辺を2で割って，x≡2 (mod 7) →x≡2,9,16,･･･
(mod 7)
→7で割って2余る整数は14で割っても2余るので，x≡2,9 (mod 14)
☆1次不定方程式☆
例：5x+3y=37 を満たす整数x，yを求めよ．
解：5x=-3y+37 なので，5x≡37 (mod 3) と書ける．
5x≡2x，37≡4なので，2x≡4．両辺を2で割って，x≡2．
x=3t+2．これをもとの式に代入して，5(3t+2)+3y=37．y=-5t-9．
答：x=3t+2，y=-5t-9
☆その他の問題☆
問題：nを自然数とするとき，3n+1+42n-1は13で割り切れることを証明せよ．(1982 名古屋市立大)
証明：(mod 13)を省略する．
3n+1+42n-1≡32+･3n-1+4･42(n-1)≡9･3n-1+4･16n-1
≡9･3n-1+4･(13+3)n-1≡9･3n-1+4･3n-1≡13･3n-1≡0
従って，3n+1+42n-1は13で割り切れる．
(証明終)
類題：nを自然数とするとき，5n+1+62n-1は31で割り切れることを証明せよ．
問題：a2+b2が3で割り切れるならば，a，bはともに3で割り切れることを示せ．(1987 都立大)
解：a，bを3で割った余りをそれぞれr，sとすると，a2≡r2，b2≡s2．
ゆえにa2+b2≡0なので，r2+s2≡0．
r2+s2を3で割った余りを表にすると次のようになる．
s r 0 1 2 0 0 1 1 1 1 2 2 2 1 2 2
この表より，r=s=0のときに限り，r2+s2≡0．
従って，a，bは3で割り切れる．すなわちa，bは3の倍数である．
問題：mは7で割れば3余る整数，nは7で割れば4余る整数とする．このとき，
m+2nを7で割ると余りはア□である．
mnをを7で割ると余りはイ□である．
n3を7で割ると余りはウ□である．
n2001を7で割ると余りはエ□である．
(2001 近畿大・理系)
解：条件は，m≡3 (mod7)，n≡4 (mod7) である．以下(mod7)を省略する．
n≡4の両辺に2をかけて，2n≡8．これとm≡3を辺々加えると，m+2n≡11≡4 ･･･ ア
m≡3とn≡4 を辺々加えると，mn≡12≡5 ･･･ イ
n≡4の両辺を3乗すると，n3≡64≡1 ･･･ ウ
n2001=(n3)667≡1667=1 ･･･ エ
☆発展☆
フェルマーの小定理：素数pとpで割り切れない整数aに対し，ap-1≡1 (mod p)
たとえばフェルマーの小定理は次のような場合に応用できる．
問題：235 (mod 7) を求めよ．
解：フェルマーの小定理より，26≡1 (mod
7)．
235=(26)5･25≡15･25≡32≡4
(mod 7)．
問題：x103≡4 (mod 11) を解け．
解：フェルマーの小定理より，210≡1
(mod 11)．
x103=(x10)10･x3≡110･x3≡x3．
よって，x3≡4 (mod 11) を解けばよい．
x=0,1,･･･,10を代入し53≡4 (mod 11)となるので，x≡5
(mod 11)．
定義：φ(n)=(nと互いに素なn以下の正の整数の個数)をオイラー関数という．
n 1 2 3 4 5 6 7 8 9 10 φ(n) 1 1 2 2 4 2 6 4 6 4
黄色の部分はnが素数のところ．
オイラーの定理：整数aとmが互いに素なとき，aφ(m)≡1 (mod m)
オイラーの定理でm=pのときφ(p)=p-1なので，フェルマーの小定理はオイラーの定理の特別な場合である．
オイラー関数の性質：
素数pと整数k≧1に対し，φ(pk)=pk-pk-1
mとnが互いに素なとき，φ(mn)=φ(m)φ(n)
問題：φ(12)を求めよ．
解：φ(12)=φ(22･3)=φ(22)･φ(3)=(22-21)(3-1)=4