合同式

合同式

整数全体を自然数 m で割った余りで分類すると m 種類に分かれる.この分類は日常生活でもしばしば用いられる.たとえば,曜日は 7 による割り算の余りで計算される.

目次

  1. 合同関係
  2. 1次合同式
  3. 中国剰余定理

1. 合同関係

2つの整数 a, b の差 a - b がm で割り切れるとき,a と b とは m を法として 合同であるといい,記号では,a ≡ b mod (m) で表す.この記号は ガウスによる.別の言い方をすれば,a ≡ b mod (m) ということは a, b を m で割った余りが一致するということである.式 a ≡ b mod (m) を 合同式という.

命題 1 整数 Z において,m を法として合同ということは同値関係である.

合同式は等式と同様な性質をもっている.

命題 2 a ≡ b mod (m) および a' ≡ b' mod (m) のとき,合同式

  1. a + a'≡ b + b' mod (m)
  2. aa' ≡ bb' mod (m)
が成立する.

f(x) を整数係数の多項式とするとき,a ≡ b mod (m) であれば,合同式

f(a) ≡ f(b) mod (m) が成立する.

問題 1 自然数 a を 10 進法で anan-1... a0 と表したとき, an + ... + a0 ≡ 0 mod (3) ならば,a ≡ 0 mod (3) である.

解答 10 ≡ 1 mod (3) だから,任意の k について,10k ≡ 1 mod (3) であり,

an10n + ... + a110 + a0 ≡ an + ... + a1 + a0 mod (3)

が成立する.

問題 2 ある年の 10 月 1 日は水曜日であった.この年の 4 月 1 日の曜日を計算せよ.

 

2. 1 次合同式

1 次合同式

ax ≡ b mod (m)

はいつ解をもつのであろうか.まず,a と m が互いに素なときを考えてみよう.

命題 3 GCD(a,m)=1 のとき,任意の b について,1 次合同式

ax ≡ b mod (m)

は解をもつ.1つの解を x0 とすれば,解全体は {x0 + nm | n ∈ Z } で与えられる.

p が素数のとき,p が a を割らなければ,1 次合同式 ax ≡ b mod (p) には解が存在する.

一般の場合,解をもつ条件は次のようになる.

定理 4 GCD(a,m) = d のとき,1 次合同式

ax ≡ b mod (m)

が解をもつ必要十分条件は d | b である.また,d | b の場合,m = dm0 とし,1つの解を x0 とすれば,解全体は {x0 + nm0 | n ∈ Z } で与えられる.

問題 3 (フェルマーの小定理) 素数 p が与えられたとき,p で割れない自然数 a に対して,合同式

ap-1 ≡ 1 mod (p)

が成立する.

 

3. 中国剰余定理

4世紀頃の中国の数学書「孫子算経」には次のような問題とその解法が記されているという.個数のわからない物があり,3 で割ると 2 余り,5 で割ると 3 余り,7 で割ると 2 余るという,このとき,個数を求めよ.これは次の連立1次合同式の解を求めることと同値である.

x ≡ 2 mod (3)     (1)
x ≡ 3 mod (5)     (2)
x ≡ 2 mod (7)     (3)

素朴に考えてみよう.(1) の解は ...,2,5,8,11,14,17,20,23,... であり,(2) の解は ...,3,8,13,18,23,... であり,(3)の解は ...,2,9,16,23,...

である.したがって,23 が1つの解であることがわかる.一般的な問題と解法は次のようになる.

定理 5 (中国剰余定理) どの2つも互いに素な自然数 m1 ,...,mr が与えられたとき,連立合同式

x ≡ b1 mod (m1)
x ≡ b2 mod (m2)
....
x ≡ bn mod (mr)

には解が存在し,1つの解を x0 とすれば,解全体は {x0 + nΠi mi | n ∈Z } で与えられる.

問題 4 200 以下の自然数のうち,3 で割れば 2 余り,4 で割れば 1 余り,5 で割れば 3 余る数をすべて求めよ.

解答 任意の解は 53 + 60n, {n ∈ Z} で与えられる.したがって,200 以下の自然数解は 53,113,173 の 3 個である.


トップへ
酒井文雄記(2000年4月)