問題
φ(n)=6を満たす自然数nを求めよ。ただし、φ(n)はオイラー関数である。
解答
nを素因数分解してn=p1^e1・・・ps^esとすると、定理3.3より、
φ(n)=n(1-1/p1)(1-1/p2)・・・(1-1/ps)
=p1^(e1-1)・(p1-1)・p2^(e2-1)・(p2-1)・・・ps^(es-1)・(ps-1)
そこで、6=p1^(e1-1)・(p1-1)・・・ps^(es-1)・(ps-1)なる式を考えると、nの素因数として現れるpiはpi≦7でなければならない。このような素数は、2,3,5,7で全部である。このとき、pi-1にあたるものは1,2,4,6である。したがって、nの素因数である可能性のあるpiは2,3,7であることがわかる。すなわち、nは次の形をしている。
n=2^α・3^β・7^γ(0≦α,0≦β,0≦γ)
はじめに、nは3と7の積の形にはなり得ない。何故ならば、n=3^β・7^γとすると、
φ(n)=3^(β-1)・(3-1)・7^γ・(7-1)=12・3^(β-1)・7^γ≠6
また、n=2^αとすると、
φ(n)=2^(α-1)・(2-1)=2^(α-1)≠6
したがって、n=2^α・3^β(0≦α,0≦β)―――① n=2^α・7^γ(0≦α,0≦γ)―――② の場合を考えればよい。
①の場合を調べる。さらに、α=0のとき、n=3^βであるから、
6=φ(n)=3^(β-1)・(3-1)=2・3^(β-1)
ゆえに、3=3^(β-1)であるから、β=2である。したがって、このとき、n=3^2=9
n=2^α・3^β(1≦α,0≦β)のとき、
6=φ(n)=2^(α-1)・(2-1)・3^(β-1)・(3-1)より、3=2^(α-1)・3^(β-1) ゆえに、α=1,β=2 したがって、このとき、n=2^1・3^2=18
②の場合を調べる。さらに、α=0のとき、n=7^γであるから、
6=φ(n)=7^(γ-1)・(7-1)=6・7^(γ-1)
ゆえに、1=7^(γ-1)であるから、γ=1である。したがって、このとき、n=7^1=7
n=2^α・7^γ(1≦α,0≦γ)のとき、
6=φ(n)=2^(α-1)・(2-1)・7^(γ-1)・(7-1)
ゆえに、1=2^(α-1)・7^(γ-1)であるから、α=1,γ=1である。したがって、このとき、n=2^1・7^1=14
以上によって、φ(n)=6を満たす自然数は7,9,14,18である。
定理3.3
n=p1^e1・p2^e2・・・ps^es(piは互いに異なる素数,ei≧1)であれば、次の式が成り立つ。
φ(n)=n(1-1/p1)(1-1/p2)・・・(1-1/ps)
引用終わり
問題
(1)「piはpi≦7でなければならない」理由を述べて下さい。
(2)「piは2,3,7であることがわかる」pi=5が抜ける理由を述べて下さい。
(3)「φ(n)=3^(β-1)・(3-1)・7^γ・(7-1)=12・3^(β-1)・7^γ≠6」γの所がγ-1でない理由を述べて下さい。
(4)「また、n=2^αとすると、φ(n)=2^(α-1)・(2-1)=2^(α-1)≠6」これを「n=2^α・3^β(1≦α,0≦β)のとき」と個別にやる理由を述べて下さい。
おまけ: