Skip to main content.

Solution to puzzle 125: Divisibility by 446617991732222310

Skip restatement of puzzle.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:

  1. If mn is divisible by p, then clearly mn(m420 − n420) 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, mp−1 congruent to np−1 congruent to 1 (modulo p).
    Now note that, for each p, p − 1 divides 420. 
    Hence m420 congruent to n420 congruent to 1 (mod p), or m420 − n420 congruent to 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.

Source: Traditional

Back to top