>>720
任意の2個の整数が互いに素ならば(a, bc)=1になるから
φ(abc)=φ(a)φ(bc)=φ(a)φ(b)φ(c)となる。何個あっても同じである。
これを用いると
φ(n)=φ(p^α)φ(q^β)…
=p^α(1-1/p)q^β(1-1/q)…
=n(1-1/p)(1-1/q)…となり証明された。
(r+nt, n)=(r, n)
nを法としての既約類の数がφ(n)
すなわち既約剰余系の数がφ(n)
ay+bx=k、(a, B)=1
ay+bbx=abより
φ(a)φ(b)=φ(ab)となる。

例えば3y+5x=15のすると
(3, 5)=1、φ(3)=2、φ(5)=4
φ(15)=8。
1 2
1 2 3 4
1 2 4 7 8 11 13 14
1 7 13 4 11 2 8 14