Decimal expansion of 1/p, where p is prime - length of repeating sequence?

Factual Questions
1

Is there any way (hopefully a ‘simple’ way if I’m going to understand it) to determine if for a given prime (p), the decimal expansion of its reciprocal (1/p) repeats with length p-1?

For example, for the prime 7, the decimal expansion of its reciprocal, 1/7, is .142857142857142857 . . . i.e. 142857 repeating, the repeating set of digits thus having length 7-1 which equals 6.

Likewise, for the prime 17, the decimal expansion of its reciprocal, 1/17, is .058823529411764705882352941176470588235294117647 . . . i.e. 0588235294117647 repeating, the repeating set of digits thus having length 17-1 which equals 16.

On the other hand, for the prime number 13, the decimal expansion of its reciprocal, 1/13, is .076923076923076923 . . . i.e. 076923 repeating, the repeating set of digits having length 6, which is not equal to 13-1.

In other words, for some primes, their reciprocals’ decimal expansion consist of a sequence of p-1 digits repeating, whereas for other primes the decimal expansion of their reciprocals consists of a repeating sequence of length less than p-1 (i.e. evidently of length (p-1)/k for some integer k)

Last November, we had a thread about the decimal expansion of 1/7. In the discussion that ensued, there was mention of cyclic numbers which seem to be of relevance here, but the question I am asking was not addressed.

So, my question again: For a given prime number p, is there any way to determine if the decimal expansion of its reciprocal (1/p) repeats with length p-1?

Thanks!

2

3 is prime and 1/3 repeats every single digit. 5 is prime but 1/5 doesn’t repeat at all. 11 is prime and 1/11 repeats every 2 d8gits.

Why do you suspect that there is a pattern?

3

Not so much a pattern as a rule; a rule to determine if the reciprocal of a given prime has a decimal expansion consisting of a repeated sequence of digits of length p-1.

Or, what may be equivalent, a rule or procedure to determine the length of the repeated digit sequence in the decimal expansion of a prime’s reciprocal.

ETA: I suspect there is a pattern, yes. But, can I justify my suspicion? No, not even close. Still, this type of thing, asking this type of question - and expecting that there’s an answer - is one of the reasons I like math.

4

A test for the number of digits (if you already have a guess, or an algorithm is as good as a function.)

If the number of repeating digits of p/q is n digits.
then 10^n - 1 has q as a factor .

( for the algorithm, start by testing for the smallest n first ? to find the smallest number that can be repeated… because repeating 4545 is the same as repeating 45… right ?)
an 11th ? 99 is divisible by 11, so 2 digits
For 13th’s … is 99 divisible by 13 ? 999 ? 9999 ? 99999 ? No. 999999 is… ( 13 * 76923 = 999 999 ) So 13ths can be expressed as repeating of 6 digits.

142857/999999 ? Do you recognize the top line ? there are 7*142857 = 999 999.
q is 7 , its 1/7th… So 9, 99 , 999 ,9999 , and 99999 do not have 7 as their factor., but 999 999 also has 7 as a factor. ( along with 13 )

The algorithm would be efficient if you already calculated the factors of 9, 99 ,999,etc and stored the data for efficiency of look up… then just looked up the information

5

The prime numbers 2 and 5 are special cases, because they are factors of the base 10, so the decimal expansions of 1/2 and 1/5 terminate.

For all other primes, the prime number p is a factor of 10^(p-1)-1, i.e., the number 999…999 with p-1 9’s. So every fraction 1/p has a decimal expansion which repeats after p-1 digits – for example, 1/7 repeats after 6 digits, and 1/17 repeats after 16 digits.

However, some primes repeat sooner than that maximum. For example, 1/37 repeats after 36 digits, but 37 is also a factor of 999, so it repeats after 3 digits, i.e., .027027027… . That means, of course, that the minimum 3 is a factor of that maximum 36.

So the rule is, for any base b (not just for base 10), and for any prime p where p is not a factor of b, the decimal expansion repeats after p-1 or a factor of p-1.

6

Here’s a paper that may interest you

7

That can be justified.

If you have n digits repeating , then put them over (10^n)-1… to get a fraction to represent them.

eg .5353535353 repeating 53 … is 53/99.

But how to show this ? I can test it many times… but how to show its always true ?

