level 1
n=3,15(mod 18),所以(3, n/3)=1
当(d, n/3d)=m>1时,这两个集合都是空集,
当(d, n/3d)=1时,3d | k 且(k, n/3d)=1,等价于(h, n/3d)=1且k=3dh,k在[1,n]中有φ(n/3d)个,在[1,(n-1)/2]中就有φ(n/3d)/2个,
d | k 且(k, n/3d)=1,k不是3的倍数,等价于k=dh且(h, n/d)=1,同理在[1, (n-1)/2]中有φ(n/d)/2个这样的k,
而当d<n/3时,都有φ(n/d)=φ(n/3d)*2
2023年04月17日 00点04分
