数の合同
著者:梅谷 武
語句:ポリヤ,エドモンド・ハレー,ウィリアム・ハミルトン,ユリウス・カエサル,クリストファー・クラヴィウス,春分点,マテーマティコイ,法,合同,剰余,非剰余,合同記号,剰余類,剰余系,完全剰余系
数の合同について述べる。
作成:2006-06-07
更新:2021-03-17
5.1 数の合同
 正の整数mと任意の整数a,bについてm|a－bという関係が成り立っているとき、aとbはmを法ほう, modulusとして合同ごうどう, congruentであるといい、
a ≡ b (mod m)
と書きます。このときaはbの、あるいはbはaの剰余じょうよ, residueと呼ばれます。m∤a－bのときは合同ではないといい、
a ≢ b (mod m)
と書きます。このときaはbの、あるいはbはaの非剰余ひじょうよ, non-residueと呼ばれます。除法の原理から、
               a
=
mq1 + r1, 0≦r1＜m
b
=
mq2 + r2, 0≦r2＜m
となる(q1,r1),(q2,r2)が一意的に定まりますが、a≡b(mod m)とr1=r2、a≢b(mod m)とr1≠r2は同じことを意味しています。
 この数の合同概念は、数をかぞえようとしたときに自然に発生するものなので、その起源は数の起源と一致すると考えていいでしょう。しかし、上の合同記号ごうどうきごうはガウスが始めて導入したもので、これによりいろいろな性質が簡単に表現できたり、計算できるようになったという意味で画期的なものでした。
 以下、この数の合同に関する基本的な性質を列挙していきます。

命題5.1.4

 整数における合同は同値関係になっている。すなわち、正の整数mを法としたとき任意の整数a,b,cに対して次が成り立つ。
(反射律) a ≡ a (mod m)
(対称律) a ≡ b (mod m) ⇒ b ≡ a (mod m)
(推移律) a ≡ b (mod m), b ≡ c (mod m) ⇒ a ≡ c (mod m)

証明

(反射律) m | (a－a)=0
(対称律) m | (a－b) ⇒ m | －(a－b)=(b－a)
(推移律) m | (a－b), m | (b－c) ⇒ m | (a－b)+(b－c)=(a－c)
■
 正の整数mを法とする合同を同値関係と考えて整数を分割したときの同値類を剰余類じょうよるい, residue classといいます。ある整数aについてaを含む剰余類をaと書くことにします。例えば、法を3としたときに整数は三つの剰余類に分割されます。
               ℤ
=
0 ∪ 1 ∪ 2
0
=
{ ⋯, －6, －3, 0, 3, 6, ⋯ } = {3n | n∈ℤ}
1
=
{ ⋯, －5, －2, 1, 4, 7, ⋯ } = {3n+1 | n∈ℤ}
2
=
{ ⋯, －4, －1, 2, 5, 8, ⋯ } = {3n+2 | n∈ℤ}
 任意の正の整数mに対して、任意の整数aから始まる連続するm個の数
a, a+1, a+2, ⋯, a+m－1
はmを法とする合同により分割した整数のm個の剰余類の代表となっています。これを剰余系じょうよけい, system of residuesといいます。特にすべての剰余類の代表を含んでいることを強調する場合に完全剰余系かんぜんじょうよけい, complete system of residuesということがあります。通常は0から始まるm個の数
0, 1, 2, ⋯, m－1
が剰余系として使われますが、有理数b/aに対して[b/a]によってb/aを超えない最大の整数を表わすことにしたときに
－
[m
2		]
, －
[m
2		]
 + 1, ⋯, －
[m
2		]
 + m － 1
という絶対値がすべてm/2以下であるような剰余系が使われることもあります。

命題5.1.8

 a≡b(mod m), c≡d(mod m)のとき次が成り立つ。
(1) a + c ≡ b + d (mod m)
(2) a － c ≡ b － d (mod m)
(3) ac ≡ bd (mod m)

証明

 仮定よりm|a－b, m|c－d.
(1) m | (a+c)－(b+d)=(a－b)+(c－d).
(2) m | (a－c)－(b－d)=(a－b)－(c－d).
(3) m | (ac－bd)=(a－b)c+(c－d)b.
■

