A Euclidean-like division algorithm for converting prime reciprocals into ternary numbers

Graphic1 For the purposes of some work I was doing involving ternary numbers, I became interested in finding a quick and easily programmable method for converting prime reciprocals into ternary representation. By trial and error I found a Euclidean-like division algorithm which works well, as illustrated by the following application to the calculation of the ternary representation of the prime reciprocal \frac{1}{7}:

3 = 0 \times 7 + 3

9 = 1 \times 7 + 2

6 = 0 \times 7 + 6

18 = 2 \times 7 + 4

12 = 1 \times 7 + 5

15 = 2 \times 7 + 1

The first equation always has 3 on the left hand side and the remainder in each equation is multiplied by 3 to obtain the left-hand side of the next equation. The procedure halts when a remainder is obtained which is equal to 1. From then on, the pattern of the coefficients of the prime denominator will repeat indefinitely. In the above example a remainder of 1 is obtained at the sixth step, and the pattern will repeat from then on, so looking at the coefficients of 7 we conclude that the ternary representation of \frac{1}{7} is 0.\dot{0}1021\dot{2} where the dot notation is used to indicate that the string of digits between the dots repeats indefinitely. This is completely analogous to the fact that the decimal, i.e., base-10, representation of \frac{1}{7} has the repeating cycle structure 0.\dot{1}4285\dot{7}. Note that the cycle length is 6 in the ternary representation of \frac{1}{7} precisely because 6 is the order of 3 modulo 7. (The order of an integer modulo a prime p is the lowest power of the integer which is congruent to 1 mod p. A well known theorem of Fermat guarantees that the order of any integer modulo a prime p is at most p - 1).

A further illustration is the computation of the ternary form of \frac{1}{13}, for which the division algorithm yields

3 = 0 \times 13 + 3

9 = 0 \times 13 + 9

27 = 2 \times 13 + 1

before the remainder repeats, giving the ternary representation 0.\dot{0}0\dot{2}. The cycle length for \frac{1}{13} is 3, which is due to the fact that 3 is the order of 3 mod 13.

In general, for a prime reciprocal \frac{1}{p}, the ternary cycle length will always be the order of 3 mod p, and the cycle will repeat from the first digit after the point.

To implement the above algorithm I wrote the following Python program which reads a list of primes from a text file (in this case, the first 100 primes greater than 3), then computes the ternary representation of the corresponding prime reciprocals, depositing the output in another text file. The output for each prime reciprocal is the first cycle of ternary digits (the cycle repeats indefinitely thereafter), as well as a statement of the cycle length.

pic01

The full output from running the above program with the first hundred primes greater than 3 is shown here.