Reciprocal Cycles¶

Another easy problem with SageMath.

In [1]:
max(range(2, 1000), key=lambda d: (1/d).period())
Out[1]:
983

But let's talk about how we would write our own algorithm for calculating the period.

If $d = 2^a 5^b n$ where $n$ is coprime to 2 and 5, then the period of $\frac{1}{d}$ is the multiplicative order of 10 modulo $n$. This is the same as finding the smallest positive $k$ such that $$10^k \equiv 1 \pmod{n}$$ (Wondering why this is called multiplicative order? It has to do with the mathematical concept of groups, but you don't need to be familiar with them to apply the formula.)

Based on the definition, we can easily write a function that computes multiplicative order that is efficient enough for this problem, but it's not very efficient in general. The computation is a special case of the discrete logarithm, which has no known efficient algorithm in general.

In [2]:
def multiplicative_order(a, n):
    if n == 1:
        return 1
    
    g = 1
    for k in range(1, n):
        g *= a
        g %= n
        if g == 1:
            return k
In [3]:
def period(d):
    while d % 2 == 0:
        d //= 2
    while d % 5 == 0:
        d //= 5
    
    return multiplicative_order(10, d)

Personally, I don't feel it's immediately obvious why multiplicative order can be used to calculate these periods. Here's a deeper dive into why this works, if you're curious.

Explanation¶

As above, let $d = 2^a 5^b n$, where $n$ is coprime to 2 and 5, and consider the unit fraction $u=\frac{1}{d}$. The decimal representation of this fraction (as with any fraction) may have a fractional part with $q$ leading digits, followed by a repetend of $r$ digits.

Let's make note of a trick you probably already know: multiplying a number by 10 gives the same result as if you just moved the original number's decimal point to the right one digit (e.g. $1.25 \times 10 = 12.5$). This means that $10^q u$ has a decimal representation with only the repetend in its fractional part. If you were to then multiply it by $10^r$, the integer part would increase, but the fractional part would stay the same since it repeats every $r$ digits.

The above is important for understanding the following: $10^q 10^r u - 10^q u$ is an integer. How do we know? Because by the logic above, the fractional part of both $10^q 10^r u$ and $10^q u$ only have the repetend, so they cancel out when we subtract, leaving us with an integer. It immediately follows that $d(10^q 10^r u - 10^q u) = 10^q 10^r - 10^q$ is also an integer that has $d$ as a factor. We can express this as $$10^{q+r} \equiv 10^q \pmod{d}$$ Through the properties of modular arithmetic, we can cancel common factors of 2 and 5 in $10^{q+r}$, $10^q$, and $d$ until we end up with $$10^r \equiv 1 \pmod{n}$$ By definition, $r$ is the multiplicative order of 10 modulo $n$.

As a concrete example of the above, consider $d = 2^4 \times 5 \times 63 = 5040$. The decimal representation of $u = \frac{1}{d}$ is $0.0001(984126)$, where 984126 is the repetend. Therefore $q=4$ and $r=6$. Sure enough, $10^q 10^r u - 10^q u = 1984125$ is an integer; therefore, $10^{10} \equiv 10^4 \pmod{5040}$, and $10^6 \equiv 1 \pmod{63}$.

Relevant sequences¶

  • Periods of reciprocals: A007732

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.