Which of the following numbers completely divide (49)15 − 1? i. 50 ii. 48 iii.…

Concept

For divisibility by a number m, an expression is divisible by m exactly when its remainder modulo m is 0.

Powers can be reduced modulo m before exponentiation. In particular, if a ≡ 1 (mod m), then an − 1 ≡ 0 (mod m) for every positive integer n.

Application

1. Modulo 50: 49 ≡ −1. Since 15 is odd, (49)15 − 1 ≡ (−1)15 − 1 = −2, not 0. Hence 50 does not divide the expression.

2. Modulo 48: 49 ≡ 1. Therefore (49)15 − 1 ≡ 115 − 1 = 0. Hence 48 divides the expression.

3. Modulo 29: 49 ≡ 20. Repeated squaring gives 202 ≡ 23, 204 ≡ 7, and 208 ≡ 20. Thus 2015 ≡ 20 × 7 × 23 × 20 ≡ 20; after subtracting 1, the remainder is 19, not 0. Hence 29 does not divide the expression.

4. Modulo 8: 49 ≡ 1. Therefore (49)15 − 1 ≡ 0. Hence 8 divides the expression.

Cross-check

The factorization an − 1 = (a − 1)(an−1 + an−2 + … + 1) shows directly that 49 − 1 = 48 divides the expression. Since 8 also divides 48, divisibility by 8 follows independently.

Therefore the numbers are ii and iv, namely 48 and 8.