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

Factual Questions
22

I read the boards every single day, @Chronos. I was pleasantly surprised to see this old topic come up. I’m no longer a mathematician in my day job, but I’ll jump at any excuse to talk algebraic number theory.

@csstudent, I am assuming that you are approaching this topic from a coding point of view: you want to write code to find full reptend primes, and you are not so much interested in the theory behind it. If I’m mistaken, please correct me. There is quite a bit of theory (I mentioned it briefly above), and modern analytic and algebraic tools in algebraic number theory and class field theory have yielded beautiful results relating primes which have a particular primitive root to the splitting/ramification behavior of prime ideals in algebraic number fields.

But unless you really want to know that theory, we’ll stick to an algorithm (hopefully as efficient as possible, much more on that later) to determine whether a given prime p is a full reptend prime. As I mentioned seven years ago, prime p is a full reptend prime if and only if 10 is a primitive root modulo p.

If I understand your code correctly, you are finding all of the primitive roots modulo a given prime p (again, please correct me if I am wrong). There is no need to do that. There are exactly phi(p-1) incongruent primitive roots modulo p, where phi is the Euler totient function. Instead of doing that, just determine whether the multiplicative order of 10 modulo p is equal to p-1. It is that simple. I have never checked, but I’m sure someone has written a function in some library to calculate the multiplicative order of an integer modulo some modulus. As a CS student, you should be able to whip it up in just a few lines of code.

But here is the huge, huge caveat: except for the deep deep theory I mentioned above, determining the multiplicative order of 10 modulo p requires us to know the prime factorization of p-1 if we have any hope of doing the calculation for large p in tractable time. As a CS student, I expect you know, or will know soon, that there is no known algorithm for determining the prime factorization of large integers in polynomial time. If you find such an algorithm, please mention me in your speech when accepting the Millennium Prize.

The number of prime divisors of p-1 has normal order log log p-1, and so grows without bound as p does. From elementary group theory, we know that the multiplicative order of 10 in the finite field with p elements is a divisor of p-1. If we know the prime factorization of p-1, just calculate 10^k modulo p for each divisor k of p-1 less than p-1. If any of those powers is congruent to 1 modulo p, then p is not a full reptend prime. If none of those powers is congruent to 1 modulo p, then p is a full reptend prime. Q.E.D.

I will be interested to see your code. I expect even if you use a library function, it will not run in polynomial time.

Thank you for the question. I’m a data analyst these days, I don’t teach (or really study) math any more. But I still love it.

23

Wow, thanks for the detailed response. Your passion is almost inspiring!

In essence my real task was to find the largest number less than n that produces the largest repetend.

I planned to work backwards from n, figure out if the current number is a full prime, and if so, then it makes sense that I’ve found the number.

I used a few different tests to see if my number is a full prime but believe it or not so far the quickest method is calculating the full period of the repetend and actually checking it it is equal to n-1.

I thought I could just loop through my list of primes, and just check if

10^{p-1} \equiv 1 (mod \text{ p})

since this would allow me to know if 10 is a primitive root modulo p but I quickly found out that non full primes can also have this property so I’m guessing it only works one way? Meaning is it a sort of surjection where a full prime must necessarily have the above property but having the above property doesn’t necessarily mean you are a full prime?

I then used the method I asked about in my original question which uses another definition, and what that tries to do is see if the group generated by all the powers of a number, in my case 10, is 1 \cdots n-1, and this would mean it is a full prime.

This was extremely slow - both earlier methods ran in ~0.001s and had a small margin of difference but this method ran in approx 4s.

Your explanation made sense (I think) and in my next version, I will find the prime factorisation of n-1 and then check if each of 10^{k} \equiv 1 \text{ mod p}
for these divisors. If yes - move on to the next prime.

Is that correct?

I must say thanks for the welcome @DPRK. I only stumbled across this board for this question but it does seem like a nice place.

Also thanks again @RayMan - your passion really does come across! I’m a CS and Maths double major student and one day hopefully want to go into something data myself.

On a side note, I know a lot of this work was done by Gauss and I’ve found a few others in Dickson’s History of Theory of Numbers. Would you happen to know who discovered that a full prime k must satisfy 10^{k-1} \equiv 1 mod k? And also who discovered what you spoke about, i.e. the powers of divisors of k-1 shouldn’t be congruent to 1 mod k?

