フェルマー・オイラーの定理について 風あざみ 2014/04/01 目次 1 証明の準備編 2 2 フェルマー・オイラーの定理の証明編 3 1 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 の存在が言えた。 □ 定理2:a, b, n を正の整数とする。a, n と b, n がともに互いに素となるとき、 ab, n も互いに素になる。 証明: 定理1より、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 も互いに素に なることがいえた。 □ 正の整数 n に対して ϕ(n) を以下のように定義する。 ϕ(n) = n 以下の正の整数のうち、n と互いに素となるものの個数 2 2 フェルマー・オイラーの定理の証明編 定理3:n を正の整数とする、n 以下の正の整数のうち、n と互いに素とな るものからなる集合 {a1 , a2 , · · · , aϕ(n) } をとる。この中から a を任意にとる。 {a · a1 , a · a2 , · · · , a · aϕ(n) } と、{a1 , a2 , · · · , aϕ(n) } は法 n において、同一の 集合である。 証明:定理2より、a · a1 , a · a2 , · · · , a · aϕ(n) は n と互いに素である。またあ る a · ai , a · aj が存在して、a · ai ≡ a · aj (mod n) となると仮定する。定理 1より、au ≡ 1 (mod n) をみたす整数 u が存在することがいえる。よって ai ≡ u(a · ai ) ≡ u(a · aj ) ≡ aj (mod n) いえるが、これは不合理。よって、 {a · a1 , a · a2 , · · · , a · aϕ(n) } と、{a1 , a2 , · · · , aϕ(n) } は法 n において、同一の 集合であることがいえた。 □ 定理4:a, n を互いに素な正の整数とする。このとき、以下が言える。 aϕ(n) ≡ 1 (mod n) 証明:定理3で取り上げた集合 {a1 , a2 , · · · , aϕ(n) } をとる。定理3より、{a · a1 , a · a2 , · · · , a · aϕ(n) } と、{a1 , a2 , · · · , aϕ(n) } は法 n において、同一の集合 である。よって以下が言える。 (a · a1 )(a · a2 ) · · · (a · aϕ(n) ) ≡ a1 , a2 , · · · aϕ(n) aϕ(n) a1 a2 · · · aϕ(n) ≡ a1 a2 · · · aϕ(n) 定理1より a1 u1 ≡ 1 (mod n)、a2 u2 ≡ 1 (mod n) (mod n) (mod n)、· · ·、aϕ(n) uϕ(n) ≡ 1 (mod n) をみたす整数 u1 , u2 , · · · , uϕ(n) の存在が言えるから aϕ(n) a1 a2 · · · aϕ(n) u1 u2 · · · uϕ(n) ≡ a1 a2 · · · aϕ(n) u1 u2 · · · uϕ(n) したがって、a ϕ(n) ≡1 (mod n) (mod n) がいえる。 よって、定理4がなりたつことがいえた。 定理4はフェルマー・オイラーの定理そのものである。 3 □
© Copyright 2024