系5.1.10

 任意の自然数kについてa ≡ b (mod m)ならば
ak ≡ bk (mod m)

系5.1.11

 任意の整係数一変数多項式f(X)についてa ≡ b (mod m)ならば
f(a) ≡ f(b) (mod m)

系5.1.12

 任意の整係数多変数多項式f(X1,⋯,Xn)についてai ≡ bi (mod m), i=1,⋯,nならば
f(a1,⋯,an) ≡ f(b1,⋯,bn) (mod m)

命題5.1.13

 正の整数k,mについて次が成り立つ。
(1) a ≡ b (mod m) ⇒ ka ≡ kb (mod m)
(2) a ≡ b (mod km) ⇒ a ≡ b (mod m)
(3) (k,m)=1, ka ≡ kb (mod m) ⇒ a ≡ b (mod m)
(4) (k,m)=d, ka ≡ kb (mod m) ⇒ a ≡ b (mod m/d)}

証明

 演習とする。■

例題5.1.15

 1723 ≡ 8 (mod 15)

解答

 1723 ≡ 223 ≡ (24)523 ≡ 8 (mod 15)■
 合同式の性質を使った検算方法に九去法というものがあります。これは整数nを
n =
k
∑
i=0
ai10i
, 10＞ai≧0, k≧0
と10進表示したときに、10i ≡ 1 (mod 9)であることから
n ≡
k
∑
i=0
ai
 (mod 9)
が成り立つことを利用したものです。

例題5.1.18

 18472946 × 9364964 = 172998374263944を九去法で検算せよ。

解答

 18472946×9364964≡142≡52≡7, 172998374263944≡15≡6(mod 9)より不正。■
 異なる法の合同式については次の命題が基本的です。

命題5.1.21

 a≡b(mod m), a≡b(mod n)のとき次が成り立つ。
a ≡ b (mod lcm(m,n))
特に(m,n)=1のときは、
a ≡ b (mod mn)

証明

 mとnの各素因数の最大冪peについてpe|mであるかpe|nであるからpe|a－bとなる。■

フェルマー数

 nを自然数としたときにFn = 22n+1の形の数をフェルマー数といいます。
          F0
=
21 + 1 = 3
F1
=
22 + 1 = 5
F2
=
24 + 1 = 17
F3
=
28 + 1 = 257
F4
=
216 + 1 = 65537
となり、F4まではすべて素数になっています。このことからフェルマーはすべてのフェルマー数が素数であるということを予想しましたが、1732年にオイラーが
F5 = 232+1 = 641 × 6700417 = 4294967297
と素因数分解できることを示し、フェルマーの予想を否定しました。
 1924年にポリヤPòlya, George, 1887-1985は素数が無限にあることを証明するには、どの二つの項も互いに素であるような自然数の無限数列を見つければよいことから、フェルマー数列(Fn)n ∈ℕがその条件を満たすことを示し、それにより素数が無限であることを証明しています。
 ここでは合同式の性質を使ってこれを示してみましょう。m＞nとし、pをp | Fm, p | Fnなる素数であると仮定します。22n + 1 ≡ 0 (mod p)より
22n ≡ －1 (mod p)
これを2m－n乗すると
(22n)2m－n ≡ (－1)2m－n (mod p)
となり
22m ≡ 1 (mod p)
が成り立ちます。一方、仮定から22m ≡ －1 (mod p)ですから、
1 ≡ －1 (mod p)
となり、p | 2です。フェルマー数は奇数ですからp=2とは成りえず、p=1であることがわかります。これにより次の命題が証明されました。

命題5.1.26

 フェルマー数列(Fn)n ∈ℕの任意の二項は互いに素である。

ファウルハーバーの定理より

 4.3節で冪和公式に関するファウルハーバーの業績について触れましたが、その内容が関・ベルヌーイの冪和公式に比べてかなり複雑であることから本書ではその詳細を述べていません。しかし、その中でkが奇数のとき、任意の正の整数nについて
P1(n) | Pk(n), Pk(n) =
n
∑
i=1
ik
が成り立つことだけは合同式を使って簡単に証明することができます。
 n=1のときは成り立ちますので、n＞1と仮定します。
