International Mathematical Olympiad

If $m=2^a\cdot 5^b\cdot s$, with $\gcd (s,10)=1$, then $\frac{10^t-1}{m}$ is short if and only if $s$ divides $10^t-1$. So we may (and will) suppose without loss of generality that $\gcd (m,10)=1$. Define $$C=\{1⩽c⩽2017:\gcd (c,10)=1\}.$$ The $m$-tastic numbers are then precisely the smallest exponents $t>0$ such that $10^t\equiv 1(\mathrm{mod}cm)$ for some integer $c\in C$, that is, the set of orders of $10$ modulo $cm$. In other words, $$S(m)=\left\{{\mathrm{ord}}_{cm}(10):c\in C\right\}.$$ Since there are $4\cdot 201+3=807$ numbers $c$ with $1⩽c⩽2017$ and $\gcd (c,10)=1$, namely those such that $c\equiv 1,3,7,9(\mathrm{mod}10)$, $$|S(m)|⩽|C|=807.$$ Now we find $m$ such that $|S(m)|=807$. Let $$P=\{1<p⩽2017:p\text{ is prime, }p\ne 2,5\}$$ and choose a positive integer $\alpha$ such that every $p\in P$ divides $10^{\alpha }-1$ (e.g. $\alpha =\phi (T)$, $T$ being the product of all primes in $P$), and let $m=10^{\alpha }-1$.

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

Proof. Obviously ${\mathrm{ord}}_m(10)=\alpha$. Let $t={\mathrm{ord}}_{cm}(10)$. Then $$cm\mid 10^t-1⟹m\mid 10^t-1⟹\alpha \mid t.$$ Hence $t=k\alpha$ for some $k\in {\mathbb{Z}}_{>0}$. We will show that $k=c$.

Denote by ${\nu }_p(n)$ the number of prime factors $p$ in $n$, that is, the maximum exponent $\beta$ for which $p^{\beta }\mid n$. For every $\ell ⩾1$ and $p\in P$, the Lifting the Exponent Lemma provides $${\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 $$\begin{array}{rl}cm\mid 10^{k\alpha }-1& ⟺\forall p\in P;{\nu }_p(cm)⩽{\nu }_p\left(10^{k\alpha }-1\right)\\ & ⟺\forall p\in P;{\nu }_p(m)+{\nu }_p(c)⩽{\nu }_p(m)+{\nu }_p(k)\\ & ⟺\forall p\in P;{\nu }_p(c)⩽{\nu }_p(k)\\ & ⟺c\mid k.\end{array}$$ The first such $k$ is $k=c$, so ${\mathrm{ord}}_{cm}(10)=c\alpha$.