Thanks all, I really appreciate the responses :slight_smile:

24

Cool. Be careful, I could go on forever. No one wants that.

Some of your terminology is a little difficult to understand, but I believe that you have the algorithm down. Let’s introduce a few concepts here:

Definitions and elementary properties: Let m \in \mathbb{Z} with m > 1. Let \mathbb{Z}/m\mathbb{Z} denote the ring of integers modulo m, and let \mathbb{Z}/m\mathbb{Z}^\times denote the multiplicative group of units of \mathbb{Z}/m\mathbb{Z}. Then the order of \mathbb{Z}/m\mathbb{Z} is m, and the order of \mathbb{Z}/m\mathbb{Z}^\times is \phi(m), where \phi denotes the Euler totient function. Very importantly, we have a formula for \phi(m), which is easy to calculate (e.g., via simple code) if we know the prime factorization of m. It is:

\displaystyle \phi(m)=m \prod_{p \mid m, p \, prime} \left(1-\frac{1}{p}\right)
where the product above is over all prime divisors p of m. This is crucial! If m is very large and we do not know the prime factorization of m, calculating \phi(m) is intractible. Fortunately for us, p is a prime if and only if \phi(p)=p-1. However, if p is very large, finding the prime factorization of p-1 is intractible.
\mathbb{Z}/m\mathbb{Z} is a finite commutative ring with unity, so it is a finite abelian group with the binary operation addition modulo m. \mathbb{Z}/m\mathbb{Z}^\times is the multiplicative group of units (equivalently, the congruence classes with representatives relatively prime to m). \mathbb{Z}/m\mathbb{Z} is cyclic if and only if there exists a primitive root modulo m. There does not always exist a primitive root modulo m! But we need some more elementary definitions and properties.

As before, let m \in \mathbb{Z} with m > 1. Let n \in \mathbb{Z} with \gcd(m, n)=1. We say that the multiplicative order of n modulo m is equal to k (denoted \mbox{ord}_m(n)=k) if k is the smallest positive integer such that n^k \equiv 1 (mod m). The multiplicative order of an integer we have described here is well-defined, in the sense that the order of the cyclic subgroup generated by n divides \mid \mathbb{Z}/m\mathbb{Z}^\times \mid, stated with a little more detail below.

Additionally, let m \in \mathbb{Z}, m > 1, and n \in \mathbb{Z} with \gcd(m, n)=1 as before. We say that n is a primitive root modulo m if \mbox{ord}_m(n)=\phi(m). It is a theorem that for p prime, \mathbb{Z}/p\mathbb{Z}^\times is cyclic, and so there exists a primitive root modulo p. One can characterize the other, nonprime integers for which there exist primitive roots, but I will not do so here. There do exist integers m such that \mathbb{Z}/m\mathbb{Z}^\times is not cyclic, and so m does not posses a primitve root. The group structure of \mathbb{Z}/m\mathbb{Z}^\times is given by the Fundamental Theorem of Finitely Generated Abelian Groups. I hope it is clear that if there exists a primitive root n modulo m, then \mathbb{Z}/m\mathbb{Z} is cyclic, and the equivalence class with representative n is a generator.

With these niceties out of the way, we recall that Lagrange told us that the order of any subgroup divides the order of the group. So, the cyclic subgroup \langle n \rangle \leq \mathbb{Z}/m\mathbb{Z} has the property that \mid \langle n \rangle \mid divides \mid \mathbb{Z}/m\mathbb{Z} \mid =\phi(m). And now, one of the most important theorems in number theory and group theory:
Fermat’s Little Theorem (NOT his Last Theorem): Let p be a prime and a \in \mathbb{Z} with \gcd(p, a)=1. Then a^{p-1} \equiv 1 (mod p). This is a special case of a more general theorem, which I believe is attributed to Euler, or maybe Lagrange, that if \gcd(a, m)=1 then a^{\phi(m)} \equiv 1 (mod m). Fermat never published a proof of his theorem, and my source claims that Euler provided the first proof of Fermat’s Little Theorem in 1736.