Well I suspect you can do it, by showing that where you put z/10^n as the value of the first set of n digits, you can show, by simplifying z/((10^n)-1) - z/10^n appropriately, to get 1/10^n of the first step…So 2nd set of digits would again be z … the repeater. and the third set is also z etc.

OR having tested it many times, just accept it as true…

8

First, notice that:
1/9 = 0.111…
1/99 = 0.010101…
1/999 = 0.001001001…

You can see that if you multiply the number by 1-digit, 2-digit, etc. numbers respectively, you get a repeating decimal of varying lengths.

The right hand-side can be expressed as (where r is the repeat count):
s = Σ[n=1] (1/10[sup]r[sup]n[/sup][/sup])

That’s a geometric series with a factor of 1/10[sup]r[/sup], which has a sum of:
1/(1 - c) - 1 =
1/(1 - 1/10[sup]r[/sup]) - 1 =
10[sup]r[/sup]/(10[sup]r[/sup] - 1) - 1 =
(10[sup]r[/sup] - (10[sup]r[/sup] - 1))/(10[sup]r[/sup] - 1) =
1/(10[sup]r[/sup] - 1)

This final expression is equivalent to 1/9, 1/99, etc. where r is the number of digits, and hence the repeat length.

9

I appreciate the thought but have to be honest - it’s all way, way beyond me. Not even close. (sigh).

I appreciate everyone’s comments but specifically want to ask Giles about what you said:

And 13 is a factor of 999999, so it repeats after 6 digits? Is that it? I thought it would be much more complicated. Thanks.

10

Primes p such that the expansion of 1/p takes a full p - 1 digits (and not any less) to repeat are called “full reptend primes”, or, in other jargon, “primes p such that 10 is a primitive root modulo p”. There’s a 1-to-1 correspondence between them and cyclic numbers, as you began to note; the finite block of repeating digits of any full reptend prime describes a cyclic number, and conversely, repeating any cyclic number infinitely produces the decimal expansion of the reciprocal of a full reptend prime.

As far as I’m aware, there’s no particularly nice way to tell whether a prime p is or is not of this form, except by, well, checking how long it takes for the expansion of 1/p to repeat digits (equivalently, finding the smallest power of 10 which is equal to 1 modulo p). But here’s a list…

11

I dug up the following in the popular-level book Excursions in Number Theory:

This is from a book originally published in 1966 and reprinted in 1988, so there’s no guarantee progress hasn’t been made since then. I do find the following interesting theorem:

For example, take q = 13. The primes of period length 13 are 53, 79, and 265371653. Multiplying these together yields 1111111111111.

12

Yes! 1/p has decimal period length p-1 if and only if 10 is a primitive root modulo p (as Indistinguishable beat me in mentioning).

Under the assumption of a Generalized Riemann Hypothesis, it has been proven that there exist infinitely many primes p such that 10 is a primitive root modulo p, and the density of such primes is known. This follows from Hooley’s conditional proof of Artin’s Conjecture on Primitive Roots.

And, Indistinguishable, you are correct that there is no known “nice” way to determine whether, given a prime p, 10 is a primitive root modulo p. The quickest way, rather than doing the (possibly very lengthy) division is to calculate the order of 10 modulo p. In order to do this fast, though, we need to know the prime factorization of p-1. Since ord_p(10) | p-1, we can do this calculation faster than the division (well, usually).

I am a number theorist, and I love this particular topic.

13

As for the business about strings of 1s which Thudlow Boink mentioned, most of that seems straightforward, but there’s one bit I’m stuck on.

Since 0.[any q digits repeating] = (that q-digit number)/(q many 9s), we have that the period of a fraction divides q just in case the fraction’s lowest-terms denominator divides (q many 9s).

If we look at the prime factorization of (q many 9s), there will of course be a factor of 3[sup]2[/sup], leaving (q many 1s) to be factorized. As for whether any factors of 3 remain in (q many 1s), by the well-known criterion for divisibility by 3, this will occur just in case q itself is divisible by 3.

So (q many 1s) is the product of all those primes with reciprocal period dividing q, except excluding 3 in the case where q is not divisible by 3, and possibly with some primes repeated.

In the case where q is a prime greater than 3 and (q many 1s) is square free, this tells us that (q many 1s) is the product of the primes with period exactly n.

