陥没地帯 (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$ への全単射写像 (上への $1$ 対 $1$ 写像, 双射ともいう) が存在することを以下に示す.

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

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

だが, $x$ は $ab$ と互いに素だから, $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)$ である.
//