What is the length of the repeating period of 1/d written in base r?

[ Editor: The proposer, Claus Tondering <ct@dde.uucp>, offered two
  "reasonably evident" properties: if d divides some power of r, 1/d
  terminates and f(d,r) = 0; and f(d,r) is a divisor of d-1 (e.g.
  f(13,10) = 6 divides 12).  The second turns out to be false in
  general; see below. ]

I will characterize f(d,r) without proof.

It is best to define f(d,r) = 1 if the expansion of 1/d to base r
terminates, since you can consider it to have a period of 1 in two ways:
the last digit is a 0 or a 9, e.g. in the case of 1/4, you can consider
it equal to either 0.25000... or 0.24999..., both of which have a period
of 1.  If you insist, f(d,r) = 0 iff for every prime p such that p|d,
p|r also.  Otherwise f(d,r) is defined as below.

Characterization:

f(d,r) = e, where e is the Haupt-exponent of r mod n, where
n = max{m : m|d and (m,r)=1}, i.e. n is the product of all the prime
factors of d that are relatively prime to r, and e is the minimal
positive integer such that r^e = 1 (mod d).

[ Editor: the prime factors must be counted with their multiplicity
  (n is the largest divisor of d prime to r; e.g. f(49,10) = 42, not 6),
  and the last congruence should read r^e = 1 (mod n). ]

Some examples:

f(15,10) = 1, since n=3 and 10^1 = 1^1 = 1 (mod 3).

f(17,10) = 16, since n=17 and 10^16 = 1 (mod 17), i.e. 10 is a
primitive root mod 17.

f(10,15) = 1, since n=2 and 15^1 = 1^1 = 1 (mod 2).

f(8,16) = 1 or 0, 0 by your definition, 1 by mine since n=1 and
16^1 = 1 (mod 1).

These are your earlier examples:

f(7,10) = 6, since n=7 and 10^6 = 3^6 = 1 (mod 7), i.e. 3 is a
primitive [Editor: "primitie" in the original] root mod 7.

f(12,10) = 1, since n=3 and 10^1 = 1^1 = 1 (mod 3).

f(4,10) = 0 or 1.

f(7,16) = 3, since n=7 and 16^3 = 2^3 = 1 (mod 7).

-- Chris Long, Rutgers University

Unless I am confused about "decimal fraction base r", f(d,r) is not in
general a divisor of d-1.  For example, take d=6, r=8.  The expansion of
1/6 in base 8 is 0.125252525..., with period 2, which is not a divisor
of 6-1=5 of course.  If d and r are relatively prime, it is "reasonably
evident" (???) that f(d,r) is a divisor of phi(d).  Is this true in
general?

-- Dean Alvis <dean@ndmath.UUCP>

If

   k
  a  = 1 mod N

then it is trivially provable that k | phi(N).  Consider the group of
units (Z/NZ)* in the ring Z/NZ.  This group has order phi(N).  Now
simply apply Lagrange's theorem for finite groups.

This is a simple exercise [Editor: "exercize" in the original] in number theory and elementary field/group
theory.  Consider first the following (base 10):

  1/3  = .33333...
  1/7  = .142857142857...
  1/11 = .0909...
  1/13 = .769230769230...
  1/17 = .05882352941176470...

[ Editor: 1/13 = .076923076923... ]

The prime numbers 7, 17, etc. have maximal period length (p-1) because
10 is a primitive root of those primes.  That is to say the smallest n
for which

    n
  10  = 1 mod p

is p-1.

For a prime p, the period length of 1/p (in base a) will be the minimum
n such that

   n
  a  = 1 mod p

That is to say the period length of 1/p is the index of a mod p.

I leave the case for p not prime as an exercise [Editor: "exercize" in
the original] for the student.  It
too is simple.  (Hint: consider a subgroup of an appropriate ring.)

-- Bob Silverman <bs@faron.UUCP>

I once worked on this; found it to be a much tougher problem than I
suspected (still don't have the complete answer).  However, f(d,r) is
not necessarily a divisor of d-1.  (In base 10, 1/14 = 0.0714285714285...,
so f(14,10) = 6, which doesn't divide 13.)  What can be said is that if
d is prime, f(d,r) divides d-1.  (Proof?)  If d isn't prime...??

-- HS

There is a discussion of the case r=10 (for rational numbers c/d,
0<c<d) in Niven and Zuckerman's "An Introduction to the Theory of
Numbers" (pp. 259-260 in 3rd ed.).  I won't be a spoiler and mention the
solution, but the length of the period is completely described - those
interested can look up this reference.  It should be easy to generalize
the discussion there to arbitrary r.

-- Dean Alvis <dean@ndmath.UUCP>