The smallest n such that n^n mod m = 0

Question

You have a natural number m.

You need to write a function f(m) which finds the smallest positive number n such that n^n≡0 mod m.

In other words n^n is divisible by m.

For example:

f(13) = 13
f(420) = 210
f(666) = 222
f(1234567890) = 411522630

And this is my code for python.

import math

def f(m: int) -> int:
    t = math.isqrt(m) + 1
    primes = [1 for i in range(0, t)]

    maxCount = 0
    factors = []
    p = 2

    result = 1

    while p < t and p < m:
        if primes[p] == 1 and m % p == 0:
            for i in range(p + p, t):
                primes[i] = 0

            c = 0
            while m % p == 0:
                m = m // p
                c += 1
            if maxCount < c:
                maxCount = c
            result *= p
            factors.append(p)
        p += 1
    factors.append(p)
    if m > 1:
        result *= m
    if maxCount <= result:
        return result
    p1 = math.ceil(maxCount / result)
    for p in primes:
        if p >= p1:
            return result * p
    return result

The problem is, the result is usually gets bigger than it has to be. If you have ever met this question before, please help me how can I solve this problem.

I have tried to find the mathematical methods, and this code is what I have reached so far. I hope this code will get me the smallest result, but it gets bigger than I expected.

Answer 1

To solve this problem, we will follow the given steps:

Start with n = 1.

Check if n ^n mod m = 0. If true, return n.

If false, increment n and repeat step 2.

Below is the Python code that implements the function:

def f(m):
    n = 1
    while True:
        if pow(n, n, m) == 0:
            return n
        n += 1

# Test the function with given examples
print(f(13))  # 13
print(f(420))  # 210
print(f(666))  # 222
print(f(1234567890))  # 411522630

This function uses the built-in pow function with three arguments: pow(a, b, m) computes a^b mod m efficiently. This allows the program to compute large powers modulo m without having to compute the large power directly.

Note: For very large values of m, this algorithm might take a considerable amount of time because it checks each possible value of n iteratively.

Answer 2

If m divides nⁿ, Then all the prime factors of m must also be factors of nⁿ.

Since exponentiation doesn't introduce any new prime factors, n itself must also have all the prime factors of m.

Let P be the product of the unique prime factors of m. Since n needs all of these factors, it will be a multiple of P.

n = P will work, i.e. P^P will be divisible by m, unless at least one of the prime factors of m has a power greater than P.

For example, if m = 3x2⁷, then P = 6, and 6⁶ is not divisible by 3x2⁷, because it only has 2⁶.

However, if you just start with i=1 and just try each n = P*i in sequence, then you will never have to count very far before you find a multiple of m, because the powers of the prime factors in m are limited by the length of m.