このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 整数の合同 へ行く。

*目次 [#p97e65ca]

#contents


*合同式 [#pe7bc4a3]

[例]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)) ◇

[例]2SUP{71};≡-17×6SUP{833}; (mod 5)が成り立つことを確かめる。

2SUP{2};≡-1 (mod 5)を活用すると、

2SUP{71};≡2SUP{2×35+1};≡(-1)SUP{35};×2≡-2 (mod 5) ←(*)

になる。

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

6SUP{833};≡1SUP{833};≡1 (mod 5)

となる。

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

-17×6SUP{833};≡-17×1≡-2 (mod 5) ←(**)

となる。

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

[問題]11|(2SUP{13};×3SUP{17};+5SUP{19};×7SUP{24};)を示せ。

*合同式xSUP{2};≡-1 (mod p) [#p0fbf114]

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

xSUP{2};≡-1 (mod p) ←(*)

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

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

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

|x|0|1|2|3|4|5|6|
|xSUP{2};|0|1|4|9≡2|16≡2|25≡4|36≡1|

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

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

|x|0|1|2|3|4|5|6|7|8|9|10|11|12|
|xSUP{2};|0|1|4|9|3|12|10|10|12|3|9|4|1|

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

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

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

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

[証明]整数xがxSUP{2};≡1 (mod p)を満たすとする。

すると、p|(xSUP{2};-1)である。

p|(x-1)(x+1) (∵xSUP{2};-1=(x-1)(x+1))

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

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

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

[2]pが奇素数のとき

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

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

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

しかし、(*)により、xSUP{2};≠1 (mod p)である(pが奇数なので、-1≠1 (mod p)である)。~
すると、4|φ(p)である。なぜならば[命題]「(a,m)=1とし、d=ordSUB{m};(a)と置く。整数kについて、aSUP{k};≡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とおく。

&mimetex("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)

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

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

(1)(2)によって、次が得られる。

&mimetex("(p-1)!");~
&mimetex("=1 \times 2 \times \cdots \times (\frac{p-1}{2}) \times \frac{p+1}{2} \times \cdots \times (p-2) \times (p-1)");~
&mimetex("\equiv x^2 \, (mod \, p))");

ウィルソンの定理より、(p-1)!≡-1 (mod p)なので、以下が成り立つ。

&mimetex("x^2 \equiv -1 \, (mod \, p))");

よって、xが(*)の解である。 □


*参考文献 [#a946552f]

-『算数からはじめよう!数論』