# Representations of rationals in base n: when are they finite? **URL:** \ **Category:** Factual Questions\ **Created:** [August 20, 2002, 3:17am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697 "2002-08-20T03:17:52Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 20, 2002, 3:17am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/1 "2002-08-20T03:17:52Z")
Well, sure, they’re never actually finite. So when do they stop repeating? I’ve noticed that p/q has a terminating representation in base 10 only if 2 and 5 are the only primes that divide q. I strongly suspect that these are equivalent conditions, and that it’s no coincidence. I’m thinking that p/q will have a terminating representation in base n iff every prime [symbol]p[/symbol] that divides q also divides n. Is this true? If so, how would I prove it? I’m not at all comfortable with number theory, so any answers will have to start at a halfway basic level. ---
**Author:** ![NeutronJack](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/neutronjack/32/4134_2.png) [@NeutronJack](https://boards.straightdope.com/u/NeutronJack)\ **Post date:** [August 20, 2002, 3:55am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/2 "2002-08-20T03:55:12Z")
Consider p=30, q=30. p/q=1, which is doesn’t repeat, but q is divisible by 2, 3, and 5. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 20, 2002, 4:00am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/3 "2002-08-20T04:00:01Z")
Fair enough. Let’s restrict p to be 1, then. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 20, 2002, 4:31am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/4 "2002-08-20T04:31:07Z")
Or at least that p and q are relatively prime (ie, p/q is in simplest form). ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 20, 2002, 4:51am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/5 "2002-08-20T04:51:12Z")
Bah. I posted too fast. I just thought up what I think is a proof for the easy half. That is: _1/q terminates =\> the only prime divisors of q are 2 and 5._ For a real number R, the following are equivalent: “R’s base-10 representation terminates” and “There is some natural number N such that 10[sup]N[/sup]R is an integer”. I don’t think this statement requires much proof, do you? Anyway, then, what we’re given is that there is some N such that 10[sup]N[/sup]/q is an integer, which we’ll call M. So 10[sup]N[/sup] = qM. Fundamental Theorem of Arithmetic. Blah blah blah. The only prime divisors of qM (and thus q) are 2 and 5. Now, I’m not so sure about the other half. The part that says: _The only prime divisors of q are 2 and 5 =\> 1/q terminates._ However, I think it might not be so hard. Let’s see… If q = 2[sup]A[/sup]5[sup]B[/sup], then let M = 2[sup]B[/sup]5[sup]A[/sup], and then qM = 10[sup]A+B[/sup]. Letting N = A + B should do it. Though I’m not as sure about this half. What do you think? ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [August 20, 2002, 11:29am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/6 "2002-08-20T11:29:44Z")
PROPOSITION: Suppose m and n are coprime integers. Then the decimal representation of m/n terminates if and only if n is of the form 2[sup]a[/sup]5[sup]b[/sup]. Proof: If n = 2[sup]a[/sup]5[sup]b[/sup] then m/n = k/10[sup]r[/sup] for some integers k,r. For example if a\>b, m/n = 5[sup]a-b[/sup]m/10[sup]a[/sup] Now it is clear that k/10[sup]r[/sup] is a terminating decimal. Conversely, if m/n = N.a[sub]1[/sub]a[sub]2[/sub]…a[sub]M[/sub], then 10[sup]M[/sup]\*(m/n) is an integer s. Then m/n = s/10[sup]M[/sup] and, after cancellation, n is of the form 2[sup]a[/sup]5[sup]b[/sup]. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 20, 2002, 3:54pm UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/7 "2002-08-20T15:54:52Z")
OK, looks good. It also looks like it’ll generalize to base n. Thanks much, guys. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2002, 12:06am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/8 "2002-08-21T00:06:49Z")
Actually, **Jabba** , I’m not 100% comfortable with the second half of your proof. Could you go over it in a little more detail? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2002, 12:22am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/9 "2002-08-21T00:22:25Z")
> [@](#): > > \*Originally posted by Achernar \* > \*\*Now, I’m not so sure about the other half. The part that says: > > _The only prime divisors of q are 2 and 5 =\> 1/q terminates._ > > However, I think it might not be so hard. Let’s see… If q = 2[sup]A[/sup]5[sup]B[/sup], then let M = 2[sup]B[/sup]5[sup]A[/sup], and then qM = 10[sup]A+B[/sup]. Letting N = A + B should do it. Though I’m not as sure about this half. What do you think? \*\* Even better: you have that qM = 10[sup]A+B[/sup], so 1/q = M/10[sup]A+B[/sup]. That should be good enough–if two rationals are equal, then they have the same representation in base ten. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2002, 12:23am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/10 "2002-08-21T00:23:46Z")
…or any base, for that matter. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [August 21, 2002, 12:59am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/11 "2002-08-21T00:59:44Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*Actually, **Jabba** , I’m not 100% comfortable with the second half of your proof. Could you go over it in a little more detail? \*\* In turn I am not sure where room for confusion lies. What part do you find difficult? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2002, 3:33am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/12 "2002-08-21T03:33:43Z")
I’ll buy that m/n = s/10[sup]M[/sup], but after that, I’m not too comfortable with it. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [August 21, 2002, 10:00am UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/13 "2002-08-21T10:00:09Z")
Okay. I am arguing that after we have cancelled the fraction s/10[sup]M[/sup] into its lowest terms the only prime factors in the denominator will be 2 or 5, since there is nowhere for any other factors to have come from. We can prove this formally: PROPOSITION: Suppose a/b = m/n where a,b,m,n are integers and m,n are coprime ( so that the fraction m/n is in its lowest terms). Then for every prime p, if p divides n then p divides b ( so the only possible prime factors of n are the prime factors of b). It will be helpful to prove first the LEMMA: Suppose that p is prime and x,y are integers. Then if p divides the product xy, p divides either x or y. Note that the assumption that p is prime is necessary here. Thus 6 divides 3\*4 but does not divide either 3 or 4. Proof: By unique prime factorization we can write x and y as products of primes. Then xy can be factorised as the factorization of x followed by the factorization of y and, again by UPF, this is the only possible factorization of xy. Now for every prime p, if p appears in the prime factorization of xy it must have apppeared in the factorization of either x or y ( by construction). Thus p divides x or p divides y, as claimed. Proof of proposition: We have mb = na. Suppose p is prime and p divides n. Then certainly p divides na and thus p divides mb. By our lemma it follows that p divides m or p divides b. But m and n have no common factor greater than 1 and so ( since p divides n) it is imposssible that p should divide m. Thus p divides b and the proof is complete. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2002, 1:41pm UTC](https://boards.straightdope.com/t/representations-of-rationals-in-base-n-when-are-they-finite/124697/14 "2002-08-21T13:41:32Z")
OK, that makes sense. Thanks.