Maths Olympiad Prep

Library / /68 of 106

Number theory Difficulty 8.5 Shortlist Prove it IMO

Call a rational number short if it has finitely many digits in its decimal expansion. For a positive integer mm, we say that a positive integer tt is mm-tastic if there exists a number c{1,2,3,,2017}c \in \{1,2,3, \ldots, 2017\} such that 10t1cm\frac{10^{t}-1}{c \cdot m} is short, and such that 10k1cm\frac{10^{k}-1}{c \cdot m} is not short for any 1k<t1 \leqslant k<t. Let S(m)S(m) be the set of mm-tastic numbers. Consider S(m)S(m) for m=1,2,m=1,2, \ldots. What is the maximum number of elements in S(m)S(m) ?

Solution

If m=2a5bsm=2^{a} \cdot 5^{b} \cdot s, with gcd(s,10)=1\operatorname{gcd}(s, 10)=1, then 10t1m\frac{10^{t}-1}{m} is short if and only if ss divides 10t110^{t}-1. So we may (and will) suppose without loss of generality that gcd(m,10)=1\operatorname{gcd}(m, 10)=1. Define
C={1c2017:gcd(c,10)=1}. C=\{1 \leqslant c \leqslant 2017: \operatorname{gcd}(c, 10)=1\} .
The mm-tastic numbers are then precisely the smallest exponents t>0t>0 such that 10t1(modcm)10^{t} \equiv 1 \pmod{c m} for some integer cCc \in C, that is, the set of orders of 1010 modulo cmc m. In other words,
S(m)={ordcm(10):cC}. S(m)=\left\{\operatorname{ord}_{c m}(10): c \in C\right\} .
Since there are 4201+3=8074 \cdot 201+3=807 numbers cc with 1c20171 \leqslant c \leqslant 2017 and gcd(c,10)=1\operatorname{gcd}(c, 10)=1, namely those such that c1,3,7,9(mod10)c \equiv 1,3,7,9 \pmod{10},
S(m)C=807. |S(m)| \leqslant |C|=807 .
Now we find mm such that S(m)=807|S(m)|=807. Let
P={1<p2017:p is prime, p2,5} P=\{1<p \leqslant 2017: p \text{ is prime, } p \neq 2,5\}
and choose a positive integer α\alpha such that every pPp \in P divides 10α110^{\alpha}-1 (e.g. α=φ(T)\alpha=\varphi(T), TT being the product of all primes in PP), and let m=10α1m=10^{\alpha}-1.

Claim. For every cCc \in C, we have
ordcm(10)=cα \operatorname{ord}_{c m}(10)=c \alpha
As an immediate consequence, this implies S(m)=C=807|S(m)|=|C|=807, finishing the problem.

Proof. Obviously ordm(10)=α\operatorname{ord}_{m}(10)=\alpha. Let t=ordcm(10)t=\operatorname{ord}_{c m}(10). Then
cm10t1m10t1αt. c m \mid 10^{t}-1 \quad \Longrightarrow \quad m \mid 10^{t}-1 \quad \Longrightarrow \quad \alpha \mid t .
Hence t=kαt=k \alpha for some kZ>0k \in \mathbb{Z}_{>0}. We will show that k=ck=c.

Denote by νp(n)\nu_{p}(n) the number of prime factors pp in nn, that is, the maximum exponent β\beta for which pβnp^{\beta} \mid n. For every 1\ell \geqslant 1 and pPp \in P, the Lifting the Exponent Lemma provides
νp(10α1)=νp((10α)1)=νp(10α1)+νp()=νp(m)+νp() \nu_{p}\left(10^{\ell \alpha}-1\right)=\nu_{p}\left(\left(10^{\alpha}\right)^{\ell}-1\right)=\nu_{p}\left(10^{\alpha}-1\right)+\nu_{p}(\ell)=\nu_{p}(m)+\nu_{p}(\ell)
So
cm10kα1pP;νp(cm)νp(10kα1)pP;νp(m)+νp(c)νp(m)+νp(k)pP;νp(c)νp(k)ck. \begin{aligned} c m \mid 10^{k \alpha}-1 & \Longleftrightarrow \forall p \in P ; \quad \nu_{p}(c m) \leqslant \nu_{p}\left(10^{k \alpha}-1\right) \\ & \Longleftrightarrow \forall p \in P ; \quad \nu_{p}(m)+\nu_{p}(c) \leqslant \nu_{p}(m)+\nu_{p}(k) \\ & \Longleftrightarrow \forall p \in P ; \quad \nu_{p}(c) \leqslant \nu_{p}(k) \\ & \Longleftrightarrow c \mid k . \end{aligned}
The first such kk is k=ck=c, so ordcm(10)=cα\operatorname{ord}_{c m}(10)=c \alpha.

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 and solution reproduced as published; topic and difficulty added by this site.