|
|
【温故知新】 φ(mn) = φ(m) + φ(n)
[这个贴子最后由luyuanhong在 2011/05/30 06:39pm 第 2 次编辑]
下面引用由尚九天在 2011/05/13 01:37pm 发表的内容：
求满足下式的所有正整数 m，n
φ(mn) = φ(m) + φ(n) .
符号 φ(m) 表示欧拉函数.
-----------------------------------------------------------
...
题 求满足下式的所有正整数 m，n ：
φ(mn)＝φ(m)＋φ(n) 。
符号 φ(m) 表示欧拉函数。
解 欧拉函数 φ(m) 表示小于等于 m 且与 m 互质的正整数的个数，它有性质
φ(mn)≥φ(m)φ(n) 。
设 φ(m)≥φ(n) ，则有
φ(m)φ(n)≤φ(mn)＝φ(m)＋φ(n)≤φ(m)＋φ(m)＝2φ(m) ，
即有
φ(n)≤2 。
满足这一不等式的，只有下列几种情形
φ(1)＝1 ,φ(2)＝1 ,φ(3)＝2 ,φ(4)＝2 ,φ(6)＝2 。
下面对各种情形分别讨论：
（1）n＝1 ,φ(n)＝φ(1)＝1 。
这时 φ(m)＝φ(m×1)＝φ(m)＋φ(1)＝φ(m)＋1 ，显然不可能。
（2）n＝2 ,φ(n)＝φ(2)＝1 。
设 m＝2^k×p ，p 与 2 互质，这时有
φ(m)＝φ(2^k×p)＝φ(2^k)φ(p)＝2^(k-1)φ(p) ，
φ(mn)＝φ(2^k×p×2)＝φ(2^(k+1))φ(p)＝2^kφ(p) ，
2^kφ(p)＝φ(mn)＝φ(m)＋φ(n)＝2^(k-1)φ(p)＋1 ,
即有 2^(k-1)φ(p)＝1 。此式要成立，必须有 k＝1 和 φ(p)＝1 。
又因为 p 与 2 互质，所以只能是 p＝1 ，m＝2^k×p＝2^1×1＝2 。
这样，就得到了一组解：
m＝2 ，n＝2 ，φ(2×2)＝φ(4)＝2＝1＋1＝φ(2)＋φ(2) 。
（3）n＝3 ，4 或 6 ，φ(n)＝2 。
这时 2φ(m)＝φ(m)φ(n)≤φ(mn)＝φ(m)＋φ(n)＝φ(m)＋2 ，
即有 φ(m)≤2 ，同时 φ(m)≥φ(n)＝2 ，所以只能是 φ(m)＝2 。
对 m ，n＝3 ，4 或 6 的各种情形进行搜索，得到下面两组解：
m＝3 ，n＝4 ，φ(3×4)＝φ(12)＝4＝2＋2＝φ(3)＋φ(4) ，
m＝4 ，n＝3 ，φ(4×3)＝φ(12)＝4＝2＋2＝φ(4)＋φ(3) 。 |
|
IP卡
狗仔卡
发表于 2011-5-13 13:37
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主
发表于 2011-5-15 11:54