Find all positive integers $a$ so that for any $\left \lfloor \frac{a+1}{2} \right \rfloor$-digit number that is composed of only digits $0$ and $2$ (where $0$ cannot be the first digit) is not a multiple of $a$.
Problem
Source: 2020 China North Mathematical Olympiad Advanced Level P5
Tags: number theory, Digits, multiple
13.03.2021 17:48
Bump this.
07.08.2021 11:14
Ans: $3,9$ are all the positive integers satisfying the problem. Proof: Let S be the set of all positive integers satisfying the problem. Claim 1: if $a = {2^p}{.5^q}.s \in S$ then $s \in S$ \[If\,\,s = 1\,\,and\,\,\,\,\left( {p;q} \right) \ne \left( {1;0} \right)\,\,\,then\,\,\,\,\left[ {\frac{{a + 1}}{2}} \right] > \max \left\{ {p,q} \right\}\,\,,\,\,so\,{\kern 1pt} \overline {2..20..0} \,\,\left( {\max \left( {p,q} \right)\,\,numbers\,\,\,0} \right) \vdots a,\,\,else\,\,if\,\,\left( {p;q} \right) = \left( {1;0} \right)\,\,then\,\,\,2 \vdots a = 2\,\,(contradiction)\]. Now, assume that $s>1 \notin S$, or there exists positive integer $u$ (have $\left[ {\frac{{s + 1}}{2}} \right]\,$) such that $u \vdots s$. \[As\,\,\left[ {\frac{{a + 1}}{2}} \right] - \left[ {\frac{{s + 1}}{2}} \right] \geqslant \max \left\{ {p,q} \right\}\,,\,\,so\,\,u{.10^{\left[ {\frac{{a + 1}}{2}} \right] - \left[ {\frac{{s + 1}}{2}} \right]}} \vdots {10^{\max \left\{ {p,q} \right\}}}\,\,\overline {u0..0} \, \vdots a\,\left( {\left[ {\frac{{a + 1}}{2}} \right] - \left[ {\frac{{s + 1}}{2}} \right]\,\,digit\,\,number\,\,0} \right)\]A contradiction. Clam 2: $s$ has at most 2 prime divisors. Assume $s$ has at least $3$ prime divisors. Case 1: $3|s$ then $\frac{{{{10}^{3.\frac{{\varphi \left( s \right)}}{4}}} - 1}}{9} \vdots s$, because \[if\,\,p = 3\,\,we\,\,have\,\,\,{v_3}\left( {\frac{{{{10}^{3.\frac{{\varphi \left( s \right)}}{4}}} - 1}}{9}} \right) = {v_3}\left( {10 - 1} \right) + {v_3}\left( {\frac{3}{4}\varphi \left( s \right)} \right) - 2 \geqslant {v_3}\left( s \right)\,else\,\,we\,\,have\,\,{10^{\varphi \left( s \right).\frac{3}{4}}} - 1 \vdots {10^{\varphi \left( {{p^{{v_p}\left( s \right)}}} \right)}} - 1 \vdots {p^{{v_p}\left( s \right)}}\]Case 2: $\left( {s,3} \right) = 1\,\,then\,\,\,\frac{{{{10}^{\frac{{\varphi \left( s \right)}}{4}}} - 1}}{9} \vdots s$ because \[\forall p \ne 3\,,\,\,p|s \Rightarrow \,\,{10^{\frac{{\varphi \left( s \right)}}{4}}} - 1 \vdots {10^{\varphi \left( {{p^{{v_p}\left( s \right)}}} \right)}} - 1 \vdots {p^{{v_p}\left( s \right)}}\,\,so,\,\,\,\overline {222.220..0} \vdots s\,\,with\,\,\,\frac{{\varphi \left( s \right)}}{4} - 1 < \left[ {\frac{{s + 1}}{2}} \right]\,\,digit\,\,\,numbers\,\,2\]Claim 3: $s = {3^r}.{p^s}\,\,(\,\,p > 5,\,\,p \in \wp )$. Assume that \[s = {p^s}.{q^t}\,\,\left( {p,q > 3,\,\,p,q \in \wp ,\,\,s,t \in \mathbb{N}} \right)\]then \[\frac{{{{10}^{\frac{{\varphi \left( s \right)}}{2}}} - 1}}{9} \vdots s\,\,becase\,\,\forall \,p|s \Rightarrow \,\,{10^{\frac{{\varphi \left( s \right)}}{2}}} - 1 \vdots {10^{\varphi \left( {{p^{{v_p}\left( s \right)}}} \right)}} - 1 \vdots {p^{{v_p}\left( s \right)}}\,\,so,\,\,\,\overline {222.220..0} \vdots s\,\]Claim 4: $p^s \notin S$ ($p>3$ is a prime number) . Because \[2.\,\,\frac{{{{10}^{\frac{{p - 1}}{2}}} - 1}}{9} \vdots p\,\,or\,\,2.\left[ {{{10}^{\frac{{p + 1}}{2}}} + 1} \right] \vdots p\]Claim 5: $s = {3^t}.{p^s}$ ($\,s,t \geqslant 1$) $\notin S$ Case 1: ${10^{\frac{{p - 1}}{2}}} + 1 \vdots p\,\, \Rightarrow {10^{{p^{s - 1}}.\frac{{p - 1}}{2}}} + 1 \vdots {p^s}\,\,\,\,\left( {LTE} \right)$ \[if\,\,t \geqslant 3 \Rightarrow u = \left( {{{10}^{{p^{s - 1}}.\frac{{p - 1}}{2}.k}} + 1} \right).x \vdots s = {3^t}.{p^s}\,\,with\,\,x = 2.\frac{{{{10}^{{3^t}}} - 1}}{9}\]($k$ is the minimun odd number such that ${p^{s - 1}}.\frac{{p - 1}}{2}.k > {3^t}$) but $u$ has ${p^{s - 1}}.\frac{{p - 1}}{2}.k \leqslant {3^t} + 2.{p^{s - 1}}.\frac{{p - 1}}{2} \leqslant \frac{{{3^t}.{p^s} + 1}}{2}$ digit numbers. \[if\,t = 1,\,\,take\,\,x = \,{\kern 1pt} \overline {222} \,\,because\,\,\,{p^{s - 1}}.\frac{{p - 1}}{2}.1 > {3^t}\,\,and\,\,3 + {p^{s - 1}}.\frac{{p - 1}}{2} < \frac{{3.{p^s} + 1}}{2}\,\]\[if\,\,t = 2\,,\,\,take\,\,\,{\kern 1pt} u = \left( {{{10}^{{p^{s - 1}}.\frac{{p - 1}}{2}.3}} + 1} \right).x\,\,with\,\,x = {\kern 1pt} \overline {22..22\,} \,\,\left( {9\,\,digit\,\,numbers\,\,} \right)\,\,because\,\,9 + 3.{p^{s - 1}}.\frac{{p - 1}}{2} < \frac{{9.{p^s} + 1}}{2}\]Case 2: ${10^{\frac{{p - 1}}{2}}} - 1 \vdots p \Rightarrow {10^{{p^{s - 1}}.\frac{{p - 1}}{2}}} - 1 \vdots {p^s}$ \[LTE \Rightarrow {10^{\frac{{\varphi \left( s \right)}}{4}}} - 1 \vdots s \Rightarrow \frac{{{{10}^{3.\frac{{\varphi \left( s \right)}}{4}}} - 1}}{9} \vdots s\]So, \[\overline {22..2200..00} \vdots s\,\,with\,\,\,\,3.\frac{{\varphi \left( s \right)}}{4} - 1 < \frac{{s + 1}}{2}\,\,digit\,\,numbers\]Claim 6: $s=3^t \in S$ then $t<3$. By induction on $t>2$ we prove that there exists a number $u_t$ has at most $\frac{{{3^3} - 1}}{2}{.3^{t - 3}}$ digit numbers such that $u_t \vdots t$ (*) \[\,t = 3,\,\,take\,\,{u_3} = \,{\kern 1pt} \overline {1111111101} \vdots {3^3}\]Assume that (*) holds for any positive integer $i \leqslant t$ then we take \[{u_{t + 1}} = {\kern 1pt} \overline {{u_t}{u_t}{u_t}} \vdots 3{u_t} \vdots {3^{t + 1}}\,and\,\,{u_t}\,\,has\,\,at\,\,most\,\,\,\frac{{{3^3} - 1}}{2}{.3^{t + 1 - 3}}\,\,digit\,\,numbers\]Now, check that $3,9$ satisfying the problem, so $a = {2^p}{.5^q}.3\,\,\,or\,\,{2^p}{.5^q}.9$ but if ($p+q>0$) work same in the claim 1 we have a contradiction.