Prove that n^7 - n is divisible by 42 for every integer n, and identify the largest integer that divides n^7 - n for all n.

Prove that n^7 - n is divisible by 42 for every integer n, and identify the largest integer that divides n^7 - n for all n.

Approach: Factor 42 into its primes and check each one separately with Fermat's little theorem, then test whether any other prime or a higher power of an existing one can divide the expression for every n.

42. Factor 42 = 2 * 3 * 7 and work in modular arithmetic one prime at a time. Fermat's little theorem gives n^p = n mod p for every prime p, so n^7 = n mod 7 directly, and n^2 = n mod 2 gives n^7 = n mod 2 by repeated multiplication. For 3, Fermat gives n^3 = n mod 3, so n^7 = (n^3)^2 * n = n^2 * n = n^3 = n mod 3. The three primes are distinct, so their product 42 divides n^7 - n for every integer n. No larger constant works: at n = 2 the value is 128 - 2 = 126 = 2 * 3^2 * 7, and at n = 3 it is 2187 - 3 = 2184 = 2^3 * 3 * 7 * 13. The greatest common divisor of 126 and 2184 is 42, so nothing beyond 42 divides every value. In general the largest such divisor of n^k - n is the product of the primes p with p - 1 dividing k - 1, which for k = 7 gives 2, 3 and 7.

Follow-up: What is the largest integer dividing n^{13} - n for every n, and how many primes does that product contain?

Key concepts: fermat little theorem, prime factorisation, divisibility, modular arithmetic.