Solution to puzzle 125: Divisibility by 446617991732222310

Show that, for all integers m and n, mn(m⁴²⁰ − n⁴²⁰) 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(m⁴²⁰ − n⁴²⁰) is divisible by each of these prime factors.

Let p be one of the above prime factors.  We consider two mutually exclusive cases:

1. If mn is divisible by p, then clearly mn(m⁴²⁰ − n⁴²⁰) is also divisible by p.
2. 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, m^p−1 n^p−1 1 (modulo p).
   Now note that, for each p, p − 1 divides 420. 
   Hence m⁴²⁰ n⁴²⁰ 1 (mod p), or m⁴²⁰ − n⁴²⁰ 0 (mod p).
   That is, m⁴²⁰ − n⁴²⁰ is divisible by p.

Thus, in both cases, mn(m⁴²⁰ − n⁴²⁰) is divisible by each prime factor p.

Therefore, for all integers m and n, mn(m⁴²⁰ − n⁴²⁰) is divisible by 446617991732222310.

Source: Traditional

Back to top