I’m omitting all proofs of the above; they can be found in any elementary text of number theory or group theory. The proof that p is a full reptend prime is maybe a little too complicated for a message board, but it essentially follows from the elementary properties we have begun to outline here. We have barely scratched the surface: algebraic number theory and class field theory await you.

SO, what does this tell us? Given a prime p with p \neq 2 and p \neq 5, \mbox{ord}_p(10)=k for some positive integer k such that k divides \mid \mathbb{Z}/p\mathbb{Z}^\times \mid = \phi(p)=p-1. p is a full reptend prime if and only if 10 is a primitive root modulo p which by definition is equivalent to \mbox{ord}_p(10)=p-1. So, check all positive integers k such that k \mid p-1 and k < p-1. If even a single one of them has the property that 10^k \equiv 1 (mod p), the p is not a full reptend prime. Otherwise, p is a full reptend prime. Q.E.D. That is the algorithm.

I’m sure I’ve made a million mistakes. Please forgive me for my errors.

As an aside, here are two notes I wrote in grad school related to this topic:
A Note on Perfect Shuffles
Primes p such that 2 is a primitive root modulo p

I do hope this links work. Please share your code with me, if you are willing. I understand if you don’t want to. I am curious about the algorithmic complexity of your code. I’ve coded for number theory investigations in C++. Once you get to primes with multiple hundreds of digits, you run into the NP completeness issues, and I figure I’m more likely to prove the Riemann Hypothesis than get my code to run in polynomial time.

Good luck, and enjoy the math and computer science. Good stuff.

25

Your code may or may not be slow, but how are you running into non-deterministic problems or non-polyomial-time computations just to figure out the order of an element in a group, or by doing the long division?

26

Oh no. I said in my post, written at 2am when I should have been sleeping, “I’m sure I’ve made a million mistakes, please forgive me.” I hope you will forgive me.

I made some crack “Once you get into primes with multiple hundreds of digits, you run into NP completeness issues [. . .]” which I have in my research, but this problem is not an example of that. The problem we are discussing here, finding the order of a in \mathbb{Z}/m\mathbb{Z}^\times has not been proven to be NP complete, and in fact it is suspected that it is not NP complete. It is in class NP.

I have no defense for my error. I’ll only feebly note that these days I get paid to do statistics and not number theory research, a situation I find unfortunate but much more rewarding financially.

@DPRK, as I hope my posts have made clear, if the prime factorization of m-1 is known, then finding the multiplicative order of n modulo m is trivial. I have outlined an algorithm for doing so, and I am sure that every modern computer language library has efficient code for doing so. This problem is equivalent to the discrete logarithm problem, and to quote from Wikipedia, “Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. Several important algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution.” I believe that quantum computing has yielded promising results regarding the algorithmic complexity of this problem, but I am not very knowledgeable about this topic.

There are significant theoretical (definitely not computational) results about primitive roots modulo a generic modulus (not necessarily prime) given by Hooley and Heath-Brown. All of this is related to Artin’s Conjecture on Primitive Roots, which has been proven conditionally under the assumption of a generalized Riemann Hypothesis. It is related to the splitting/ramification behavior of ideals sitting above rational primes in algebraic number fields that are Kummer extensions of \mathbb{Q}. There are beautiful results tying higher order reciprocity theory and class field theory to the problem. These results, so far as I know, are utterly pure and irrelevant to the algorithmic complexity of the discrete logarithm problem. So, no help for writing computer code.

My lengthy discussion of algorithmic complexity is, admittedly, somewhat of a tangent to the original question posted seven years ago, but I hope it is an interesting or at least informative tangent.

27

You sound like some of my students. Maybe one day I will be inspiring.

28

Sorry for being confusing. @csstudent 's algorithm is polynomial in the size of the group, but, you are right, that does not help if n is big.

29

Once again, thanks for the incredibly detailed response. I’ll attempt to take my time to digest the information and translate it into what I need once I begin coding and will be sure to share the code once I have done so.

I do really appreciate your help and the fact that you’ve taken the time out to give me such informative answers. I read a tweet the other day about how a lot of people when asked why they went into math answer with, ‘I had this teacher…’

My case was similar and I’m sure you will have inspired many already - no need to speak about the hypothetical maybe some day.