P1(n) =
n(n+1)
2
ですから、n(n+1) | 2(1k + 2k + ⋯ +nk)を示せば結論が得られます。
               
2(1k + 2k + ⋯ +nk)
≡
2(1k + 2k + ⋯ +(n－1)k) (mod n)
≡
(1k + (n－1)k) + (2k + (n－2)k) + ⋯ +((n－1)k+1k) (mod n)
≡
(1k + (－1)k) + (2k + (－2)k) + ⋯ +((－1)k+1k) (mod n)
kが奇数であることから一番下の式はnを法として0になり、n | 2Pk(n)が成り立ちます。
               
2(1k + 2k + ⋯ +nk)
=
(1k + nk) + (2k + (n－1)k) + ⋯ +(nk+1k)
≡
(1k + (－1)k) + (2k + (－2)k) + ⋯ +((－1)k+1k) (mod n+1)
やはりkが奇数であることから一番下の式はn+1を法として0になり、n+1 | 2Pk(n)が成り立ちます。n>1のとき(n,n+1)=1ですからn(n+1) | 2Pk(n)が証明できました。
 また、任意の正の整数nについてP1(n) | Pk(n)が成り立つので、系3.6.59より多項式としてP1(X) | Pk(X)が成り立つこともわかります。

グレゴリオ暦

 天体の運動から生活のために必要な情報を得るということは、人類が古代から取り組んできた問題です。さまざまな民族がそれぞれ独自に数学を発達させてきた一つの要因は、よりよい暦を作成する必要に迫られたためであると考えられます。西洋の数学の起源はピュタゴラス派の分派であるマテーマティコイ*1が数論、幾何学、音楽、天文学をマテーマタ(学ばるべきもの)と呼んだことに由来することからわかるように、古代においては天文学は数学に含まれていました。
 ヨーロッパにおいてはこの伝統は近代まで続いています。有名な例を挙げれば、ニュートンの友人であったエドモンド・ハレーHalley, Edmond, 1656-1742、ゲッティンゲン大学天文台長であったガウス、ダンシンク天文台長であったウィリアム・ハミルトンHamilton, William Rowan, 1805-1865らが数学と天文学の両方の業績を残しています。
 ここでは、数の合同概念と暦法がどのようにかかわっているのかを簡単な例で見てみましょう。
 暦法の一つの問題として「一年を何日にするか」ということがあります。ここで、一年とは地球から見た太陽が、春分点しゅんぶんてん, vernal equinoxを通過したときから次に春分点を通過するまでの時間のことです。一日とは地球から見た太陽が、ちょうど真南を通過したときから次に真南を通過するまでの時間です。ややこしいのは地球の自転や公転の周期が常に変動しているということです。現在は1900年初頭の平均太陽日と平均太陽年を採用していますが、それによると一年は365.24219879日となっています。
 古代ローマ帝国の初代皇帝となったユリウス・カエサルCaesar, Gaius Iulius, B.C.100-B.C.44はユリウス暦を定めました。これは一年を365.25日と決めて、平年を365日、四年毎の閏年を366日として、暦のずれを補正するものです。しかし、これですと一年に
365.24219879 － 365.25 = 0.00780121 [日]
だけずれていって、128年経過すると
0.00780121 × 128 = 0.99855488 [日]
となり、約一日ずれることになります。
 ヨーロッパではこのユリウス暦が16世紀まで使われていました。しかし、その頃になるとそのずれは10日ぐらいまでになり暦と季節とのずれがはっきりしてきて、改暦の必要性が生じました。教皇グレゴリウス13世は、1579年にクリストファー・クラヴィウスClavius, Christopher, 1538-1612らを中心とした委員会を発足させ、改暦問題を研究させました。委員会ではコペルニクスを含む天文学者達に計算させて一年を365.2425日と定めました。この新しいグレゴリオ暦は1582年2月24日に発布され、同年10月4日木曜日の翌日が10月15日金曜日とされました。それ以来、現在に至るまでこの暦が多くの国々で使われています。日本では1900年に採用されました。
 グレゴリオ暦では一年に