All that remains is to show that (q many 1s) is in fact square-free whenever q is a prime greater than 3 (or, just as well, whenever q is prime at all). But this, I’m stuck on…

14

Well, Yates’ 1978 article “The Mystique of Repunits” claims it to be an open problem as to whether (q many 1)s is square-free for all prime q [noting that this fails in non-decimal bases; for example, in addition to the trivial examples of length 2, we have that 11111 is eleven squared in base 3]. Thus, either I incorrectly interpreted the claim from “Excursions in Number Theory” as carrying an implication that no prime factor would have to be repeated in (q many 1)s for prime q, or the question as to whether this would ever happen was settled in the negative between 1978 and 1988 with the claim being added to “Excursions in Number Theory” on its reprinting, or Yates was unaware that this problem had already been so solved in 1978, or the claim was made accidentally without proof.

15

Let q be an odd prime, and let N be the integer represented by q 1’s. (We are assuming decimal representation throughout.) The rational primes appearing in the prime factorization of N are exactly the primes which ramify in the algebraic number field K=**Q**(10^(1/q), \zeta_q), a Kummer extension of Q, where \zeta_q is a primitive qth root of unity. By a standard result in algebraic number theory, there are only finitely many such primes.

I’m glad you posted that the question you posed, Indistinguishable, is open, since I’ve spent the past two days trying to prove it, with no success (and I obviously haven’t found a counterexample). We might hope to glean information about the multiplicity of the primes “downstairs” from the splitting/ramification behavior of the primes in K lying above primes in the prime factorization of N. I think I’ll stop now, and read the link you posted.

16

Very simple - you can set the upper limit of repeating for 1/p at p-1.

Divide p into 10000000000000000 or 1.000000000000000 or anything.
The remainder dividing by p will obviously be 0 to p-1. Divide that by p, and the remainder again is in that range. And so on.
Before you have divided into the remainder p times, you will get the same remainder as you had previously. At that point, you are in a repeating sequence.

For example, 1/7
1.0000000… divided by 7 -
10/7 gives 1 remainder 3. (answer 0.1…)
30/7 remainder 2 (0.14…)
20/7 remander 6 (0.142…)
60/7 remainder 4 (0.1428…)
40/7 remainder 5 (0.14285…)
50/7 remainder 1 (0.142857…)

  • oh look, we are repeating from the top… 10/7 ( final answer 0.142857 142857 142857…)

Obviously if you hit a 0, it ends.
The repetition will possibly be less than p-1 - i.e. 1/3 - 10/3 sequence never gives a remainder other than 1.

17

Yes. I don’t know if the previous answers have made this clear, but it is a theorem that if p is a prime other than 2 or 5, the period of the decimal representation of 1/p is the multiplicative order of the residue class of 10 in the finite field with p elements. It is the smallest positive integer k such that 10^k is congruent to 1 modulo p. In particular, k is a divisor of p-1 (therefore it is necessarily less than or equal to p-1). The proof of this statement is elementary.

18

Hi @RayMan

I know you posted this a long time ago but I was just doing some work as a CS undergraduate on full repetend primes and wanted to ask you regarding the last few lines you wrote here.

Currently, to find all primes with full repetends, I am finding out all primitive roots and then checking if 10 is in there somewhere. This is the python code from stackoverflow:

from math import gcd as bltin_gcd

def primRoots(modulo):
    required_set = {num for num in range(1, modulo) if bltin_gcd(num, modulo) }
    return [g for g in range(1, modulo) if required_set == {pow(g, powers, modulo)
            for powers in range(1, modulo)}]

print(primRoots(17))

Now I’m not a maths expert nor a number theory expert but your final paragraph seems to detail a more efficient way to do what I’m doing but I can’t really understand it.

Would you be able to help me out?

20

Welcome, @csstudent. I hope you get an answer, and if there’s any place online where the answer can be found, it’s probably here… but I must warn you that seven years is a long time online, and neither @RayMan nor @Indistinguishable is around much any more. Though of course, they’re both welcome to come back, too.

And even if you don’t find the answer to that specific question, you might want to stick around. This is a fun place to be a nerd.

21

Isn’t he just saying to compute powers of 10 modulo p? You can do it by multiplying by 10, then reducing modulo p, each time. Eventually you get 1.