Thanks @DPRK for adding to the discussion also.

I have some other deadlines at the moment but will keep you guys updated!

Edit: I just remembered I won’t be able to share my code on the board due to plagiarism checks which will render my work useless but if there is a private message feature on here I can send you directly

30

Was doing some quick testing of the logic you gave me but I’m not sure if I’m doing something wrong.

I have a for loop going from the largest prime I need to test, say 457 down to 9.

For each prime p calculate the prime factorisation of p-1.

For each prime factor k, calculate 10^k mod p.

If any calculation involving k gives the result 1, skip to the next prime. If not, then p is a full repetend.

When testing the none full repetend prime 449 with prime factors 2 and 7, neither of 10^{2} or 10^{7} is equivalent to 1 mod p so it is being classed as a full repetend.

Where’s my logic going wrong? If you need to see code please private message me - I have no idea how to do so.

Thanks in advance

EDIT: again, my bad. I’m rushing the gun and not reading properly. Should be divisors not prime factors. I think that’s a lesson to take my time and not rush.

31

I think I see the issue right away: you need to check every divisor of p-1, not just the prime divisors. In other words, every prime factor is a divisor, but not every divisor is a prime factor. The order of an integer modulo p can be a composite integer.

I think that right there might be the issue. I hope so. But please let us know if you have any other questions.

Edit: And I see your edit beat my reply. I think you’ve got it.

32

Yep, thanks. As mentioned I will try and take it a bit slower.

On a side note, if my task is to find the largest x less than n such that 1/x produces the largest period, am I overlooking non-primes?

Realistically there isn’t any reason why I should be overlooking numbers that aren’t divisible by 2 or 5 but also not prime is there?

33

I confess, I’m not sure I completely understand your question. The original question, posted 7 years ago, concerned the decimal representation of \frac{1}{p}, for p prime, so everything I’ve written so far has concerned fractions where the denominator is prime.

If I’m understanding your question correctly – and I fully admit I may not be understanding it correctly – you’re asking essentially why are we restricting ourselves to prime denominators, why not consider composite denominators?

One thing to note from a pure perspective is that if m is a composite integer, \mathbb{Z}/m\mathbb{Z}^\times is not necessarily cyclic; sometimes it is and sometimes it isn’t. The integers for which it is cyclic have been characterized: there is a theorem that some texts call the Primitive Root Theorem that characterizes them; there are infinitely many such generators for the quotient groups.

