Skip to main content
OlympiadHQ

Browse · MathNet

Print

XVI OBM

Brazil number theory

Problem

Call a super-integer an infinite sequence of decimal digits: . Given two super-integers and , their product is formed by taking to be the last digits of the product and . Can we find two non-zero super-integers with zero product? A zero super-integer has all its digits zero.
Solution
The answer is yes. In fact, there exist two sequences and such that, for every , divides and divides ; then divides and .

Consider first . We proceed by induction. For choose . Suppose is a multiple of and let be divided by . Then and we may choose or according to the parity of , so is even and, consequently, is a multiple of . This completes the induction.

The induction for is not that different. Indeed, choose and suppose . Then and it's always possible to choose such that , since admits inverse modulo .
Final answer
Yes

Techniques

Divisibility / FactorizationInverses mod nInduction / smoothing