Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

Suppose that can be written in base as and in base as . In base , what is the remainder when is divided by ?
Solution
The prime factorization of . By the Chinese Remainder Theorem, it suffices to find the residues of modulo , , and . Since the units digit of in base is equal to , it follows that is divisible by . Also, we note that is congruent modulo to the sum of its base digits. Indeed, if can be represented as , then It follows that and that By the Chinese Remainder Theorem and inspection, we determine that , so that (by the Chinese Remainder Theorem again) .
Final answer
66