オイラーのトーシェント (ファイ) 関数で, が成り立つことを高校数学範囲で証明してみた. とか の値を求めよなんていう入試問題があったが, はともかく, を集合の包除を使って数え上げるのは時間の無駄にしか思えない.
【問】
正の整数 , について, , が互いに素であるであることと, 整数 , が存在して, をみたすことは同値なことを示せ.
【解】
まず, , が互いに素であるとする.
で表される正の整数は存在するから, そのうちの最小の正の整数を とし (自然数の空でない部分集合に最小値が存在するのは公理である), と表わす (, は整数).
を で割り, 商 , 余り として, と書ける. すると,
となって, を の形に表わすことができる. は余りで, であるが, だとすると, が, で表される最小の正の整数であることに矛盾する. したがって, である. これから, である.
まったく同様の議論で, は で割り切れ, 商を として, となる.
, は互いに素であるから, である. したがって, 整数 , が存在して, をみたす.
今度は, 整数 , が存在して, をみたすとする.
, の最大公約数を として, , (, は正の整数) とすると,
から, となり, と は互いに素である.
//
※ 上の命題は, または の整数の場合でも, , とすれば, の場合に帰着でき, 成立する.//
次は, 中国剰余定理の証明.
【問】
正の整数 , が互いに素であるならば, 任意の整数 , に対し,
を満たす整数 が存在し, で唯一の解をもつ.
【解】
正の整数 , は互いに素であるので,
をみたす, 整数 , が存在する. したがって,
となる. そこで,
とおくと,
となるが,
なので,
同様にして,
となる. が でただ一つ存在することを示すために,
とすると,
かつ
なので, は, でも でも割り切れ,
となって, 一致する. したがって一意性が示せた.
【問】
, が互いに素な正の整数であるとき, が成立する. ただし, は, オイラーのトーシェント関数である.
【解】
と互いに素であり, かつ 以下の自然数の集合を , と互いに素である 以下の自然数の集合を とする. 集合 の要素の個数は であり, 集合 の要素の個数は, である. 集合 から要素 を取り出し, また集合 から要素 を取り出し, 順序対 を作る. その順序対の集合を と書く. この集合の個数は, である. さらに, と互いに素であり, かつ 以下の自然数の集合を とする. 集合 の要素の個数は, である. を示すために, 集合 から集合 への全単射写像 (上への 対 写像, 双射ともいう) が存在することを以下に示す.
集合 から, 任意の要素 をひとつとり, で割った余りを , で割った余りを とする (余りの一意性からただ一つ値が定まる). すなわち,
だが, は と互いに素だから, , とも素である. したがって, ユークリッド互除法より,
となり, ということがわかる. 集合 の任意の要素 を 集合 の要素 にこのようにひとつ対応させるやり方は, 集合 から, 集合 への写像となる.
中国剰余定理から, 任意の に対し,
を満たす整数 が, で, ただひとつ定まる.
と は互いに素なので, 互除法の原理から, と も互いに素である. 同様にして, と も互いに素である. すると,
,
となる整数 , , , が存在するが, 両式をかけあわせて整理すると,
となり, これから, と も素であることがいえる. したがって, である.
任意の に対して, が常に存在し, しかもただ一つに定まるので, いま考えている写像は全射かつ単射 (全単射) であることがいえた. したがって, 集合 と集合 の要素数は同じで, である.
//