雑記 (28)

前回求めた関係は、 p素数のとき

 (a+b)^p \equiv a^p + b^p (\mathrm{mod}\, p)

ということであり、容易に多変数でも成り立つことがわかる。特に、

 (1+1+\cdots+1)^p \equiv 1^p+1^p+\cdots+1^p (\mathrm{mod}\, p)

から、フェルマーの小定理が得られる。すなわち、

 a^p \equiv a \,(\mathrm{mod} \, p)

つまり、 a \not\equiv 0 \,(\mathrm{mod}\, p) であれば、

 a^{p-1} \equiv 1 \,(\mathrm{mod} \, p)

である。しかし、こんな風にしなくても、前々回の記事でやったように、 \mathbb{Z}/p\mathbb{Z} の 0 を除いた乗法テーブル (掛け算の表) が群構造ですべて閉じている (表が列、行がもれなくダブリなく埋まっている) ことから、結局、要素の置換になっているに過ぎぬという事実を利用すれば、

 (a\cdot 1)(a \cdot 2) \cdots (a(p-1)) \equiv 1\cdot2 \cdots (p-1)

から

 a^{p-1} \equiv 1 \,(\mathrm{mod} \, p)

がすぐに得られる。

これをもっと一般化したのがオイラーの定理である。オイラーの定理の場合は、 p素数である必要はないが、その代わりに  a, p は互いに素であるという条件が必要になる。 p素数とは限らないので、以下では間違えないように記号を  m に変える。


「互いに素である自然数  a, m について、

 a^{\phi(m)} \equiv 1 \,(\mathrm{mod}\, m)

が成立する。なお、 \phi(m) は「オイラー函数」と呼ばれるもので、自然数の集合、

 \{1,\cdots, m-1\}

で、 m と互いに素な集合の要素の個数を与えるものである」

すぐにわかるのは、 m p (素数)としたとき、

 \phi(p) = p - 1

で、 a, p はもちろん互いに素だから、オイラーの定理は、フェルマーの小定理を与えるということである。

証明は、まったく同じように考えればよい。

(証明)

 \{1,\cdots, m-1\}

から、 m と素である要素を取り出して部分集合  Mを作る。

 M = \{h_1, h_2,\cdots, h_{\phi(m)}\}

ここで、

 aM = M  \,(\mathrm{mod}\,m)

である。以下、その証明。 a, h_i は、 m と素なので  ah_i m と素である。そうすると、 ah_i \,(\mathrm{mod} \,m) は、集合  M に属するから、 M から  M への写像  h_i \mapsto ah_i を定義できる。このとき、 ah_i \equiv ah_j \,(\mathrm{mod} \,m) 、つまり、 a(
h_i - h_j) \equiv 0 \,(\mathrm{mod} \,m)
ならば、 h_i \equiv h_j \, (\mathrm{mod} \, m) となって単射となり、したがって全射でもある。

以上のことから、

 (ah_1)(ah_2)\cdots(ah_{\phi(m)})\\
= a^{\phi(m)}(h_1 h_2 \cdots h_\phi(m))\\
\equiv h_1h_2\cdots h_{\phi(m)} \,(\mathrm{mod} \,m)

が成立する。 h_1h_2\cdots h_{\phi(m)} m と互いに素なので、

 (h_1h_2 \cdots h_{\phi(m)})x + my= 1

となる整数  x, y が存在し、同じことだが、

 (h_1h_2 \cdots h_{\phi(m)})x  \equiv 1 \,(\mathrm{mod}\,m)

となる。以上より

 a^\phi(m) \equiv 1 \,(\mathrm{mod}\, m)

が証明された。//

(活用例)

リンちゃんは、おかあさんから 1 個 66 円の柿と 1 個 35 円の蜜柑をあわせて 3,890 円買ってきてといわれました(なんと理不尽なおかあさん!)。

柿の数を x 個、蜜柑の数をy個とすると、

 66x + 35y = 3890

となるが、そもそも、そのような整数解があるかどうかは、66 と 35 の最大公約数をしらべればわかるのだった(単項イデアル!)。ユークリッドの互除法を適用してみると、

 66 - 35  = 31\\
35 - 31 = 4\\
31 - 4\times7 =  31 - 28 = 3
 28 - 3 \times 9 = 28  - 27 = 1\\
27 - 1\times 27 = 0

なので、最大公約数は 0 になる前の 1 である。つまり、66 と 35 は互いに素である。したがってリンちゃんにとって残念なことに、整数解  x, y は存在する。

 66x + 35y = 3890

 66x \equiv  31x \,(\mathrm{mod}\,35)

 3890 = 3500 +350 + 35 +5

から、

 31x  \equiv 5 \,(\mathrm{mod}\, 35)

となる整数 x を求めれば良いことがわかった。

1 から 34 までの数字で、35= 5 \times 7 と互いに素でないものは、

 5, 7, 10, 14, 15, 20, 21,  25, 28, 30

の 10 個ある。そうすると、オイラーの関数の値は、

 \phi(35) = 34 -10 = 24

となり、オイラーの定理を適用すると、

 31^{24} \equiv 1 \,(\mathrm{mod}\, 35)

となる。求める  x は、

 31x \equiv 5\times 31^{24} \,(\mathrm{mod}\,35)
 x \equiv 5 \times 31^{23} \,(\mathrm {mod}\, 35)

を簡単にすればいい。以下、すべて  \mathrm{mod}\, 35 での計算とする。

 x\\
\equiv 5 \times (-4)^{23} \\
\equiv 5 \times ((-4)^2)^{11}\times(-4)\\
\equiv 15\times (16^2)^5\times16
 \equiv 15\times 11^5 \times 16\\
\equiv 15\times 16^2\times11\times16\\
\equiv 15\times 11^2 \times 16
 \equiv 15\times16^2\\
\equiv 15 \times 11\\
\equiv 25

 x =25 とすると、y=64

 x, y > 0 でこれ以外の整数の組み合わせはない。こたえは、柿 25 個、蜜柑 64 個。