Jump to content

User:Ling Kah Jai/Midy's theorem

From Wikipedia, the free encyclopedia

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. If the period of the decimal representation of a/p is 2n, so that

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

For example

First extension of Midy's theorem

[edit]

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[2] 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 10k − 1.

For example

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

Case of 149

[edit]

The fraction 149 is a repeating decimal with a period of 42:

149 = 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 149 satisfies:


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 17.

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 149.

The period of the reciprocal

[edit]

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, or a factor of it. In this case, n = 72 and

λ(72) = 7 × 6

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

106 ≡ 1 (mod 7) from Fermat's little theorem, i.e.
106 − 1 ≡ 0 (mod 7) or 7 divides 999999.

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

999999 × (1036 + 1030 + 1024 + 1018 + 1012 + 106 + 1)

Since 999999 is divisible by 7, we have to prove that (1036 + 1030 + 1024 + 1018 + 1012 + 106 + 1) is divisible by 7 also. We already know from Fermat's little theorem that 106 ≡ 1 (mod 7), thus

(1036 + 1030 + 1024 + 1018 + 1012 + 106 + 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

[edit]

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 149, 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

[edit]

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

{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

[edit]

Proof of the original theorem

[edit]

The remainders in the long division of fraction 1p are generated by the operation ×10 (mod p), i.e. the cyclic group , Zp = {1, 10, 102, 103, ... 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
  • 10k from Row 2

Now since the group is cyclic:

102k ≡ 10 ≡ 1 (mod p)

Fork 1

[edit]

That is 10k is its own inverse. It is further deduced that 10kp - 1 (mod p), since (p - 1)2 ≡ 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

[edit]
102k ≡ 1 (mod p)
102k - 1 ≡ 0 (mod p)
(10k - 1)(10k + 1) ≡ 0 (mod p)

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

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

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

Continue

[edit]

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

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

The sum of these two elements

≡ 10i + 10i+k
≡ 10i(1 + 10k)
≡ 10ip
≡ 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 1p and add them together, it is equivalent to adding the following two fractions together:

1p + p-1p = pp

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

Proof of first extension

[edit]

The remainders in the long division of fraction 1p are generated by the operation × b (mod p), i.e. the cyclic group , Zp = {1, b, b2, b3, ... 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
  • bk from Row 2
  • b2k from Row 3
  • ...
  • b(h - 1)k from Row h

Now since the group is cyclic:

Since then

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

  • bi from Row 1; and
  • bi+k from Row 2 and etc

The sum of these elements

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

Where

...

This completes the proof.

Proof of third extension

[edit]

The remainders in the long division of fraction 1p are generated by the operation × b (mod p), i.e. the cyclic group , Zp = {1, b, b2, b3, ... 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 bh 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.

  1. ^ A Theorem on Repeating Decimals; W. G. Leavitt; American Mathematical Monthly, Vol. 74, No. 6 (June – July, 1967) , pp. 669–673
  2. ^ Extended Midy's Theorem, Bassam Abdul-Baki, 2005