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 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
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
di. Let
D be the digit
b-1.
Multiplying (1) by
bL, 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
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 divides 1 +
bL, 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
bL ≡ -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 2
L. This implies that
a
(3) ---- (b2L - 1) = d1d2d3...d2L
p
exactly -
i.e., 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).
Suppose
bL ≡ 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
dL+i =
di for all
i. But this implies that the period of
a/
p is actually
L, rather than 2
L, 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.