Super Duper Composite!

We factorise to get: $446617991732222310 = 2 × 3 × 5 × 7 × 11 × 13 × 29 × 31 × 43 × 61 × 71 × 211 × 421$

We claim that $mn(m^{420} - n^{420})$ is divisible by each of these prime factors.

Let $p$ be one of the prime factors. So one of the two cases occur:

• If $mn$ is divisible by $p$ , then we are done.
• If $mn$ is not divisible by $p$ , then both $m$ & $n$ are not divisible by $p$ . Hence, by Fermat's Little Theorem, $m^{p-1} \equiv n^{p-1} \equiv 1 \pmod{p}$ . For each $p$ , $(p - 1)$ divides $420$ (This is the LCM of $\{p_i -1 \}$ ). Hence, $m^{420} \equiv n^{420} \equiv 1 \pmod{p}$ That is, $m^{420} - n^{420}$ is divisible by $p$ . Thus, in both cases, $mn(m^{420} - n^{420})$ is divisible by each prime factor $p$ .

Therefore, for all integers $m$ & $n$ , $mn(m^{420} - n^{420})$ is divisible by $446617991732222310 \Rightarrow k=\boxed{420}$ .

Looking at this problem, (especially at the long number) one may feel overwhelmed and feel tempted to just skip this question. However, one idea that can be employed in number theory questions such as the above is the Fermat Little Theorem (FLT) : as follows --- especially when the question involves prime division and powers.

Let $p$ be a prime and $a$ be a positive integer relatively prime to $p$ . Then $a^{p-1} \equiv 1 (\bmod p)$ .

Case 1: Let $mn$ divide the prime $p_1$ of $446617991732222310$ .

Case 2: Let $\gcd (m,p) =1$ and $\gcd (n, p) =1$ , meaning that $m$ and $n$ are relatively prime to $p$ . Thus, we can apply FLT here. In our question, observe that the largest prime of $446617991732222310$ is $421$ . Hence, for every ordered pair of integers $(m,n)$ , $m^{421 -1} \equiv n^{421-1} \equiv 1 (\bmod 421)$ Hence, $m^{420} - n^{420} \equiv 0 (\bmod 421)$ and this applies for all prime of $446617991732222310$ .

Thus, the smallest $k = \boxed{420}$

I have to accept one thing. I did not factorize the number by myself. I checked up to 2,3,5,7,11,13 .. and when I checked with 17, not getting divisible. I gave up, and checked wolfram alpha. (I feel this should have been provided with the question)

Anyways,

446617991732222310 = 2 * 3 * 5 * 7 * 11 * 13 * 29 * 31 * 43 * 61 * 71 * 211 * 421

So, we have 13 prime factors

Now, a prime number, 'p' would leave a remainder of 1 when it divides $m^{p-1}$ , if 'm' and 'p' are relatively prime, by Fermat's little theorem. Same remainder would be left when 'p' divides $n^{p-1}$ , if 'p' and 'n' are relatively prime. So, if 'p' is relatively prime to both 'm' and 'n', then $m^{p-1}$ - $n^{p-1}$ should be div by 'p'.

Now, we have two cases:

Case 1: one of 'm' or 'n' is div by 'p', 'p' being one of the 13 prime factors of the number

Case 2: $m^{p-1}$ - $n^{p-1}$ is div by 'p'

Taking the worst case scenario (Case 2),

'k' should be a multiple of (each of the prime factors) - 1

that is, k = LCM (1,2,4,6,10,12,28,30,42,60,70,210,420) = $\boxed{420}$

The prime factorization of the huge divisor is $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 29 \times 31 \times 43 \times 61 \times 71 \times 211 \times 421$ Firstly, we prove that when k=420, it fits the conditions. Consider all primes $p$ less than or equal to 421. We just need to prove that the dividend $mn(m^{420}-n^{420})$ is a multiple of all such primes.

If $m$ or $n$ is divisible by $p$ we are done. Otherwise, neither $m$ nor $n$ is divisible by $p$ and we just need to prove that $m^{420}-n^{420}$ is divisible by $p$ .

Since $m$ and $p$ (and similarly, $n$ and $p$ are relatively prime, by Fermat's Little Theorem (which states that $a^{p-1}$ is congruent to 1 modulo $p$ where $p$ is prime and $a$ is a positive integer relatively prime to $p$ ), both $m^{420}$ and $n^{420}$ are congruent to 1 modulo p and their difference will thus be a multiple of p.

Now we prove that when k is less than 420 it does not satisfy the conditions.

Consider the case when n=1. Note that $mn(m^{k}-n^{k})=m(m^{k}-1)$ after substituting m and n. As it is not necessary for m to be a multiple of 421, let's assume that m is not a multiple of 421. However, it is not necessary for $m^{k}-1$ to be a multiple of 421. Thus the dividend will not always be a multiple of 421, and will not be a multiple of that huge number. Thus 420 is the minimal value of k.