Maths Olympiad Prep

Library / /26 of 33

, 2011

Number theory Difficulty 8.4 Shortlist Prove it Baltic Way

Determine all positive integers dd such that whenever dd divides an integer nn, dd will also divide any integer mm having the same digits as nn.

Solution

Answer: d=1d = 1, d=3d = 3 or d=9d = 9. It is known that 11, 33 and 99 have the given property. Assume that dd is a kk digit number such that whenever dd divides an integer nn, dd will also divide any integer mm having the same digits as nn. Then there exists a k+2k+2 digit number 10a1a2ak10a_1a_2\dots a_k which is divisible by dd. Hence a1a2ak10a_1a_2\dots a_k10 and a1a2ak01a_1a_2\dots a_k01 are also divisible by dd. Since a1a2ak10a1a2ak01=9a_1a_2\dots a_k10 - a_1a_2\dots a_k01 = 9, dd divides 99, and hence d=1d=1, d=3d=3 or d=9d=9 as stated.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.