Midy's Theorem

Midy's Theorem: Fractions and Decimals and Primes... Oh my!

Background: Given any real number x and integer b > 1, one can form a "base-b expansion" of x by selecting the unique* integers c_n (n = 0, 1, 2, ...) such that

x = c₀ + c₁b^-1 + c₂b^-2 + . . .

where each c_n is a nonnegative integer and c_n < b for all n > 0. The case we're all familiar with is decimal expansions; binary, ternary, and hexadecimal expansions are all other examples of the same thing.

Here's something important about these objects: a real number x can be expressed as a fraction m/n (where m and n are relatively prime integers) iff for all integer bases b > 1, the base b expansion of x either (i) terminates in an infinite string of zeros; or (ii) eventually falls into a repeating cycle of digits, in which case we say that x = m/n is periodic in the base b. The block of digits that repeats is called the repetend, and its length is called the period.

Theorem: Suppose p is prime, and a is an integer such that gcd(a, p) = 1. (That is, a and p are coprime.) Suppose furthermore that b is an integer greater than or equal to 2 such that the length of the period of the repeating base-b expansion for a/p is even. Then dividing the repetend in half and adding the two halves digit-wise yields a string of the digits (b - 1).

Example: Let's use everybody's favorite base, b= 10, so that we are working with ordinary decimal expansions. Choose p=7 and a=1. Then certainly gcd(a,p)=1. And as most people remember from elementary school math, the decimal expansion of 1/7 is

                   1
                 ---- = 0.142857142857142857...
                   7

Now since this fraction's period is 6, an even number, we can apply the Theorem. This says that if we split the period in two and add the halves digit-wise, we should get a string of 9s. Lo and behold:

                        1  4  2
                      + 8  5  7
                      ----------
                        9  9  9

as desired.

Exercise: Do some more examples to convince yourself of the generality of the theorem. Try 13ths, 11ths, 29ths, etc. Check the conditions of the theorem. See if the conclusion is valid. For an added challenge, do this for several different bases b.

Proof of Theorem: Suppose a, p, and b are given satisfying the hypotheses of the theorem, and let the period of a/p be 2L, for some integer L. Thus we have, in base b:

                    a
(1)                ---  = 0.d1d2d3...dL...d2L repeating...
                    p

for certain digits d_i. Let D be the digit b-1.

Multiplying (1) by b^L, then adding the resulting equation back to (1), we have

              a
(2)          ---- (1 + bL) = d1d2d3...dL.(d1+dL+1)...(dL+d2L) repeating...
             p

where each pair of parentheses on the righthand side represents one digit.

Because we assume that the d_i are not all zero, and because of the fact (true regardless of the base b) that 0.DDDD repeating... = 1, it follows that the Theorem holds iff the lefthand side of (2) is an integer. This, in turn, will only be true if p divides 1 + b^L, because by hypothesis, gcd(a,p)=1.

So we have transformed the problem into proving a congruence in modular arithmetic; namely, we wish to show that b^L ≡ -1 (mod p). To accomplish this, we have only one fact in our arsenal of knowledge: that the period of a/p in the base b is exactly 2L. This implies that

              a
(3)          ---- (b2L - 1) = d1d2d3...d2L
             p

exactly - i.e., that the LHS of (3) is an integer, so that b^2L ≡ 1 (mod p). By the rules of modular arithmetic, we can (sort of) take the square root of each side of this conguence, implying that b^2L ≡ +/- 1 (mod p).

Suppose b^L ≡ 1 (mod p). Then

              a
(3)          ---- (bL - 1) = d1d2d3...dL.(dL+1-d1)...(d2L-dL) repeating...
             p

is an integer, from which it follows that d_L+i = d_i for all i. But this implies that the period of a/p is actually L, rather than 2L, a contradiction!

Hence it must be true that b^L ≡ -1 (mod p), and the Theorem follows. QED

Remarks: I have so far been unable to determine who exactly Midy is, or why this theorem is named for him. I have noded it under this title in consistency with MathWorld, the database of mathematical definitions maintained by Stephen Wolfram, and originally written by Eric Weisstein. (Note that I developed my proof independently; the MathWorld article contains no justification.) MathWorld, in turn, cites as a source a 1960s text by Redemacher, but until I (or someone else) track this book down, Midy's true identity shall remain a mystery.

As for the importance of Midy's Theorem, I shall say bluntly that there probably isn't any. At best, it is a number theoretical amusement, and if perchance but a single mathematically-inclined reader should come upon this node and derive one whit of pleasure from it, then its purpose will have been served.