ガウスの補題について

ガウスの予備定理について
風あざみ
2016/01/30
目次
1
証明の準備編
2
2
ガウスの予備定理の証明編
3
1
1
証明の準備編
定理１：a, n を互いに素な正の整数とする。このとき、ax + ny = 1 をみた
す整数 x, y が存在することが言える。
証明：整数の集合 I を以下のように定義する。
I = {k は整数 | 整数 s, t を用いて、k = as + nt とかける。}
a = a · 1 + n · 0 ∈ I, n = a · 0 + n · 1 ∈ I
だから、I は正の整数 a, n を元に持つ。 I の正の元のうち、最小になるもの
を e とする。I の元 k を任意にとるとき、k は e で割り切れることを証明す
る。まず k が e で割り切れないと仮定する。このとき、k を e で割った時の
商を q 、余りを r とすると、以下のように書ける。
k = eq + r, 0 < r < e
ここで、k, e ∈ I だから整数 s, t, u, v が存在して、以下のように書ける。
k = as + nt, e = au + nv
r = k − eq = a(s − uq) + n(t − vq) ∈ I だから、r は I の元となる。ところが
0 < r < e だから、r は e より小さな正の整数であることがわかる。このこと
は、e の最小性に反する。したがって、k が e で割り切れないという仮定は誤
りで、k は e で割り切れることが証明された。特に、I の元 a, n が e で割り
切れることがいえる。e ≥ 2 と仮定すると、e が a, n の 2 以上の公約数とな
り、a, n を互いに素であることに反する。よって、e = 1 であること、つまり
au + nv = 1 が証明された。
以上より、ax+ny = 1 をみたす整数 x, y の存在が言えた。
□
定理２：a, b, n を正の整数とする。a, n と b, n がともに互いに素となるとき、
ab, n も互いに素になる。
証明：定理１より、ax + ny = 1, bx + ny = 1 の整数解をもつことがいえ
る。ax + ny = 1 の整数解を (x1 , y1 )、bx + ny = 1 の整数解を (x2 , y2 ) とす
ると、ab(x1 x2 ) + n(ax1 y2 + bx2 y1 + ny1 y2 ) = 1 ここで、ab, n の最大公約数
d を取ると、d は明らかに 1 の約数である。したがって、ab, n も互いに素に
なることがいえた。
□
定理３：a, n を正の整数とする。a, n が互いに素となるとき、n − a, n も互い
に素になる。
2
証明：n − a, n が公約数 c > 1 を持つと仮定する。このとき、a = n − (n − a)
より、a は明らかに c で割り切れる。n は c で割り切れるから、n, a は公約数
c > 1 をもつことが言えるが、これは不合理である。
以上より、n−a, n も互いに素になることがいえた。
□
正の整数 n に対して ϕ(n) を以下のように定義する。
ϕ(n) = n 以下の正の整数のうち、n と互いに素となるものの個数
また定理３の系として、以下が言える。
定理３の系：正の整数 n に対して、gcd(n, a) = 1, 1 ≤ a <
a の個数と gcd(n, a) = 1,
n
2
n
2
をみたす整数
< a ≤ n − 1 をみたす整数 a の個数は等しい。
証明：gcd(n, a) = 1, 1 ≤ a <
n
2
をみたす整数 a を任意に取る。このとき、
定理３より、n − a は gcd(n, n − a) = 1,
< n − a ≤ n − 1 をみたすこと
がいえる。したがって、{gcd(n, a) = 1, 1 ≤ a < n2 をみたす整数 a の個数
} ≤ {gcd(n, a) = 1, n2 < a ≤ n − 1 をみたす整数 a の個数 } であることが
n
2
< a ≤ n − 1 をみたす整数 a を任意に取る。
このとき、定理３より、n − a は gcd(n, n − a) = 1, 1 ≤ n − a < n2 をみた
いえる。また、gcd(n, a) = 1,
n
2
すことがいえる。したがって、{gcd(n, a) = 1,
< a ≤ n − 1 をみたす整数
a の個数 } ≤ {gcd(n, a) = 1, 1 ≤ a < をみたす整数 a の個数 } であるこ
とがいえる。以上より、{gcd(n, a) = 1, 1 ≤ a < n2 をみたす整数 a の個数
n
2
n
2
} = {gcd(n, a) = 1,
えた。
n
2
< a ≤ n − 1 をみたす整数 a の個数 } であることがい
□
n が奇数のとき、 n2 は整数になり得ず、また n が 4 以上の偶数のとき、 n2 , n
は 1 より大きな公約数 n2 を持つので、 n2 , n は互いに素ではない。
したがって、定理３の系より、n を 3 以上の整数とするとき、ϕ(n) は偶数に
なることが言える。
このとき、gcd(n, a) = 1, 1 ≤ a <
1,
2
n
2
n
2
をみたす整数 a の個数と gcd(n, a) =
< a ≤ n − 1 をみたす整数 a の個数はともに、 ϕ(n)
2 になる。
ガウスの予備定理の証明編
a, n を互いに素な正の整数 (ただし、n ≥ 2) とするとき、整数 ϵ(a, n) を以
下にように定義する。
a を n で割ったときの絶対値最小の余りが正のとき、ϵ(a, n) = 1
a を n で割ったときの絶対値最小の余りが負のとき、ϵ(a, n) = −1
以降簡単のため、ϵ(a, n) を ϵ(a) と書くことにする。
3
定理３：n を 3 以上の整数とする、n2 未満の正の整数のうち、n と互いに素とな
るものからなる集合 {a1 , a2 , · · · , a ϕ(n) } をとる。この中から a を任意にとる。
2
{a · a1 , a · a2 , · · · , a · a ϕ(n) } と、{ϵ(a · a1 )a1 , ϵ(a · a2 )a2 , · · · , ϵ(a · a ϕ(n) )a ϕ(n) }
2
2
2
は法 n において、同一の集合である。
証明：定理２より、a · a1 , a · a2 , · · · , a · a ϕ(n) は n と互いに素である。また
2
ある a · ai , a · aj が存在して、a · ai ≡ a · aj
(mod n) となると仮定する。
定理１より、au ≡ 1
(mod n) をみたす整数 u が存在することがいえる。
(mod n) がいえるが、これは不合
理。そして、ある a · ai , a · aj が存在して、a · ai ≡ −a · aj (mod n) と
よって ai ≡ u(a · ai ) ≡ u(a · aj ) ≡ aj
なると仮定する。定理１より、au ≡ 1
(mod n) をみたす整数 u が存在す
(mod n) がい
ることがいえる。よって ai ≡ u(a · ai ) ≡ −u(a · aj ) ≡ −aj
える。したがって、ai + aj ≡ 0
(mod n) かつ 0 < ai + aj < n がいえる
が、これは不合理。よって、{a · a1 , a · a2 , · · · , a · a ϕ(n) } と、{ϵ(a · a1 )a1 , ϵ(a ·
2
a2 )a2 , · · · , ϵ(a · a ϕ(n) )a ϕ(n) } は法 n において、同一の集合であることがいえ
2
た。
2
□
定理４：a, n を互いに素な正の整数とする。このとき、以下が言える。
a
ϕ(n)
2
≡ ϵ(a · a1 )ϵ(a · a2 ) · · · ϵ(a · a ϕ(n) ) (mod n)
2
証明：定理３で取り上げた集合 {a1 , a2 , · · · , a ϕ(n) } をとる。定理３より、{a ·
2
a1 , a · a2 , · · · , a · a ϕ(n) } と、{ϵ(a · a1 )a1 , ϵ(a · a2 )a2 , · · · , ϵ(a · a ϕ(n) )a ϕ(n) } は
2
2
2
法 n において、同一の集合である。よって以下が言える。
(a · a1 )(a · a2 ) · · · (a · a ϕ(n) )
2
≡ (ϵ(a · a1 )a1 )(ϵ(a · a2 )a2 ) · · · (ϵ(a · a ϕ(n) )a ϕ(n) ) (mod n)
2
a
ϕ(n)
2
2
a1 a2 · · · aϕ(n)
≡ ϵ(a · a1 )ϵ(a · a2 ) · · · ϵ(a · a ϕ(n) ) · a1 a2 · · · a ϕ(n)
2
(mod n)
2
定理１より a1 u1 ≡ 1
(mod n)、a2 u2 ≡ 1 (mod n)、· · ·、a ϕ(n) u ϕ(n) ≡ 1
2
2
(mod n) をみたす整数 u1 , u2 , · · · , uϕ(n) の存在が言えるから
a
ϕ(n)
2
a1 a2 · · · a ϕ(n) u1 u2 · · · u ϕ(n)
2
2
≡ ϵ(a · a1 )ϵ(a · a2 ) · · · ϵ(a · a ϕ(n) ) · a1 a2 · · · a ϕ(n) u1 u2 · · · u ϕ(n)
2
よって、a
ϕ(n)
2
2
(mod n)
2
≡ ϵ(a · a1 )ϵ(a · a2 ) · · · ϵ(a · a ϕ(n) ) (mod n) がいえる。
2
よって、定理４がなりたつことがいえた。
4
□
特に、定理４の n = p(ただし、p は素数とする) の場合、ガウスの予備定理
そのものである。
a
p−1
2
≡ ϵ(a)ϵ(2a) · · · ϵ(
p−1
a) (mod p)
2
5

Download Report