AMC 10 · 2017 · #19
Grade 6 number-theoryPick an answer.
Dividing a 79-digit number by 45 head-on is hopeless. But 45 = 9 x 5, and 9 and 5 have no common factor, so the remainder mod 45 is locked in once we know the remainder mod 9 and the remainder mod 5. Each of those is easy: mod 5 depends only on the last digit, and mod 9 depends only on the digit sum. Find the two small remainders, then test the few possibilities that fit both.
Split 45 into 9 and 5
Split 45 into two coprime factors.
Breaking 45 into the coprime pieces 9 and 5 turns one impossible division into two easy ones.
6.NS.B.4Identify SubproblemsRemainder when divided by 5
For the 5 side only the last digit matters.
Tens, hundreds, and beyond are all multiples of 5, so only the last digit can leave a remainder.
4.NBT.B.6Look For A PatternRemainder when divided by 9
For the 9 side the digit sum divides exactly.
Every power of 10 is one more than a multiple of 9, so a number and its digit sum always land on the same remainder.
A number and its digit sum always land on the same remainder when divided by nine.
▸ Why?
Every place value is one more than a multiple of nine, so only the digit sum survives the division.
▸ Why?
Splitting the divisor into pieces that share no factor lets each piece be tested on its own.
Combine the two clues
Combining the two clues gives 9.
Only one multiple of 9 under 45 also lands 4 past a multiple of 5, so it must be the answer.
4.OA.B.4Eliminate PossibilitiesTo divide a giant number by 45, split 45 into 9 and 5: the last digit handles the 5 and the digit sum handles the 9, then find the one remainder that fits both.
- Split 45 into 9 and 5
- Remainder when divided by 5
- Remainder when divided by 9
- Combine the two clues