For a positive integer n, which is the greatest number among the following…

Concept

A guaranteed divisor can be established by factoring out common prime powers and by using congruences to prove any remaining factor divides the expression for every allowed value.

For an expression of the form xn − yn, if x ≡ y (mod m), then xn − yn is divisible by m. The greatest offered divisor is then found by comparing all guaranteed factors represented by the choices.

Application

1. Factor the expression: 36n − 63n = 36n − 23n·33n = 33n(33n − 23n).

2. For the factor 19, observe that 33 = 27 ≡ 8 (mod 19) and 23 = 8. Raising both congruent values to the positive integer n gives 33n ≡ 23n (mod 19), so 19 divides the parenthetical factor.

3. Because n ≥ 1, the factor 33n contains at least 33 = 27. Hence 27·19 = 513 divides the expression for every positive integer n.

4. The value 3 is also a divisor, but it is smaller than 513. The values 500 and 6 are not guaranteed divisors, as the case n = 1 already gives the odd value 513.

Cross-check

1. For n = 1: 36 − 63 = 729 − 216 = 513 = 513·1.

2. For n = 2: 312 − 66 = 531441 − 46656 = 484785 = 513·945.

Therefore, the greatest offered number that always divides the expression is 513.