A division algorithm for converting prime reciprocals into ternary numbers

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 :

The first equation always has on the left hand side and the remainder in each equation is multiplied by to obtain the left-hand side of the next equation. The procedure halts when a remainder is obtained which is equal to . From then on, the pattern of the coefficients of the prime denominator will repeat indefinitely. In the above example a remainder of is obtained at the sixth step, and the pattern will repeat from then on, so looking at the coefficients of we conclude that the ternary representation of is 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 has the repeating cycle structure . Note that the cycle length is in the ternary representation of precisely because is the order of modulo . (The order of an integer modulo a prime is the lowest power of the integer which is congruent to mod . A well known theorem of Fermat guarantees that the order of any integer modulo a prime is at most ).

A further illustration is the computation of the ternary form of , for which the division algorithm yields

before the remainder repeats, giving the ternary representation . The cycle length for is , which is due to the fact that is the order of mod .

In general, for a prime reciprocal , the ternary cycle length will always be the order of mod , 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 primes greater than ), 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.