**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`_{0} + `c`_{1}`b`^{-1} + `c`_{2}`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 2`L`, for some integer `L`. Thus we have, in base `b`:

`a`
(1) --- = 0.`d`_{1}`d`_{2}`d`_{3}...`d`_{L}...`d`_{2L} 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 + `b`^{L}) = `d`_{1}`d`_{2}`d`_{3}...`d`_{L}.(`d`_{1}+`d`_{L+1})...(`d`_{L}+`d`_{2L}) 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 2

`L`. This implies that

`a`
(3) ---- (`b`^{2L} - 1) = `d`_{1}`d`_{2}`d`_{3}...`d`_{2L}
`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) ---- (`b`^{L} - 1) = `d`_{1}`d`_{2}`d`_{3}...`d`_{L}.(`d`_{L+1}-`d`_{1})...(`d`_{2L}-`d`_{L}) 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 2

`L`, 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.