Question

求满足φ(mn)=φ(m)+φ(n)的所有正整数m,n

Answer 1

φ(x)是欧拉函数
是少于或等于x的数中与x互质的数的个数.
当(m,n)=1时有
φ(mn)=φ(m)*φ(n)
如果(m,n)不=1
φ(mn)>=φ(m)*φ(n)
通常木有人关注φ(mn)=φ(m)+φ(n)
而且如果n>=3那么φ(n)>=2
这样如果m和n都>=3那么
φ(mn)>=3 max{φ(n),φ(m)}>φ(m)+φ(n)
所以m,n至少有个是2
φ(2n)=φ(2)+φ(n)
φ(2n)=1+φ(n)
设n可以被质数p,q,.,r整除.
若n是奇数
φ(n)=n(1-1/p)(1-1/q)...(1-1/r)
φ(2n)=2n(1-1/p)(1-1/q)...(1-1/r)(1-1/2)
不行
若n是偶数
φ(n)=n(1-1/p)(1-1/q)...(1-1/r)
φ(2n)=2n(1-1/p)(1-1/q)...(1-1/r)
φ(n)=n(1-1/p)(1-1/q)...(1-1/r)=2
n=3,4,6
所以(m,n)是
(3,2)
(4,2)
(6,2)
或者
(2,3)
(2,4)
(2,6)