Wednesday, April 15, 2015

Repeating Decimals

In our monetary system, different coins represent different fractions of a dollar, and most of us have memorized a few basic fraction to decimal conversions.  For example, one quarter is worth ¼ of a dollar or $0.25, so we know that ¼ = 0.25.  Similarly, one dime is worth 1/10 of a dollar or $0.10, one nickel is worth 1/20 of a dollar or $0.05, and one penny is worth 1/100 of a dollar or $0.01.  Therefore, we know that ¼ = 0.25, 1/10 = 0.1, 1/20 = 0.05, and 1/100 = 0.01.

One of the reasons these particular values were picked for coins was because the decimals for these fractions terminate, despite the fact that most fractions do not.  For example, a quarter can be represented with long division as the following:


0.
2
5
4
1.
0
0

8


2
0

2
0



0

The remainder reaches zero and so the decimal terminates, which makes for easier calculations for adding and subtracting amounts in cents.  But imagine a coin that was worth 1/3 of a dollar.  Using long division, we would get:


0.
3
3
3
3
1.
0
0
0

9




1
0




9




1
0




9





1


The remainder never reaches zero, and so the threes carry on infinitely, which is why we don’t have a coin worth 1/3 of a dollar.  In mathematical terms, the three is repeated and the decimal can be expressed as 1/3 = 0.333…

The following table shows the decimal notation of the first twenty integers as denominators with a numerator of one:

Fraction
Decimal
Repeated Part
Period
1/1
1
(terminates)
0
1/2
0.5
(terminates)
0
1/3
0.333…
3
1
1/4
0.25
(terminates)
0
1/5
0.2
(terminates)
0
1/6
0.1666…
6
1
1/7
0.142857…
142857
6
1/8
0.125
(terminates)
0
1/9
0.111…
1
1
1/10
0.1
(terminates)
0
1/11
0.090909…
09
2
1/12
0.08333…
3
1
1/13
0.076923…
076923
6
1/14
0.0714285…
714285
6
1/15
0.0666…
6
1
1/16
0.0625
(terminates)
0
1/17
0.0588235294117647…
0588235294117647
16
1/18
0.0555…
5
1
1/19
0.052631578947368421…
052631578947368421
18
1/20
0.05
(terminates)
0

There does not seem to be any pattern to the length of the repeated part of the decimal, and as we will see later that is because there is a relationship between it and prime numbers, which has no known pattern.  However, there are certain rules that can be applied.

First of all, all denominators comprised of only factors of 2 or 5 terminate.  For example, 2, 4 (22), 5, 8 (23), 10 (2∙5), 16 (24), 20 (225), and so on all terminate.  This is due to our numbering system being in base 10, which is 2 times 5.

Secondly, if the denominator is a prime number (other than 2 or 5), then the period is a factor of one less than the denominator.  For example, 7 is a prime number, and the period for 1/7 is 6, which is a factor of 7 – 1 = 6.  Also, 11 is a prime number, and the period for 1/11 is 2, which is a factor of 11 – 1 = 10.  The reasoning behind this is somewhat involved.  You may recall from your high school math class that the sum of an infinite geometric series is t1/1 – r (when |r| < 1), where t1 is the first term and r is the ratio.  This means that any repeating decimal (such as 0.090909…) can be expressed as a fraction by first rewriting it as an infinite geometric series (0.090909… = 0.09 + 0.0009 + 0.000009 + …) and then using the infinite geometric sum formula (t1/1 – r = 0.09/1 – 0.01 = 0.09/0.99 = 9/99 = 1/11).  In general, the numerator is the repeated part of the decimal and the denominator must contain a string of nines as long as the period of the decimal (before simplifying).  Since 7 has a period of 6, 7 must divide evenly into a string of 6 nines (999999 / 7 = 142857).  Since 11 has a period of 2, 11 must divide evenly into a string of 2 nines (99 / 11 = 9).  Mathematically, the string of nines n digits long can be represented as 10n – 1.  Now, Fermat’s Little Theorem states that “if p is prime and a is coprime to p, then p divides ap−1 – 1.”  So if a = 10 and p is a prime number (other than 2 or 5 so that a and p are coprime) and n = p – 1, then p must divide into 10n – 1, which matches the string of nines needed in the denominator for a repeating decimal, meaning that all prime numbers must have a period that repeats itself every p – 1 digits.  That is why the prime number 7 has a period of 6.  So why doesn’t the prime number 11 have a period of 10 instead of 2?  Technically, it does have a period of 10, but only if you include five sets of two (1/11 = 0.0909090909…).  Because of the repetition of numbers in the period of 10 itself, the final period is short-circuited to a factor of 10, in this case 2.