Please forgive me for being nonrigorous and somewhat casual in what follows: what I am going to casually call the “maximality” of the period of the repeating portion of the decimal representation of \frac{1}{m} for arbitrary m \in \mathbb{Z,} m \neq 0, m not necessarily prime, is related to the fact that when 10 is a primitive root modulo m (this necessarily requires \gcd(10, m)=1, the powers of 10 consist of all the integers relatively prime to m, and, very importantly from Eulers Theorem, 10^{\phi(m)}\equiv 1 (mod m). (We’re talking equivalence classes in the quotient group – I’m being very nonrigorous here). If m is prime, every positive integer less than m is relatively prime to m, and so the numbers in the decimal representation of \frac{1}{m} can run through every power of 10 (if 10 is a primitive root modulo m and m is prime). If m is composite, then \mid \mathbb{Z}/m\mathbb{Z}^\times\mid = \phi(m) < m-1, and so the powers of 10 modulo m cannot take on the “maximal” number of values.

I need to think about your question a little bit. I’ll follow your advice of not rushing.

34

I think the ambiguity here is my fault. I came into the discussion with the wrong preconceptions it seems.

To be clear, my task is given a number n, find x<n such that the period of 1/x is the largest. If any two x give the same largest period, pick the biggest one.

As part of my research I came across full primes and probably incorrectly assumed that n should be a full prime but I have no reason to assume that right?

I thought if I work backwards from n and find my first full prime this would be my x, but there could be a non-prime between this first full prime x and n with longer period of I’m not mistaken?

Or am I justified in my restriction to only considering primes?

35

@csstudent no, given n such an x maximizing the period need not be prime.

I mean, it could be in some cases, but, e.g., say n = 300 is a counterexample with x = 17^2.

36

Just as I feared.

I guess my algorithm which just checks the period of decimal to verify its a full prime is actually the best method then as it also works for non primes.

I had done a lot of research into full primes and my whole report was going to be based around the history and different methods of full primes but I guess I’ll have to pivot it into something else now.

37

@DPRK, you chose a modulus m = 17^2 with the property that \mathbb{Z}/m\mathbb{Z}^\times is cyclic and 10 is a primitive root modulo 17^2. This is not a coincidence.

@csstudent, the moduli you must consider are positive integers of the form p^k or 2p^k for p prime and k \in \mathbb{N}. These are exactly the integers characterized by the Primitive Root Theorem (some texts call it this, this name shouldn’t be considered universal) with the property that \mathbb{Z}/m\mathbb{Z}^\times is cyclic. Note that m=p^k with k=1 is the special case of the denominator being prime we were discussing before you broadened the discussion with your question. If 10 is a primitive root modulo a modulus m of the form p^k or 2p^k, then the period of the decimal representation of \frac{1}{m} is “maximal” in the sense I described it earlier.

Please note that you still need to do some work: I do not know of an a priori way to determine which of those reciprocals of integers will have the largest period (I mean, there might be a way, but if there is I am not aware of it). It just means that you can narrow down your search. Instead of checking every integer, you just have to check that 10 is a primitive root modulo the integers of the form I have mentioned. That saves a whole lot of work, or in the case of a computer algorithm, it saves a whole lot of cases to consider.

All of this can absolutely be proven, by the way. The Primitive Root Theorem will be a part of it, plus some very reasonable number theory/group theory. A messageboard is just not the place for it.

EDIT: “Primitive Root Theorem” shouldn’t be considered standard. I’ve poked around and I’ve only found it in one of the many many group/field/number theory texts I have. But it is a very fundamental result in group/field/number theory.

So, to affirm what @DPRK said: he is right, the reciprocal of a prime may end up having the largest period, etc., in the way you described, but it doesn’t have to be. It could also be an integer of the form m=p^k or m=2p^k. But it must be an integer of one of those forms.

38

. . . And an observation: if m=2p^k then \gcd(10, m)>1, and so 10 cannot be a primitive root modulo m. So you only need to consider the prime powers. Just like that, half of the cases to consider (in some sense) just disappeared.

39

Sure, about when (\mathbb{Z}/m\mathbb{Z})^\times is a cyclic group, but there should be more that @csstudent needs to do for his or her research project. It is easy to check small examples like 17^2 and 19^2 by hand, but the next step is to construct (bigger) examples of “record period” m that are not “full primes”, or prove that none exist. It is not a mere matter of checking that 10 is a primitive root: for example consider m=7^3.

40

I do not know what you mean here. I am considering m=7^3. I consider it a good number. I don’t know what you mean by this.

“Full reptend prime” has been defined elsewhere in this thread (though not by me). We have expanded our consideration to decimal expansions of reciprocals of integers that are not necessarily prime now (that was not the original consideration, posted seven years ago), so primes may not be the integers that @csstudent seek (as you correctly pointed out earlier).

This is the problem @csstudent has described:

My contention is that given n, the x in question must be of the form x=p^k for p prime, p \neq 2, p \neq 5, k \in \mathbb{N}, and 10 a primitive root modulo x. I also said this earlier:

Yes, @csstudent still needs to do some work, as I explicitly stated earlier. I do not know which of the reciprocals of those integers will have the largest period, and I said as much. How do you find which one has the largest period? Well, I know of no other way than to . . . do the division and find out which one has the longest period. As I said, maybe there is some a priori way to know, but if there is, I do not know what it is.

To speak in perhaps clearer mathematical language, the criteria I have outlined give necessary but not sufficient conditions for determining, given n, the possible x values which satisfy @csstudent’s requirements. It will cut down on the number of cases to consider. But, at least as of right this moment typing this, I fear that performing the division may be unavoidable.

41

In fact it is not a “good number”, because the decimal period of 1/7^3 is 294 but the period of 337<7^3 is 336 > 294.

But now let’s say I want the next “good number” that is (1) greater than 19^2 and (2) is not a “full reptend prime”. Seems like an excellent opportunity for a computer search? Or is it obvious what it is?