Solution to puzzle 125: Divisibility by 446617991732222310
Show that, for all integers m and n, mn(m420 − n420) is divisible by 446617991732222310.
Firstly, we obtain the prime factorization of 446617991732222310; for example, at Dario Alpern's Factorization Engine. We get:
446617991732222310 = 2 × 3 × 5 × 7 × 11 × 13 × 29 × 31 × 43 × 61 × 71 × 211 × 421.
We must show that mn(m420 − n420) is divisible by each of these prime factors.
Let p be one of the above prime factors. We consider two mutually exclusive cases:
- If mn is divisible by p, then clearly mn(m420 − n420) is also divisible by p.
- If mn is not divisible by p, then both m and n are not divisible by p.
Hence, since p is prime, m and p and n and p are relatively prime, and, by Fermat's Little Theorem, mp−1 np−1 1 (modulo p).
Now note that, for each p, p − 1 divides 420.
Hence m420 n420 1 (mod p), or m420 − n420 0 (mod p).
That is, m420 − n420 is divisible by p.
Thus, in both cases, mn(m420 − n420) is divisible by each prime factor p.
Therefore, for all integers m and n, mn(m420 − n420) is divisible by 446617991732222310.
Back to top