19. Let $p$ and $q$ be positive integers. If $\frac{p}{q}=0.123456789 \ldots$ (i.e. when $\frac{p}{q}$ is expressed as a decimal the first 9 digits after the decimal point are 1 to 9 in order), find the smallest value of $q$.
(2 marks)
設 $p 、 q$ 為正整數。若 $\frac{p}{q}=0.123456789 \ldots$ (即 $\frac{p}{q}$ 以小數表示時小數點後首 9 個位依次是 1至 9), 求 $q$ 的最小值。
(2 分)
19. 10989019
19. We have $0.123456789 \leq \frac{p}{q}0.00000001$. Since $10 q-81 p$ is an integer, it is at least 1 and so $q \geq \frac{1}{0.000000091}>10989010$.
When $10 q-81 p=1$, then $10 q-1$ is divisible by 81 and is at least 109890099 . The smallest multiple of 81 above this minimum is 109890189 . This corresponds to $q=10989019$ and $p=1356669$. This $q$ is clearly smallest when $10 q-81 p=1$, and is also smallest in general since if $10 q-81 p>1$ we would have $q \geq \frac{10 q-81 p}{0.000000091} \geq \frac{2}{0.000000091}>20000000$. It follows that the smallest possible value of $q$ is 10989019 .
Remarks.
(1) It can be checked that $\frac{1356669}{10989019}=0.1234567890000008 \ldots$.
(2) The upper bound $\frac{p}{q}<0.12345679$ is basically not used in the solution. However if one recalls that $111111111=12345679 \times 9$, then this would lead us to consider multiplication by 81 . It also helps compute $0.123456789 \times 81$ more easily.