Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 7 down vote accepted

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$.

share|improve this answer
    
And conversely. –  André Nicolas Jun 30 '13 at 15:11
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.