ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (264)

オイラーのトーシェント (ファイ) 関数で,  \phi(ab) = \phi(a)\phi(b) が成り立つことを高校数学範囲で証明してみた.  \phi(1024) とか  \phi(2015) の値を求めよなんていう入試問題があったが,  \phi(1024) はともかく,  \phi(2015) を集合の包除を使って数え上げるのは時間の無駄にしか思えない.

 \phi(2015) 
\\= \phi(5\times 13 \times 31) 
\\= \phi(5)\phi(13)\phi(31)
\\= (5-1)(13-1)(31-1)
\\= 1440


【問】
正の整数  a, b について,  a, b が互いに素であるであることと, 整数  s, t が存在して,  as + bt = 1 をみたすことは同値なことを示せ.

【解】
まず,  a, b が互いに素であるとする.

 aX+bY で表される正の整数は存在するから, そのうちの最小の正の整数を d とし (自然数の空でない部分集合に最小値が存在するのは公理である),  d = as + bt と表わす ( s,  t は整数).

 a d で割り, 商 q, 余り r として,  a = dq+r と書ける. すると,

 \begin{eqnarray}
r &=& a-dq
\\&=& a-(as+bt)q
\\&=& a(1-s)+b(-tq)
\end{eqnarray}

となって,  r aX+bY の形に表わすことができる. r は余りで,  0 \leq r < d であるが,  r \neq 0 だとすると,  d が,  aX+bY で表される最小の正の整数であることに矛盾する. したがって,  r = 0 である. これから,  a = dq である.

まったく同様の議論で,  b d で割り切れ, 商を q' として,  b = dq' となる.

 a, b は互いに素であるから,  d=1 である. したがって, 整数  s, t が存在して,  as + bt = 1 をみたす.

今度は, 整数  s, t が存在して,  as + bt = 1 をみたすとする.

 a, b の最大公約数を  d として,  a = da',  b = db' ( a',  b' は正の整数) とすると,

 d(a's + b't) = 1 から,  d = 1 となり,  a b は互いに素である.
//
※ 上の命題は,  a <0 または  b <0 の整数の場合でも,  as = (−a)(−s),  bt = (−b)(−t) とすれば, a, b > 0 の場合に帰着でき, 成立する.//

次は, 中国剰余定理の証明.

【問】
正の整数  m, n が互いに素であるならば, 任意の整数 a, b に対し,

 x \equiv a \pmod{m}
 x \equiv b \pmod{n}

を満たす整数  x が存在し,  \bmod{mn} で唯一の解をもつ.

【解】
正の整数  m,  n は互いに素であるので,

 mp+ nq = 1

をみたす, 整数  p, q が存在する. したがって,

 mp \equiv 1 \pmod{n}
 nq \equiv 1 \pmod{m}

となる. そこで,

 x = mpb+nqa とおくと,

 x \equiv nqa \pmod{m}

となるが,  nq \equiv 1 \pmod{m}

なので,

 x \equiv a \pmod{m}

同様にして,

 x \equiv b \pmod{n}

となる.  x \bmod{mn} でただ一つ存在することを示すために,

 y \equiv a \pmod{m}
 y \equiv b \pmod{n}

とすると,

 x-y \equiv 0 \pmod{m}

かつ

 x-y \equiv 0 \pmod{n}

なので,  x-y は, m でも  n でも割り切れ,

 x-y \equiv 0 \pmod{mn}
 x \equiv y \pmod{mn}

となって, 一致する. したがって一意性が示せた.

【問】
 a,  b が互いに素な正の整数であるとき,  \phi(ab) = \phi(a)\phi(b) が成立する. ただし,  \phi は, オイラーのトーシェント関数である.

【解】
 a と互いに素であり, かつ  a 以下の自然数の集合を  A,  b と互いに素である  b 以下の自然数の集合を  B とする. 集合  A の要素の個数は  \phi(a) であり, 集合  B の要素の個数は,  \phi(b) である. 集合  A から要素  p を取り出し, また集合  B から要素 q を取り出し, 順序対  (p, q) を作る. その順序対の集合を  A \times B と書く. この集合の個数は,  \phi(a)\phi(b) である. さらに,  ab と互いに素であり, かつ ab 以下の自然数の集合を  C とする. 集合  C の要素の個数は,  \phi(ab) である.  \phi(ab) = \phi(a)\phi(b) を示すために, 集合  C から集合  A \times B への全単射写像 (上への 11 写像, 双射ともいう) が存在することを以下に示す.

集合 C から, 任意の要素  x をひとつとり,  a で割った余りを  r,  b で割った余りを  r' とする (余りの一意性からただ一つ値が定まる). すなわち,

 x \equiv r \pmod{a}
 x \equiv r' \pmod{b}

だが,  xab と互いに素だから,  a,  b とも素である. したがって, ユークリッド互除法より,

 \mathrm{gcd}(x,a)= \mathrm{gcd}
(a,r)=1
 \mathrm{gcd}(x,b)= \mathrm{gcd}
(b,r')=1

となり,  (r,r') \in A\times B ということがわかる. 集合  C の任意の要素  x を 集合  A \times B の要素  (r,r') にこのようにひとつ対応させるやり方は, 集合  C から, 集合  A \times B への写像となる.

中国剰余定理から, 任意の  (r,r') \in A\times B に対し,

 \begin{eqnarray}
x &\equiv& r \pmod{a}\\
x &\equiv& r' \pmod{b}
\end{eqnarray}

を満たす整数  x が,  \bmod{ab} で, ただひとつ定まる.

 r a は互いに素なので, 互除法の原理から,  x a も互いに素である. 同様にして,  x b も互いに素である. すると,

 xs + at = 1,  xu + bv =1

となる整数  s, t, u,  v が存在するが, 両式をかけあわせて整理すると,

 x(sux + bsv +atu)+ab(tv) = 1

となり, これから,  x ab も素であることがいえる. したがって, x \in C である.

任意の  (r,r') \in A \times B に対して,  x \in C が常に存在し, しかもただ一つに定まるので, いま考えている写像は全射かつ単射 (全単射) であることがいえた. したがって, 集合 C と集合  A \times B の要素数は同じで,  \phi(ab) = \phi(a)\phi(b) である.
//