365.24219879 － 365.2425 = 0.00030121 [日]
だけずれていって、3320年経過すると
0.00030121 × 3320 = 1.0000172 [日]
となり、約一日ずれることになります。この3000年の間には暦によるずれだけではなく、地球の自転や公転のずれなどの別の要因による補正が必要になりますので、十分な精度になっています。
 それではグレゴリオ暦において平年を365日、閏年を366日として補正する場合、閏年をどのように定めたのでしょうか。まず、ユリウス暦と同じように閏年Xを
X ≡ 0 (mod 4)
と定めると4年間が365 × 3 + 366 = 1460[日]となり、対応する太陽年365.2425 × 4 = 1459.97[日]との差は0.03[日]です。これでは400年で3日多くなってしまいます。そこで100年おきに閏年を平年とし、400年目には閏年にすると定めました。つまり、閏年Xの中で
          X
≡
0 (mod 100)
X
≢
0 (mod 400)
という条件を満たすものを平年にすると定めたのです。最近では1900年は平年で2000年は閏年となりました。
 日常的に必要となる暦法の問題として「指定された年月日が何曜日であるかを求める」ということがあります。ある暦における各年月日に対して、その暦の最初の日から経過した日数を対応させることによって、自然数とその暦の年月日を一対一に対応させることができます。曜日というのは日、月、火、水、木、金、土という七種類を繰り返して年月日を分類する ことですから、経過日数を法7で考えれば曜日を求めることができます。
 曜日と法7の完全剰余系との対応を次のように定めます。
曜日と法7の剰余系の対応
0123456
日月火水木金土
 グレゴリオ暦ではその最初の日である1582年10月15日が金曜日と定められましたが、経過日数をこの日から計算しようとするとやや複雑になりますので、1581年12月31日を0として、1582年1月1日を第1日目とするような経過日数を計算し、それを法7で考えます。
 まず、年数nが与えられたときに0年からn年までにある閏年の数を求める方法ですが、正の整数aについて、
[n
a		]
はn/aを超えない最大の整数を表わします。これはnを超えないaの正の倍数の個数と考えられますので、これを利用して閏年の数を計算します。
 (year,month,day)を年月日の指定する数の組としたとき、(year－1)年12月31日までの経過日数はすべてを平年と考えた経過日数
(year－1582) × 365
と1582年から(year－1)年までにあった閏年の数
lb36
[year
4		]
－
[year
100		]
+
[year
400		]
rb36 －lb36
[1582
4		]
－
[1582
100		]
+
[1582
400		]
rb36
の和になります。
 (month－1)月までの経過日数はその年が平年か閏年かで変わりますので、各月の日数表を2種類用意してそれを参照して計算することにします。この二つにdayを加えれば経過日数dが得られます。
 後は基準日である1581年12月31日が木曜日、法7で考えれば4となるので、d + 4を法7の完全代表系で表わせば曜日が求まります。これをプログラミングしてみましょう。

sample5.1.11.py

# -*- coding: utf-8 -*-
Common = [31,28,31,30,31,30,31,31,30,31,30,31]
Leap   = [31,29,31,30,31,30,31,31,30,31,30,31]
WeekChars = [u'日',u'月',u'火',u'水',u'木',u'金',u'土']
 
def DayOfWeek( year, month, day ):
  if ( year < 1582 ):
    raise ValueError, "Week:year error %d" % year
  if ( month < 1 ) or ( month > 12 ):
    raise ValueError, "Week:month error %d" % month
  if ( year % 4 == 0 ):
    if ( year % 100 == 0 ) and ( year % 400 != 0 ):
      DaysOfMonth = Common
    else:
      DaysOfMonth = Leap
  else:
    DaysOfMonth = Common
  if ( day < 1 ) or ( day > DaysOfMonth[month-1] ):
    raise ValueError, "Week:day error %d" % day
  a = (year-1582)*365 + (year/4) - (1582/4) \
    - (year/100) + (1582/100) + (year/400) - (1582/400) 
  b = 0
  for i in range( month - 1 ):
    b += DaysOfMonth[i]
  d = a + b + day
  w = ( d + 4 ) % 7
  return w
 
