User:Ling Kah Jai/Midy's theorem

In mathematics, Midy's theorem, named after French mathematician E. Midy, 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. If the period of the decimal representation of a/p is 2n, so that

${\frac {a}{p}}=0.{\overline {a_{1}a_{2}a_{3}\dots a_{n}a_{n+1}\dots a_{2n}}}$

then the digits in the second half of the repeating decimal period are the 9s complement of the corresponding digits in its first half. In other words

$a_{i}+a_{i+n}=9\,$

$a_{1}\dots a_{n}+a_{n+1}\dots a_{2n}=10^{n}-1.\,$

For example

${\frac {1}{17}}=0.{\overline {0588235294117647}}{\text{ and }}05882352+94117647=99999999.\,$

First extension of Midy's theorem

If k is any divisor 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 states that if the repeating portion of the decimal expansion of a/p is divided into blocks of length k then the sum of these blocks will be a multiple of 10^k − 1.

For example

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

has a period of 18. Dividing the repeating portion into blocks of length 6 or 3 and summing gives

$052631+578947+368421=999999$

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

Case of 1⁄49

See also: Repeating decimal

The fraction 1⁄49 is a repeating decimal with a period of 42:

1⁄49 = 0.0204081632 6530612244 8979591836 7346938775 51 (42 repeating digits)

There are 42 (note that this number is the period) positive integers which are less than 49 and coprime to 49. Multiplying 020408163265306122448979591836734693877551 by each of these integers results in a cyclic permutation of the original number:

• 020408163265306122448979591836734693877551 × 2 = 040816326530612244897959183673469387755102
• 020408163265306122448979591836734693877551 × 3 = 061224489795918367346938775510204081632653
• 020408163265306122448979591836734693877551 × 4 = 081632653061224489795918367346938775510204
• ...

The repeating number can be obtained from 02 and repetition of doubles placed at two places to the right:

02
  04
    08
      16
        32
          64
           128
             256
               512
                1024
                  2048
+                   ...
----------------------
020408163265306122448979591836734693877551...0204081632...

because 1⁄49 satisfies:

$x={\frac {1}{50}}+{\frac {2x}{100}}\,.$

Add the front and rear halves of digits together. It becomes:

 020408163265306122448
+979591836734693877551
----------------------
 999999999999999999999

Divide the number into three portions then add them together:

 02040816326530
 61224489795918
+36734693877551
---------------
 99999999999999

Divide the number into six portions then add them together:

 0204081
 6326530
 6122448
 9795918
 3673469
+3877551
--------
29999997

Case of failure: divide the number into seven portions then add them together:

 020408
 163265
 306122
 448979
 591836
 734693
+877551
--------
3142854

Note that 3142854 = 142857 + 3 × 99999 and 142857 is the repeating digits of 1⁄7.

Divide the number into pairs of digits. Add these pairs together:

02+04+08+16+32+65+30+61+22+44+89+79+59+18+36+73+46+93+87+75+51 = 990

Adding every digits of the number together becomes 189. Break this number again into digits and add again and again of course it yields 9.

The above shows that Midy's theorem, which applies for the reciprocal of a prime, is partially true for 1⁄49.

The period of the reciprocal

when the reciprocal of a prime, p (excluding 2 and 5) is expressed as repeating decimal, its period is either (p − 1) or a factor of it (see repeating decimal). For the reciprocal of a composite integer, n, the period is either Carmichael function, $\lambda (n)$ or a factor of it. In this case, n = 7² and

λ(7²) = 7 × 6

It is easy to see the explanation for derviation of Carmichael function in this case following the following rationale:

10⁶ ≡ 1 (mod 7) from Fermat's little theorem, i.e.

10⁶ − 1 ≡ 0 (mod 7) or 7 divides 999999.

Our task is to prove 49 divides 42 digits of 9, which is the number:

999999 × (10³⁶ + 10³⁰ + 10²⁴ + 10¹⁸ + 10¹² + 10⁶ + 1)

Since 999999 is divisible by 7, we have to prove that (10³⁶ + 10³⁰ + 10²⁴ + 10¹⁸ + 10¹² + 10⁶ + 1) is divisible by 7 also. We already know from Fermat's little theorem that 10⁶ ≡ 1 (mod 7), thus

(10³⁶ + 10³⁰ + 10²⁴ + 10¹⁸ + 10¹² + 10⁶ + 1) (mod 7)

≡ (1 + 1 + 1 + 1 + 1 + 1+ 1) (mod 7) ≡ 0 (mod 7)

This explains Carmichael's function for this case.

Second Extension of Midy's theorem

Obviously Midy's theorem or the first extension does not apply when the period length ℓ = 1 as this period length cannot be broken down.

In the case of 1⁄49, Midy's theorem is also true, except for block size k = 7. One could inspect the reciprocal of other composite integers coprime to 10 and deduce that Midy's theorem is also partially true for some of these composite integers.

Third Extension of Midy's theorem

(Z₁₇, *) is the multiplicative group of integer modulo 17. The cyclic subgroup generated by 10 is also Z₁₇:

{1, 10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12}

The sum of these number is 8×17, divisible by 17.

Arrange these 16 numbers into a ring in the same sequence and select numbers at any regular intervals:

