Midy's theorem

Last updated October 02, 2024

In mathematics, Midy's theorem, named after French mathematician E. Midy,^[1] is a statement about the decimal expansion of fractions a/p where p is a prime and a/p has a repeating decimal expansion with an even period (sequence A028416 in the OEIS ). If the period of the decimal representation of a/p is 2n, so that

Extended Midy's theorem

If k is any divisor of h (where h is the number of digits of the period of the decimal expansion of a/p (where p is again a prime)), then Midy's theorem can be generalised as follows. The extended Midy's theorem^[2] states that if the repeating portion of the decimal expansion of a/p is divided into k-digit numbers, then their sum is a multiple of 10^k − 1.

For example,

{\frac {1}{19}}=0.{\overline {052631578947368421}}

has a period of 18. Dividing the repeating portion into 6-digit numbers and summing them gives

052631+578947+368421=999999.

Similarly, dividing the repeating portion into 3-digit numbers and summing them gives

052+631+578+947+368+421=2997=3\times 999.

Midy's theorem in other bases

Midy's theorem and its extension do not depend on special properties of the decimal expansion, but work equally well in any base b, provided we replace 10^k − 1 with b^k − 1 and carry out addition in base b.

For example, in octal

{\begin{aligned}&{\frac {1}{19}}=0.{\overline {032745}}_{8}\\[8pt]&032_{8}+745_{8}=777_{8}\\[8pt]&03_{8}+27_{8}+45_{8}=77_{8}.\end{aligned}}

In dozenal (using inverted two and three for ten and eleven, respectively)

{\begin{aligned}&{\frac {1}{19}}=0.{\overline {076{\mathcal {E}}45}}_{12}\\[8pt]&076_{12}+{\mathcal {E}}45_{12}={\mathcal {EEE}}_{12}\\[8pt]&07_{12}+6{\mathcal {E}}_{12}+45_{12}={\mathcal {EE}}_{12}\end{aligned}}

Proof of Midy's theorem

Short proofs of Midy's theorem can be given using results from group theory. However, it is also possible to prove Midy's theorem using elementary algebra and modular arithmetic:

Let p be a prime and a/p be a fraction between 0 and 1. Suppose the expansion of a/p in base b has a period of ℓ, so

{\begin{aligned}&{\frac {a}{p}}=[0.{\overline {a_{1}a_{2}\dots a_{\ell }}}]_{b}\\[6pt]&\Rightarrow {\frac {a}{p}}b^{\ell }=[a_{1}a_{2}\dots a_{\ell }.{\overline {a_{1}a_{2}\dots a_{\ell }}}]_{b}\\[6pt]&\Rightarrow {\frac {a}{p}}b^{\ell }=N+[0.{\overline {a_{1}a_{2}\dots a_{\ell }}}]_{b}=N+{\frac {a}{p}}\\[6pt]&\Rightarrow {\frac {a}{p}}={\frac {N}{b^{\ell }-1}}\end{aligned}}

where N is the integer whose expansion in base b is the string a₁a₂...a_ℓ.

Note that b^ℓ − 1 is a multiple of p because (b^ℓ − 1)a/p is an integer. Also bⁿ−1 is not a multiple of p for any value of n less than ℓ, because otherwise the repeating period of a/p in base b would be less than ℓ.

Now suppose that ℓ = hk. Then b^ℓ − 1 is a multiple of b^k − 1. (To see this, substitute x for b^k; then b^ℓ = x^h and x − 1 is a factor of x^h − 1. ) Say b^ℓ − 1 = m(b^k − 1), so

{\frac {a}{p}}={\frac {N}{m(b^{k}-1)}}.

But b^ℓ − 1 is a multiple of p; b^k − 1 is not a multiple of p (because k is less than ℓ ); and p is a prime; so m must be a multiple of p and

{\frac {am}{p}}={\frac {N}{b^{k}-1}}

is an integer. In other words,

N\equiv 0{\pmod {b^{k}-1}}.

Now split the string a₁a₂...a_ℓ into h equal parts of length k, and let these represent the integers N₀...N_h − 1 in base b, so that

{\begin{aligned}N_{h-1}&=[a_{1}\dots a_{k}]_{b}\\N_{h-2}&=[a_{k+1}\dots a_{2k}]_{b}\\&{}\ \ \vdots \\N_{0}&=[a_{l-k+1}\dots a_{l}]_{b}\end{aligned}}

To prove Midy's extended theorem in base b we must show that the sum of the h integers N_i is a multiple of b^k − 1.

Since b^k is congruent to 1 modulo b^k − 1, any power of b^k will also be congruent to 1 modulo b^k − 1. So