data = [(1582,10,15),(1623,6,19),(1643,1,4),(1777,4,30)]
for d in data:
  w = DayOfWeek( d[0], d[1], d[2] )
  print "%4d.%2d.%2d %s" % (d[0],d[1],d[2],WeekChars[w])

sample5.1.11.pyの実行結果

1582.10.15 金
1623. 6.19 月
1643. 1. 4 日
1777. 4.30 水

sample5.1.11.rb

# coding: utf-8
$Common = [31,28,31,30,31,30,31,31,30,31,30,31]
$Leap   = [31,29,31,30,31,30,31,31,30,31,30,31]
$WeekChars = ['日','月','火','水','木','金','土']
 
def DayOfWeek(year, month, day)
  if ( year < 1582 )
    raise ValueError, "Week:year error"
  end
  if ( month < 1 ) or ( month > 12 )
    raise ValueError, "Week:month error"
  end
  if ( year % 4 == 0 )
    if ( year % 100 == 0 ) and ( year % 400 != 0 )
      $DaysOfMonth = $Common
    else
      $DaysOfMonth = $Leap
    end
  else
    $DaysOfMonth = $Common
  end
  if ( day < 1 ) or ( day > $DaysOfMonth[month-1] )
    raise ValueError, "Week:day error"
  end
  a = (year-1582)*365 + (year/4) - (1582/4)
      - (year/100) + (1582/100) + (year/400) - (1582/400)
  b = 0
  for i in 0...(month - 1)
    b += $DaysOfMonth[i]
  end
  d = a + b + day
  w = ( d + 4 ) % 7
  return w
end
 
data = [[1582,10,15],[1623,6,19],[1643,1,4],[1777,4,30]]
for d in data
  w = DayOfWeek(d[0], d[1], d[2])
  printf "%4d.%2d.%2d %s\n", d[0], d[1], d[2], $WeekChars[w]
end

sample5.1.11.rbの実行結果

1582.10.15 金
1623. 6.19 月
1643. 1. 4 日
1777. 4.30 水

参考文献

[1] カール・フリードリヒ ガウス, ガウス 整数論, 朝倉書店, 1995
img
 
 
[2] 高木 貞治, 初等整数論講義 第2版, 共立出版, 1971
img
 
 
[3] 遠山 啓, 初等整数論, 日本評論社, 1972
img
 
 
[4] G.H. ハーディ, E.M. ライト, 数論入門〈1〉, シュプリンガー・フェアラーク東京, 2001
img
 
 
[5] 永田 久, 暦と占いの科学 (新潮選書), 新潮社, 1982
img
 
 
[6] 山崎 昭, 久保 良雄, 暦の科学―"時"を読む基礎知識, 講談社, 1984
img
 
 
註　　釈
*120世紀の考古学の進歩により、ピュタゴラス派の数学はバビロニアを起源としていることが次第にあきらかになってきている。
人　　物
ポリヤ Pòlya, George, 1887-1985
エドモンド・ハレー Halley, Edmond, 1656-1742
イギリスの天文学者、物理学者、数学者、気象学者。1705年にハレー彗星の軌道計算の結果から1758年に接近すると予言し、その通りになった。
ウィリアム・ハミルトン Hamilton, William Rowan, 1805-1865
アイルランドの数学者、天文学者。
ユリウス・カエサル Caesar, Gaius Iulius, B.C.100-B.C.44
古代ローマの政治家。
クリストファー・クラヴィウス Clavius, Christopher, 1538-1612
ドイツの数学者、天文学者。
 
自　　然
春分点 しゅんぶんてん, vernal equinox
太陽が南半球から北半球へ赤道面を通過する点。
 
数　　学
法 ほう, modulus
合同 ごうどう, congruent
剰余 じょうよ, residue
非剰余 ひじょうよ, non-residue
合同記号 ごうどうきごう
ガウスは『整数論』第1章 数の合同に関する一般的な事柄において'≡'を合同を表わす記号として用いた。
剰余類 じょうよるい, residue class
剰余系 じょうよけい, system of residues
完全剰余系 かんぜんじょうよけい, complete system of residues
 
Published by SANENSYA Co.,Ltd.