2021 AMC 10A Problem 11
For which of the following integers is the base- number not divisible by ?
Show solution without answering
Key insight
Write both numbers using powers of b. Their difference is 2 × b × b × (b - 1), a multiple of 3 whenever b or b - 1 is.
Solution
1. In base , the digits count powers of , just as in base they count powers of . For example, in base , .
2. So in base :
3. Subtract. The parts cancel:
4. Factor out :
5. Since is prime, a product is a multiple of exactly when one of its factors is. The factor is not, so we need or to be a multiple of .
6. Check each choice:
| multiple of ? | ||
|---|---|---|
| yes () | ||
| yes () | ||
| yes () | ||
| yes () | ||
| no |
- Check directly: , and its digit sum is not a multiple of .
The answer is .
Why this works
A number written in base is really an expression in , so a difference of two such numbers can be simplified and factored like algebra. Factoring answers the question for every base at once. Since and are next to each other, the only bases that fail are those one less than a multiple of , like .
Alternative approach
Use the factored form to compute each value: gives , gives , gives , gives , and gives . Their digit sums are , and only is not a multiple of .
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Write both numbers as polynomials in :
Subtracting, the and terms cancel:
Since is prime and does not divide , this is divisible by exactly when or , that is, when or .
Check the choices: , , , all work, but does not. Indeed for the value is , whose digit sum is not a multiple of .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 8: Base Numbers
- Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
- Introduction to Algebra, Chapter 11: Special Factorizations
- Introduction to Number Theory, Chapter 9: Base Number Arithmetic
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.