フェルマー・オイラーの定理について

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

Download Report