Midy's Theorem: Fractions and Decimals and Primes... Oh my!
Given any real number x and integer b > 1, one can form a "base-b expansion" of x by selecting the unique* integers cn (n = 0, 1, 2, ...) such that
x = c0 + c1b-1 + c2b-2 + . . .
where each cn is a nonnegative integer and cn < 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
---- = 0.142857142857142857...
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
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:
(1) --- = 0.d1d2d3...dL...d2L repeating...
for certain digits di
. Let D
be the digit b
Multiplying (1) by bL
, then adding the resulting equation back to (1), we have
(2) ---- (1 + bL) = d1d2d3...dL.(d1+dL+1)...(dL+d2L) repeating...
where each pair of parentheses on the righthand side
represents one digit.
Because we assume that the di
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 divide
s 1 + bL
, because by hypothesis
So we have transformed the problem into proving a congruence
in modular arithmetic
; namely, we wish to show that bL
≡ -1 (mod p
). To accomplish this, we have only one fact in our arsenal
of knowledge: that the period
in the base b
is exactly 2L
. This implies that
(3) ---- (b2L - 1) = d1d2d3...d2L
, that the LHS
of (3) is an integer, so that b2L
≡ 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 b2L
≡ +/- 1 (mod p
≡ 1 (mod p
(3) ---- (bL - 1) = d1d2d3...dL.(dL+1-d1)...(d2L-dL) repeating...
is an integer
, from which it follows that dL+i
for all i
. But this implies that the period of a
is actually L
, rather than 2L
, a contradiction!
Hence it must be true that bL
≡ -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.