满足 n^n mod m = 0 的最小 n

Question

你有一个自然数m。

\n

您需要编写一个函数 f(m) 来查找满足 n^n\xe2\x89\xa10 mod m 的最小正数 n。

\n

换句话说，n^n 可以被 m 整除。

\n

例如：

\n

f(13) = 13\nf(420) = 210\nf(666) = 222\nf(1234567890) = 411522630\n

\n

这是我的 python 代码。

\n

import math\n\ndef f(m: int) -> int:\n    t = math.isqrt(m) + 1\n    primes = [1 for i in range(0, t)]\n\n    maxCount = 0\n    factors = []\n    p = 2\n\n    result = 1\n\n    while p < t and p < m:\n        if primes[p] == 1 and m % p == 0:\n            for i in range(p + p, t):\n                primes[i] = 0\n\n            c = 0\n            while m % p == 0:\n                m = m // p\n                c += 1\n            if maxCount < c:\n                maxCount = c\n            result *= p\n            factors.append(p)\n        p += 1\n    factors.append(p)\n    if m > 1:\n        result *= m\n    if maxCount <= result:\n        return result\n    p1 = math.ceil(maxCount / result)\n    for p in primes:\n        if p >= p1:\n            return result * p\n    return result\n

\n

问题是，结果通常会比它必须的要大。\n如果您以前遇到过这个问题，请帮助我如何解决这个问题。

\n

我试图找到数学方法，而这段代码是我迄今为止所达到的。\n我希望这段代码能给我带来最小的结果，但它比我预期的要大。

\n

Answer 1

如果 m 整除 n ⁿ，则 m 的所有素因数也必定是 n ⁿ的因数。

由于求幂不会引入任何新的质因数，因此 n 本身也必须具有 m 的所有质因数。

令 P 为 m 的唯一质因数的乘积。由于 n 需要所有这些因素，因此它将是 P 的倍数。

n = P 有效，即 P ^P可被 m 整除，除非m 的质因数中至少有一个具有大于 P 的幂。

例如，如果 m = 3x2 ⁷，则 P = 6，并且 6 ⁶不能被 3x2 ⁷整除，因为它只有 2 ⁶。

然而，如果你只是从 i=1 开始，然后依次尝试每个 n = P*i，那么在找到 m 的倍数之前，你永远不必数得很远，因为 m 中素数因子的幂是有限的米的长度。