Skip to main content
OlympiadHQ

Browse · MathNet

Print

Croatia_2018

Croatia 2018 number theory

Problem

Determine all positive integers such that there exist positive integers and which satisfy Here denotes the sum of digits of . (Romania 1999)
Solution
Notice that, for each positive integer , the numbers and give the same remainder when divided by . Applying this observation to , we conclude that , and give the same remainder when divided by . This implies that and are both divisible by . But then and are also divisible by . This proves that any positive integer satisfying the given condition must be divisible by .

Let us now prove the converse: let be a multiple of , i.e. let for some positive integer . Taking numbers where each of the numbers has exactly digits, we obtain a pair which satisfies .
Final answer
All positive integers divisible by 9

Techniques

Modular ArithmeticDivisibility / Factorization