N=\sum _{i=0}^{h-1}N_{i}b^{ik}=\sum _{i=0}^{h-1}N_{i}(b^{k})^{i}

\Rightarrow N\equiv \sum _{i=0}^{h-1}N_{i}{\pmod {b^{k}-1}}

\Rightarrow \sum _{i=0}^{h-1}N_{i}\equiv 0{\pmod {b^{k}-1}}

which proves Midy's extended theorem in base b.

To prove the original Midy's theorem, take the special case where h = 2. Note that N₀ and N₁ are both represented by strings of k digits in base b so both satisfy

0\leq N_{i}\leq b^{k}-1.

N₀ and N₁ cannot both equal 0 (otherwise a/p = 0) and cannot both equal b^k − 1 (otherwise a/p = 1), so

0<N_{0}+N_{1}<2(b^{k}-1)

and since N₀ + N₁ is a multiple of b^k − 1, it follows that

N_{0}+N_{1}=b^{k}-1.

Corollary

From the above,

{\frac {am}{p}}

is an integer

Thus $m\equiv 0{\pmod {p}}$

And thus for $k={\frac {\ell }{2}}$

b^{\ell /2}+1\equiv 0{\pmod {p}}

For $k={\frac {\ell }{3}}$ and is an integer

b^{2\ell /3}+b^{\ell /3}+1\equiv 0{\pmod {p}}

and so on.

Notes

↑ Leavitt, William G. (June 1967). "A Theorem on Repeating Decimals". The American Mathematical Monthly. 74 (6). Mathematical Association of America: 669–673. doi:10.2307/2314251. JSTOR 2314251. MR 0211949.
↑ Bassam Abdul-Baki, Extended Midy's Theorem, 2005.

Related Research Articles

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is an integer factorization of $15$ , and $(x - 2)(x + 2)$ is a polynomial factorization of $x 2 - 4$ .

This article collects together a variety of proofs of Fermat's little theorem, which states that

Lagrange's four-square theorem, also known as Bachet's conjecture, states that every nonnegative integer can be represented as a sum of four non-negative integer squares. That is, the squares form an additive basis of order four. $where the four numbers are integers. For illustration, 3, 31, and 310 can be represented as the sum of four squares as follows:$

A hexagonal number is a figurate number. The nth hexagonal number h_n is the number of distinct dots in a pattern of dots consisting of the outlines of regular hexagons with sides up to n dots, when the hexagons are overlaid so that they share one vertex.

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. Formulas for calculating primes do exist; however, they are computationally very slow. A number of constraints are known, showing what such a "formula" can and cannot be.

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest member of the set of positive integers $m$ having the property that

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name refers to the bijection that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols.

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

A decimal representation of a non-negative real number $r$ is its expression as a sequence of symbols consisting of decimal digits traditionally written with a single separator: $Here . is the decimal separator, k is a nonnegative integer, and are digits, which are symbols representing integers in the range 0, ..., 9.$

In mathematics, an infinite periodic continued fraction is a continued fraction that can be placed in the form

A repeating decimal or recurring decimal is a decimal representation of a number whose digits are eventually periodic ; if this sequence consists only of zeros, the decimal is said to be terminating, and is not considered as repeating.

Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x⁴ ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x⁴ ≡ p to that of x⁴ ≡ q.

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

In number theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation $. If k is the smallest such exponent for x, then x is called a primitive k th root of unity modulo n . See modular arithmetic for notation and terminology.$

In algebraic number theory Eisenstein's reciprocity law is a reciprocity law that extends the law of quadratic reciprocity and the cubic reciprocity law to residues of higher powers. It is one of the earliest and simplest of the higher reciprocity laws, and is a consequence of several later and stronger reciprocity laws such as the Artin reciprocity law. It was introduced by Eisenstein, though Jacobi had previously announced a similar result for the special cases of 5th, 8th and 12th powers in 1839.

References

Rademacher, H. and Toeplitz, O. The Enjoyment of Mathematics: Selections from Mathematics for the Amateur. Princeton, NJ: Princeton University Press, pp. 158–160, 1957. MR 0081844
E. Midy, "De Quelques Propriétés des Nombres et des Fractions Décimales Périodiques". College of Nantes, France: 1836.
Ross, Kenneth A. "Repeating decimals: a period piece". Math. Mag. 83 (2010), no. 1, 33–45. MR 2598778

External links

Weisstein, Eric W. "Midy's Theorem". MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Leavitt, William G. (June 1967). "A Theorem on Repeating Decimals". The American Mathematical Monthly. 74 (6). Mathematical Association of America: 669–673. doi:10.2307/2314251. JSTOR 2314251. MR 0211949.

[2] Bassam Abdul-Baki, Extended Midy's Theorem, 2005.

[1]

[2]