Computing the period length of a decimal expansion

It is assumed that the basic facts about the length of the period of a decimal fraction are known. Here is an example how such a period length can actually be computed, even with modest means.

The example is with a prime number, p=523. In this case, it is known that the period length is a factor of p-1. For general (not necessarily prime) n the same method can be employed, but then not with n-1 but with phi(n) which in turn is n-1 if and only if n is prime. In practice, this is not recommended: in order to compute phi(n), one has to decompose n into prime factors, and if one has done that, it is easier to compute the period lengths for the factors of n separately.

The factorisation of p-1 is: 522 = 2 * 3 * 3 * 29

  1. Compute some 10i mod 523, so that as many factors of 522 as possible appear among the i:

    i 10i mod 523 equals
    7 107 mod 523 240
    14 2402 mod 523 70
    29 (702*10) mod 523 361
    58 3612 mod 523 94
    87 (361*94) mod 523 462
    174 4622 mod 523 60
    261 (462*60) mod 523 1

    This computation always ends with 1 because ap-1 mod p = 1 for all 0<a<p. If not, then either p is not a prime or you have made a mistake somewhere.

  2. Draw conclusions.

    The period length has to be a factor of 261 but none of the numbers in the list. The only factors that remain are 1, 2, 3, 6, 9, 18.

  3. Start over. Same as step 1 but this time have as many of the remaining candidates as possible appear in the list.

    (Since 18 is so small, you can take a shortcut: 109 mod 523 is neither 1 nor -1, so there is no need to compute 1018 mod 523.)

No further i with 10i mod 523 are found. Thus the answer is 261.