1

Reading up on positional notation and converting between different bases, I came across this statement:

For integers p and q with gcd(p, q) = 1, the fraction p/q has a finite representation in base b if and only if each prime factor of q is also a prime factor of b.

I'm trying to construct a proof of such, but all I have so far (not much) is: $$p/q = p\times q^{-1} = p \times \left(\prod\limits_{i}a_i\right)^{-1}$$ where each element $a_i$ is one of $q$'s prime factors. I imagine the next step is converting $\prod\limits_{i}a_i$ to base-$b$, but I'm not sure how to tackle that. Any help?

ivan
  • 3,237

1 Answers1

3

Suppose that $q=a_1^{r_1}a_2^{r_2}\dots a_m^{r_m}$, where $a_1,\dots,a_m$ are distinct primes, and $r_1,\dots,r_m$ are positive integers. Suppose further that $a_k\mid b$ for $k=1,\dots,m$. Let $r=\max\{r_1,\dots,r_m\}$; then $q\mid b^r$, so there is an integer $s$ such that $b^r=qs$. Clearly, then, $$\frac{p}q=\frac{ps}{qs}=\frac{ps}{b^r}\;.$$ Thus, $b^r\left(\frac{p}q\right)$ is an integer, and the base-$b$ representation of $\frac{p}q$ is that same integer shifted $r$ ‘decimal’ places to the right. In particular, it terminates.

For the other direction, if $\frac{p}q$ has a base-$b$ representation that terminates with $r$ digits to the right of the ‘decimal’ point, then $b^r\left(\frac{p}q\right)$ is an integer, and you can reverse the reasoning above to show that each prime factor of $q$ must divide $b$; I’ll leave you to work out the details.

Brian M. Scott
  • 616,228