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.

I have been thinking a little bit about the binary decimal expansion of reciprocal prime numbers; and I have a few questions.

I found this neat table which lists the binary expansion of many fractions, and I was trying to find some patterns.

Here are my questions, for brevity I say a natural number has a period N if the binary decimal expansion of it's reciprocal has period N: (for example, 1/7 = .001001... has period 3)

  1. Given an arbitrary natural number N, does there exist a prime number of minimum period N?

(By minimum period I mean to exclude the case that one prime has a period which is a multiple of the period of another prime. For example, 1/3 = .0101... has period 2, and 1/5 = .00110011... has period 4; so while 1/3 has period 4, what I call it's "minimum period" is 2)

2. Can two prime numbers have the same minimum period?

A useful result which I believe is well known, is that a natural number has a period N if and only if it is a factor of 2N - 1.

Does anyone know of a good reference that describes some theory behind the relationship between the period of the reciprocal of a natural number, and the prime factorization of that number?

share|improve this question
    
I recommend changing the phrase "inverse prime numbers" to "reciprocals of prime numbers". The latter has a clear meaning, the former does not. –  Arturo Magidin Sep 3 '10 at 19:41
    
I edited the OP, thanks for the suggestion. –  Matt Calhoun Sep 3 '10 at 19:46
1  
If you look at my answer together with mau's answer on this question, adjusting the base form 10 to 2, that gives you the criteria you're looking for or at least a start on it. –  Isaac Sep 3 '10 at 19:51
3  
For the second question: both 1/41 & 1/271 have period 5; 1/7 & 1/13 have period 6; 1/73 & 1/137 have period 8, ... Relevant Mathematica code: Sort[{Length[Nest[First, RealDigits[1/#], 2]], #} & /@ Prime[Range[500]]] –  J. M. Sep 3 '10 at 20:04
    
From the table I linked: 1/7 = .001 (repeating); 1/13 = .000100111011 (repeating); so although it's true that 7 and 13 have the same period (12), they do not have the same minimum period, so this is not what I am looking for, sorry for the confusing way I stated the question, I am happy to make any edits which are suggested for clarity. Actually I noticed most primes p have a repeating sequence which is p-1 digits long (such as 13, but not 7)... –  Matt Calhoun Sep 3 '10 at 22:47

1 Answer 1

up vote 2 down vote accepted

(In the below post there are several links with the apostrophes omitted; fill them in if the links don't work.)

The phenomenon you are studying is a phenomenon in modular arithmetic. If a prime $p$ has period $n$, this means that there is some numerator $N$ such that $\frac{N}{2^n - 1} = \frac{1}{p}$. This is equivalent to $Np = 10^n - 1$, or $p | 2^n - 1$, or $2^n \equiv 1 \bmod p$. The smallest $n$ for which this is true is called the order of $2 \bmod p$, sometimes denoted $\text{ord}_p(2)$ (although this is confusingly also used to denote the greatest power of $p$ which divides $2$...).

Fermat's little theorem guarantees that $\text{ord}_p(2)$ always divides $p-1$; you have already observed this yourself. However, predicting the exact order is very difficult to do in general. For example, knowing that the order is actually equal to $p-1$ is equivalent to knowing that $2$ is a primitive root, and it is not currently even known whether this is true infinitely often. In any case, you should be able to find basic information about order in any good textbook on elementary number theory.

With that background out of the way...

The answer to question 1 is no. The only exception is $n = 6$ by Zsigmondy's theorem.

The answer to question 2 is yes. If $p$ and $n$ are relatively prime, then $p$ has period $n$ if and only if $p$ divides $\Phi_n(2)$, where $\Phi_n(x)$ is the $n^{th}$ cyclotomic polynomial. (This is more or less a restatement of the condition that $p | 2^n - 1$ but $p$ doesn't divide $2^k - 1$ for $k < n$.) So it suffices to show that some number of this form has more than one prime factor relatively prime to $n$. There are two cases here which are particularly classical:

  • $n$ is a prime $q$. In this case $\Phi_q(2) = 2^q - 1$ is a Mersenne number, and $2^{11} - 1 = 23 \cdot 89$ is the smallest composite Mersenne number, hence $23$ and $89$ both have period $11$.

  • $n = 2^k$ for some $k$. In this case $\Phi_{2^k}(2) = 2^{2^{k-1}} + 1$ is a Fermat number, and $\Phi_{64}(2) = 2^{32} + 1 = 641 \cdot 6700417$ is the smallest composite Fermat number, hence $641$ and $6700417$ both have period $64$.

The answer to question 3 is the following.

Lemma: If $n, m$ are relatively prime odd numbers, then $\text{ord}_{mn}(2) = \text{lcm}(\text{ord}_n(2), \text{ord}_m(2))$.

Proof. $\text{ord}_{mn}(2)$ is the order of the element $2$ in the multiplicative group of $\mathbb{Z}/mn\mathbb{Z}$, which we will denote $U(mn)$. By the Chinese remainder theorem, $U(mn)$ is isomorphic to the direct product $U(m) \times U(n)$, so the order of $2$ in $U(mn)$ must be the $\text{lcm}$ of the orders of $2$ in $U(m)$ and $U(n)$.

It follows that to compute $\text{ord}_m(2)$ for arbitrary $m$ it suffices to compute it for the odd prime power factors of $m$ and then to take the $\text{lcm}$ of the resulting numbers. (Note that if $m$ is divisible by a power of $2$ this only contributes a leading string of zeroes to the binary expansion of $\frac{1}{m}$ and hence does not affect the computation of the period.) Again, you can find a discussion of the Chinese remainder theorem in any good textbook on elementary number theory. (I am particularly bad at recommending textbooks on elementary number theory because I learned mine through a summer program, not a textbook...)

share|improve this answer
1  
@Matt: as a general rule, you should wait maybe a day or so to accept answers. That makes it easier for other answers to accrue which might offer additional insights (as well as specific references, which I haven't provided), and it also allows the relevant answers to receive more votes. (Finally, it allows people to correct anything wrong I might've said :P) –  Qiaochu Yuan Sep 4 '10 at 1:16

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.