Repeating Decimal in Different Bases

Lemma: The rational number $\frac{p}{q}$ (with $\gcd(p,q) = 1$ ) in base $n$ terminates if and only if $q \mid n^k$ for some $k$ .

Proof: If $\frac{ p}{q}$ terminates in $k$ digits after the decimal point, then $n^k \times \frac{p}{q}$ is an integer, implying that $q \mid n^k$ .
Conversely, if $\frac{ p}{q}$ does not terminate in $k$ digits after the decimal point for any $k$ , then this tells us that $n^k \times \frac{p}{q}$ is never an integer, and thus $q \not \mid n^k$ for any $k$ . $_ \square$

---

Applying the above lemma to the problem, we get that $67500 \mid n^k$ for some large enough $k$ . Since the set of factors of 67500 is $\{2, 3, 5 \}$ , this tells us that $30 \mid n$ is a necessary and sufficient condition. Thus, there are $\lfloor \frac{67500 } { 30 } \rfloor = 2250$ solutions.

Let's prove the theorem that

Theorem : For $p, q \in \mathbb N, q\neq1$ and $gcd(p,q)=1$ ,

Base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits $\iff D_q \subseteq D_b$ , where for any positive integer $c$ , $D_c$ is the set of all distinct prime factors of $c$ .

For the sake of clarification, when $c=40=2^3 \times 5$ , $D_{40} = \{ 2,5\}$ .

To prove the theorem, we'll use a number of lemmas.

---

• Lemma - $1$ : For any positive integer $q$ and $b$ , with $q \neq 1$ and $b\geq2$ , $q \mid b^m$ for some $m \iff D_q \subseteq D_b$ .

Proof : If $q \mid b^m$ for some $m$ , every prime factor of $q \in b$ . So, $D_q \subseteq D_b$ .

Now assume, $D_q \subseteq D_b$ . Let $m$ be the minimum positive integer such that for each prime $w \in D_q$ , the highest exponent $e$ of $w$ , with $w^e \mid q$ , doesn't exceed $m$ . Then $q \mid b^m$ .

That proves Lemma - $1$ .

---

• Lemma - $2$ : For any positive integer $p, b$ and $m$ , with $b \geq 2$ , base- $b$ expansion of $(p\times b^{-m})= \dfrac{p}{b^m}$ terminates after a finite number of digits.

Proof : Let the base- $b$ expansion of $p$ be $\overline{b_nb_{n-1}\cdots{ } \cdots{ } \cdots{ }b_1b_0}=b_n\times b^n+b_{n-1}\times b^{n-1}+ \cdots{ } \cdots{ } \cdots{ }+b_1\times b^1+b_0 \times b^0$ , where $n\geq0$ is a positive integer and for each integer $i$ (with $0\leq i \leq n$ ), $0\leq b_i<b$ .

Then, $(p\times b^{-m})= \dfrac{p}{b^m}= b_n\times b^{n-m}+b_{n-1}\times b^{n-1-m}+ \cdots{ } \cdots{ } \cdots{ }+b_1\times b^{1-m}+b_0 \times b^{-m}$ . As every power of $b$ in the latter expression is unique in the expression, and for each integer $i$ (with $0\leq i \leq n$ ), $0\leq b_i<b$ , and for some $j$ (with $0\leq j\leq n$ ) and every $k$ (with $0\leq k <j$ ), $b_j\neq0$ and $b_k=0$ , base- $b$ expansion of $(p\times b^{-m})= \dfrac{p}{b^m}$ terminates after a finite number of digits; with $(m-j)$ digits after the unit digit (exclusive).

This establishes Lemma - $2$ .

---

• Lemma -3: For any positive integer $r\neq0$ (with $gcd(q,r)=1=gcd(p,q)$ and $q\neq1$ ), base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits $\iff$ base- $b$ expansion of $\dfrac{pr}{q}=\dfrac{p}{q} \times r$ terminates after a finite number of digits.

Proof : Assume that base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits. Then there is $m$ digits after the unit digit (exclusive), for some positive integer $m$ . Then, $(\dfrac{p}{q}\times b^m)$ is an integer. But $\dfrac{p}{q} = (\dfrac{p}{q}\times b^m) \times b^{-m}$ , which implies $\dfrac{pr}{q} = (\dfrac{p}{q}\times r \times b^m) \times b^{-m}$ . But as $(\dfrac{p}{q}\times r \times b^m)$ is an integer, the base- $b$ expansion of the right hand side of the last equation, by Lemma - $2$ , terminates after a finite number of digits. So does $\dfrac{pr}{q}$ .

Now suppose that base- $b$ expansion of $\dfrac{pr}{q}=\dfrac{p}{q} \times r$ terminates after a finite number of digits. That means, for some positive integer $m$ , $(\dfrac{pr}{q}\times b^m)=(\dfrac{p}{q} \times b^m)\times r$ is an integer, which implies $(\dfrac{p}{q} \times b^m)$ is an integer, as $q$ and $r$ are coprime and $q\neq1$ . And as $(\dfrac{p}{q} \times b^m)$ is an integer, base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits.

This completes the proof for Lemma - $3$ .

---

Now we prove the theorem stated at the beginning. Let's restate the theorem for convenience.

Statement : For $p, q \in \mathbb N, q\neq1$ and $gcd(p,q)=1$ ,

Base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits $\iff D_q \subseteq D_b$ , where for any positive integer $c$ , $D_c$ is the set of all distinct prime factors of $c$ .

Proof : Assume that base- $b$ expansion of $\dfrac{p}{q}$ terminates after a finite number of digits. Then for some positive integer $m$ , $(\dfrac{p}{q}\times b^m)$ is an integer. As $gcd(p,q)=1$ and $q \neq 1$ , $q\mid b^m$ , which, by Lemma - $1$ , implies, $D_q \subseteq D_b$ .

Suppose, $D_q \subseteq D_b$ . Then, by Lemma - $1$ , $q \mid b^m$ for some positive integer $m$ . Then $\dfrac{p}{q}=(\dfrac{p}{q}\times b^m)\times b^{-m}$ . The right side of the last equation, by Lemma - $2$ , terminates after a finite number of digits, as $\dfrac{p}{q}\times b^m$ is an integer. So does $\dfrac{p}{q}$ , which is the left side of the same equation.

This completes the proof.

---

Now, $D_{67500=2^2\times3^3\times5^4}=\{2,3,5\}$ . That means, each $n$ must be divisible by $2\times3\times5=30$ . There are $\lfloor\dfrac{67500}{30}\rfloor=2250$ such $n\leq67500$ , as the minimum of such $n$ is strictly larger than $2$ .

So, the answer is $\boxed{2250}$ .

---

NOTE :

• Although we state and prove the theorem only for positive fractions/rational numbers $\dfrac{p}{q}$ , it's not hard to see it's valid also for negative fractions.

• Lemma - $3$ isn't used in the proof of the theorem. After writing the proof for Lemma - $3$ , I found this proof of the theorem, which doesn't use Lemma - $3$ .