How do we know $p/q$ can be expressed as a terminating fraction in base $B$ only if prime factors of $q$ are prime factors of $B$?

Question

On cs.stackexchange I asked a math question: How to demonstrate only 4 numbers between two integers are multiples of .01 and also writable as binary.

Yuval Filmus answered with a explanation depending on knowledge that "a (reduced) rational number $p/q$ can be represented exactly in base $B$ if and only if all prime factors of $q$ are prime factors of $B$." I've tried googling to find how that's known and I've found a couple other posts that mention it as a known fact. It's not self-evident to me, should it be? Is it practical to demonstrate to someone with no background in number theory, or is it a theorem with a recognized name? Or just one of those things that's theorem 8.2 in one textbook and Theorem 24 in another?

I'm just asking out of curiosity - the original question arises in talking about why not to store currency in variables of type double in float.

Thanks

Answer 1

It is an immediate fact.

$\frac{p}{q} \times b^N$ is an integer $M$. Hence, $pb^N = q M$

Since $\gcd(p,q)=1$ (coprime), by Euclid's Lemma (or obviously) $q | b^N$.

So the prime factors of $q$ must be prime factors of $b$.

Answer 2

Suppose $\mathrm{gcd}(x,y) = 1$. The number $x/y$ is representable exactly in base $B$ if for some $n$, we can write $x/y = t/B^n$, or $x B^n = y t$. That is, $x/y$ is representable exactly if $y$ divides some power of $B$. If $y \mid B^n$ and $p \mid y$ for some prime $p$ then $p \mid B^n$ and so $p \mid B$. That is, all prime factors of $y$ must be prime factors of $B$. Conversely, suppose that all prime factors of $y$ are also primes factors of $B$. Write $y = p_1^{s_1} \cdots p_k^{s_k}$, and take $s = \max(s_1,\ldots,s_k)$. Then $y \mid B^s$.

If we're more careful, then we can calculate $n$ exactly. Suppose $p_i^{t_i} \parallel B$ (this is shorthand for $p_i^{t_i} \mid B$ and $p_i^{t_i+1} \nmid B$). Then $y \mid B^n$ iff $s_i \leq nt_i$ for all $i$, and so the minimal such $n$ is $\max(\lceil s_1/t_1 \rceil,\ldots,\lceil s_k/t_k \rceil)$. For example, how many digits are required to represent $1/4$ in base $10$? We have $4 = 2^2$ and $2^1 \parallel 10$, and so the number of digits required is $\max(\lceil 2/1 \rceil) = 2$.