欧拉函数φ(n)=24,求所有的n?以及φ(n)等于一个任意正整数的一般方法
24的约数有1, 2, 3, 4, 6, 8, 12, 24, 其中后继为素数的有1, 2, 4, 6, 12。因此n的可能质因数有2, 3, 5, 7, 13。可设n = 2^a·3^b·5^c·7^d·13^e。 有24 = φ(n) = φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d)·φ(13^e)。分别由φ(2^a), φ(3^b), φ(5^c), φ(7^d), φ(13^e)是24的约数, 可知a ≤ 4, b ≤ 2, c, d, e ≤ 1。 可能性情况约束为有限种。1。 若e = 1, 有φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d) = φ(n)/...全部
24的约数有1, 2, 3, 4, 6, 8, 12, 24, 其中后继为素数的有1, 2, 4, 6, 12。因此n的可能质因数有2, 3, 5, 7, 13。可设n = 2^a·3^b·5^c·7^d·13^e。
有24 = φ(n) = φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d)·φ(13^e)。分别由φ(2^a), φ(3^b), φ(5^c), φ(7^d), φ(13^e)是24的约数, 可知a ≤ 4, b ≤ 2, c, d, e ≤ 1。
可能性情况约束为有限种。1。 若e = 1, 有φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d) = φ(n)/φ(13) = 2。可知a ≤ 2, b ≤ 1, c = d = 0。(1) 若b = 1, φ(2^a) = 1, 可得a = 0, 1, 分别得解n = 39, 78。
(2) 若b = 0, φ(2^a) = 2, 可得a = 2, 得解n = 52。2。 若e = 0, d = 1, 有φ(2^a)·φ(3^b)·φ(5^c) = φ(n)/φ(7) = 4。
可知a ≤ 3, b ≤ 1, c ≤ 1。(1) 若c = 1, φ(2^a)·φ(3^b) = 1, 得b = 0, a = 0, 1, 分别得解n = 35, 70。(2) 若c = 0, b = 1, φ(2^a) = 2, 得a = 2, 得解n = 84。
(3) 若b = c = 0, φ(2^a) = 4, 得a = 3, 得解n = 56。3。 若d = e = 0, c = 1, 有φ(2^a)·φ(3^b) = φ(n)/φ(5) = 6。
可知b = 2, 否则左端不能被3整除。于是φ(2^a) = 1, 得a = 0, 1, 得解n = 45, 90。4。 若c = d = e = 0, 有φ(2^a)·φ(3^b) = 24。
同样知b = 2, 于是φ(2^a) = 4, 得a = 3, 得解n = 72。综上, 全部解为n = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90, 共10个。
以上过程可以推广为一般方法(虽然效率难以保证)。枚举φ(n)的约数, 确定n的可能的素因子。确定各素因子的指数范围, 然后在有限的范围内枚举指数的取值。视情况不需要枚举所有可能的组合, 而是可由已经取定的指数进一步限制未取定的指数的范围。收起
