Security Akademeia

目次 †

目次
合同式
合同式x2≡-1 (mod p)
参考文献

↑

合同式 †

[例]815013723≡3 (mod 4)が成り立つことを確かめる。

815013723
=815013700×100+23
≡815013700×0+23 (mod 4)　（∵100≡0 (mod 4))
≡23 (mod 4)
≡20+3 (mod 4)
≡3 (mod 4)　(∵20≡0 (mod 4))　◇

[例]271≡-17×6833 (mod 5)が成り立つことを確かめる。

22≡-1 (mod 5)を活用すると、

271≡22×35+1≡(-1)35×2≡-2 (mod 5)　←(*)

になる。

また、6≡1 (mod 5)であることから、

6833≡1833≡1 (mod 5)

となる。

示したい合同式の右辺は、

17×6833≡-17×1≡-2 (mod 5)　←(**)

となる。

したがって、(*)と(**)は一致する。　◇

[問題]11|(213×317+519×724)を示せ。

↑

合同式x2≡-1 (mod p) †

　どんな素数pについて、次の合同式は解を持つのか、つまり、この合同式を満たす整数xが存在するためのpの条件は何かを調べる。

x2≡-1 (mod p)　←(*)

　この合同式の解としての√(-1)は、虚数単位のi(=√(-1))とはまったく別物である。

[例]p=7の場合に、(*)を考察する。

7を法として平方を計算すると、次の表が得られる。

x	0	1	2	3	4	5	6
x2	0	1	4	9≡2	16≡2	25≡4	36≡1

1≡6 (mod 7)であり、表のx2の項には6が現れないので、x2≡-1 (mod 7)に解がないことがわかる。　◇

[例]p=13の場合に、(*)を考察する。

x	0	1	2	3	4	5	6	7	8	9	10	11	12
x2	0	1	4	9	3	12	10	10	12	3	9	4	1

1≡12 (mod 13)であり、表のx2の項にはx≡5と8のときに12が現れるので、x≡5と8のときにx2≡-1 (mod 13)は解を持つ。　◇

　上記の例により、p=7のときには(*)は解を持たず、p=13のときには(*)は解を持つ。このようにpの値によって、(*)が解を持つかどうかが決まる。

　実は、(*)が解を持つ条件は、p=2またはp≡1 (mod 4)であることがわかっている。即ち、pの条件は唯一の偶素数である2であるか、1型の素数であることである。
　p=13は1型の素数であるため、(*)が解を持つ条件を満たす。

[補題]pが素数のとき、合同式x2≡1 (mod p)の解は、x≡±1 (mod p)だけである。

[証明]整数xがx2≡1 (mod p)を満たすとする。

すると、p|(x2-1)である。

p|(x-1)(x+1)　（∵x2-1=(x-1)(x+1)）

このとき、pは素数であるから、p|(x-1) or p|(x+1)が成り立つ。これは、x≡1 (mod p) or x≡-1 (mod p)が成り立つということなので、補題が証明された。　□

[定理]合同式x2≡-1 (mod p)が解を持つための必要条文条件は、p=2 or p≡1 (mod 4)である。

[証明][1]p=2のとき、x2≡-1≡1 (mod 2)となり、x=1が解となる。よって、p=2のときに、(*)は解がある。

[2]pが奇素数のとき

(i)p≡3 (mod 4)の場合、即ち3型の素数の場合に、(*)が解を持たないことを示す。

背理法を用いる。(*)の解となる整数xが存在したと仮定する。

このとき、x4≡(-1)^2≡1 (mod p)が成り立つので、xのpを法とする位数ordp(x)は4の約数である。

しかし、(*)により、x2≠1 (mod p)である（pが奇数なので、-1≠1 (mod p)である）。
すると、4|φ(p)である。なぜならば[命題]「(a,m)=1とし、d=ordm(a)と置く。整数kについて、ak≡1 (mod m)となるための必要十分条件は、d|kである」が成り立つからである。

4|φ(p)
4|p-1　（∵φ(p)=p-1）

しかし、これはp≡3 (mod 4)という仮定に矛盾している。

よって、pが3型の素数のときには、(*)には解がない。

(ii)p≡1 (mod 4)の場合、即ち1型の素数の場合に、(*)が解を持つことを示す。

証明方針としては、ウィルソンの定理を用いて、(*)の解を作る。

1からp-1までのp-1個の数を、「前半」（1から(p-1)/2まで）と「後半」（(p+1)/2からp-1まで）に分けて、前半の数すべての積をxとおく。

$x=1~\times~2~\times~\cdots~\times~(\frac{p-1}{2})$ 　←(1)

後半の数については、以下を考慮する。

(p-1)≡-1,(p-2)≡-2,…,(p+1)/2≡-(p-1)/2 (mod p)

これらをすべて掛け合わせると次が得られる。

$(\frac{p+1}{2}~\times~\cdots~\times~(p-2)~\times~(p-1)~\equiv~(-1)^{\frac{p-1}{2}}x~\,~(mod~\,~p))$
$(\frac{p+1}{2}~\times~\cdots~\times~(p-2)~\times~(p-1)~\equiv~x~\,~(mod~\,~p))$ 　←(2)　（∵p≡1 (mod 4)であることから、(p-1)/2は偶数である。よって、 $(-1)^{\frac{p-1}{2}}~=~1$ ）