1. Select every alternative numbers, starting from the first or second number, the sum of these 8 numbers is 68, which is divisible by 17;
2. Select one out of every three. It takes 3 cycles to select all the numbers;
3. Select one number out of every four. There are four starting choices / sets. The sum of each set is 34, which is divisible by 17;
4. Select one number out of every five (or 7, 9, 11, 13 or 15). It takes 5 (or 7, 9, 11, 13, or 15) cycles to select all the numbers;
5. Select one number out of every six (or 10, 14). The selected sets are the same as item 1;
6. Select one number out of every eight. There are eight couples and the sum of each couple is 17;
7. Select one number out of every 12. the selected sets are the same as item 3;

How to arrange positive integers not more than a prime number p in a ring such that if we select a series of numbers from the ring at a regular interval starting from any position, the sum of each selected series is divisible by p?

The solution is:

• First find the primitive root modulo p, say it is a.
• Then list the consecutive numbers generated by a in multiplication modulo p in a ring.

Proof based on group theory

Proof of the original theorem

The remainders in the long division of fraction 1⁄p are generated by the operation ×10 (mod p), i.e. the cyclic group , Z_p = {1, 10, 10², 10³, ... 10^ℓ-1} (mod p), where:

• ℓ is the order (and is even according to Midy's prerequisite)
• 10^ℓ ≡ 1 (mod p)
• Say ℓ⁄2 = k

First break the cyclic group into front and rear halves and arranged them in two rows. Select the first elements from both rows. They are:

• 1 from Row 1; and
• 10^k from Row 2

Now since the group is cyclic:

10^2k ≡ 10^ℓ ≡ 1 (mod p)

Fork 1

That is 10^k is its own inverse. It is further deduced that 10^k ≡ p - 1 (mod p), since (p - 1)² ≡ 1 (mod p). No other element of the cyclic group is the inverse of itself except the identity.

The sum of the two elements

= 1 + (p - 1) = p

Fork 2

10^2k ≡ 1 (mod p)

10^2k - 1 ≡ 0 (mod p)

(10^k - 1)(10^k + 1) ≡ 0 (mod p)

Since 10^k not ≡ 1 (mod p), i.e. 10^k - 1 not ≡ 0 (mod p) then

(10^k + 1) ≡ 0 (mod p)

Since 10^k (mod p) is a positive integer < p, thus the arithmetic sum [10^k (mod p) + 1] shall thus be p.

Continue

Select (i + 1)^th elements from both rows. They are

• 10ⁱ from Row 1; and
• 10^i+k from Row 2

The sum of these two elements

≡ 10ⁱ + 10^i+k

≡ 10ⁱ(1 + 10^k)

≡ 10ⁱp

≡ 0 (mod p)

Given that both elements are positive integers not more than p, the arithmetic sum shall thus be p it self. We have thus proved that the sum of any two matching elements of the two rows is always p.

When we wrap round the decimals represented by 1⁄p and add them together, it is equivalent to adding the following two fractions together:

1⁄p + p-1⁄p = p⁄p

The result is thus no other than 0.999....

Proof of first extension

The remainders in the long division of fraction 1⁄p are generated by the operation × b (mod p), i.e. the cyclic group , Z_p = {1, b, b², b³, ... b^ℓ-1} (mod p), where:

• ℓ is the order and is a multiple of k according to Midy's prerequisite, say ℓ = h k
• b^ℓ ≡ 1 (mod p)

First break the cyclic group into h blocks with each block having k elements. Arrange them in h rows. Select the first elements from all rows. They are:

• 1 from Row 1; and
• b^k from Row 2
• b^2k from Row 3
• ...
• b^(h - 1)k from Row h

Now since the group is cyclic:

$b^{hk}\equiv b^{l}\equiv 1{\pmod {p}}$

$b^{hk}-1\equiv 0{\pmod {p}}$

$(b^{k}-1)(b^{(h-1)k}+...+b^{3k}+b^{2k}+b^{k}+1)\equiv 0{\pmod {p}}$

Since $b^{k}-1\not \equiv 0{\pmod {p}}$ then

$(b^{(h-1)k}+...+b^{3k}+b^{2k}+b^{k}+1)\equiv 0{\pmod {p}}$

Select (i + 1)^th elements from all rows. They are

• bⁱ from Row 1; and
• b^i+k from Row 2 and etc

The sum of these elements

$\equiv \sum _{n=0}^{h-1}b^{i+nk}$

$\equiv b^{i}\sum _{n=0}^{h-1}b^{nk}$

$\equiv b^{i}\times 0{\pmod {p}}$

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

Thus the sum of h blocks of numbers is equivalent to:

${\frac {1}{p}}+{\frac {a_{1}}{p}}+{\frac {a_{2}}{p}}...{\frac {a_{h-1}}{p}}$

$={\frac {np}{p}}$

Where

$a_{1}\equiv b^{k}{\pmod {p}}$

$a_{2}\equiv b^{2k}{\pmod {p}}$

$a_{3}\equiv b^{3k}{\pmod {p}}$

...

$a_{h-1}\equiv b^{(h-1)k}{\pmod {p}}$

This completes the proof.

Proof of third extension

The remainders in the long division of fraction 1⁄p are generated by the operation × b (mod p), i.e. the cyclic group , Z_p = {1, b, b², b³, ... b^ℓ-1} (mod p).

If we arrange these elements into a ring and select the a series of elements at an interval counting from the first element, the selection will eventually come back to the first element, 1. That is, there exist a number h such that b^h k ≡ 1 (mod p) and this happens when h k is a multiple of ℓ or h k = n ℓ.

In this manner, the proof of the first extension can thus be applied to the third extension.