Third, if the denominator d has a period of one less than itself, then d is prime.  Such prime numbers are called long primes.  For example, 7 must be a long prime because it has a period of 7 – 1 = 6, 17 must be a long prime because it has a period of 17 – 1 = 16, and 19 must be a long prime because it has a period of 19 – 1 = 18.  The reason behind this is due to Lehmer’s Theorem, which states that “if there exists an a where p divides into ap - 1 – 1, but p does not divide into ap – 1/q – 1 for all primes q dividing p – 1, then p is prime.”  Because of our argument in the second point dealing with infinite geometric sums, since 7 has a period of 6, 7 cannot evenly divide into 9, 99, 999, 9999, or 99999, but finally must evenly divide into 999999.  In other words, if p = 7 and a = 10, p divides into ap - 1 – 1, but p does not divide into ap – 1/q – 1 for all primes q dividing p – 1, so by Lehmer’s Theorem p = 7 must be prime.  With the help of a computer, other long primes include 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, and so on. 

It’s pretty amazing that long primes even exist, especially with larger numbers.  If you think about it, using long division on a long prime must result in every single remainder between one and the period before being repeated (otherwise the period would be too short to be a long prime).  For example, using long division on the long prime 7 into 1 looks like the following:


0.
1
4
2
8
5
7
7
1.
0
0
0
0
0
0

7







3
0






2
8







2
0






1
4







6
0






5
6







4
0






3
5







5
0






4
9








1


The remainders are 3, 2, 6, 4, 5, and 1, which are all the numbers between 1 and 6 exactly once, before cycling through again.  That means that dividing a larger long prime number such as 983 would result in every single number between 1 and 983 appearing as a remainder exactly once before the cycle is repeated again!

The repeated part of the quotient of long primes, called cyclic numbers, also have fascinating properties.  First of all, multiplying a cyclic number by any integer less than its long prime number results in a number with the same digits in the same order.  For example, the cyclic number of the long prime 7 is 142857.  Multiplying 142857 by any integer less than 7 results in a number with the same digits in the same order:

142857 x 3 = 428571
142857 x 2 = 285714
142857 x 6 = 857142
142857 x 4 = 571428
142857 x 5 = 714285
142857 x 1 = 142857

Note that to make the diagonal number pattern, the multipliers are in the same order as the remainders of dividing 1/7 by long division.  Changing the numerator shifts the numbers of the remainders and the digits in the quotient.  So if you divide 3/7 by long division, your first remainder is 2, then 6, then 4, then 5, then 1, then 3, which is the same order of the remainders in 1/7, therefore resulting in the same order of digits in the quotient in 1/7.


0.
4
2
8
5
7
1
7
3.
0
0
0
0
0
0
2.
8







2
0






1
4







6
0






5
6







4
0






3
5







5
0






4
9







1
0







7








3


Since 1/7 x 3 = 3/7, 0.142857… x 3 = 0.428571… which means 142857 x 3 = 428571. 

A second fascinating property is that the first half of the digits of a cyclic number added to the second half of the digits results in a string of nines.  For example, for the cyclic number 142857, the first half of this number is 142 and the second half is 857.  Adding these two numbers results in:

142
+ 857
999

For another example, the cyclic number of the long prime 17 is 0588235294117647 and

05882352
+ 94117647
99999999

The reason for this also quite involved.  From our rules of repeating decimals, 1/7 = 142857/999999, and since 999999 = 106 – 1 = (103 – 1)(103 + 1) = (999)(1001), 1/7 = 142857/999999 can be rearranged to 1001/7 = 142857/999.  As mentioned above, since 7 has a period of 6, 7 cannot evenly divide into 9, 99, 999, 9999, or 99999, but finally must evenly divide into 999999.  Applying the difference of squares, 999999 = 106 – 1 = (103 – 1)(103 + 1), so 7 must evenly divide into (103 – 1)(103 + 1).  However, we already said that 7 cannot evenly divide into 999 or 103 – 1, so 7 must divide into 103 + 1, which means that 1001 divided 7 must be an integer.  Therefore, since 1001/7 = 142857/999, 142857/999 must be an integer.  Now, 142857/999 = 142000/999 + 857/999 or 142.142142142… + 0.857857857…  Since this sum must be an integer, each digit after the decimal must be 9, because 0.999… = 1, meaning the first half of the digits of this cyclic number added to the second half of the digits of this cyclic number must result in a string of nines.  (A quick proof that 0.999… = 1 is that 0.999… = (0.333…)3 = (1/3)3 = 1.)   A similar argument can be made for any cyclic number, since the period will always be even, which means the difference of squares can always be applied.

Therefore, using long division to turn fractions into decimals leads to finding fascinating properties of terminating and repeating decimals.  The period of repeating decimals do not seem to follow any sort of pattern, but certain rules can be applied, especially concerning prime numbers.  Investigating a little deeper leads to the discovery of long primes and cyclic numbers, which also have some amazing properties.

No comments:

Post a Comment