Question

初等数论题目

第7题 万分感谢

Answer 1

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的可能的素因子.
确定各素因子的指数范围, 然后在有限的范围内枚举指数的取值.
视情况不需要枚举所有可能的组合, 而是可由已经取定的指数进一步限制未取定的指数的范围.