Proving the Length of Repeating Blocks in Decimal Expansions

[Meg D]

I have to prove that if n is any natural number then the decimal expansion of 1/n either terminates or repeats in blocks of numbers at most n-1 digits long.

for example, 1/11 = 0.0909090909... the repeating block of numbers is 09 which is 2 digits long and 2 is less than 11. 1/7 =0.142857142857142857...the repeating block of numbers is 142857 which is 6 digits long and 6 is less than 7. How do i prove that the size of the repeating block is ALWAYS less than the denominator whenever i divide by 1?

 

[robert Ihnot]

Start with Fermat's little theorem. This tells us that for prime p, we have for any residue a, the value: a^(p-1)==1 Mod p. For 7 this means we have the equation 10^6==1 Mod 7. This shows that 7 is a divisor of 999999. In this case: 999999/7 = 142857. So, with a little bit of "slight of hand we see that 1/999999 can be modified into an infinite series because 1/10^6 + 1/10^12++++ to infinity sums up as 1/10^-1= 1/999999. Thus we arrive at
1/7 = an endless repeating pattern of .142857142857...etc.

(For a prime, not 2 or 5, we see the period can be less than p-1, since in the case of 11, we have 10^2==1 Mod 11, giving a period of length 2.)

If a given M does not contain 2 or 5, we have an s such that 10^s==1 Mod M, THUS THE MINIMAL S IS THE LENGTH OF THE PERIOD. If M contains more than 1 prime, we use the Euler phi function, and phi(s) is always less than s.

 

[Meg D]

Hey Robert thanks for replying to my qustion but i am really bad at math and i don't understand what your answer is saying and i still do not understand why the repeating blocks of numbers in decimals will always be less then the denominator if divided by one.

 

[robert Ihnot]

I realize it is a very complicated answer, but the basic is you have to understand modulo arithmetic. TAke the case of 11, 10^2 = 100==1 Mod 11, tells us that we need just two decimals. Now with 7, it takes 10^6 =1,000,000 = 7 x 142857 +1 ==1 Mod 7. So that six places are necessary.

The answer for a prime, other than 5 or 2, is the number of decimals in the expression is the number of 9s necessary for the prime to evenly divide into the number. Take 13, will it divide 9? will it divide 99? 999? No, the smallest number of 9s necessary is 6, 999999/13 = 76923.

So look at Fermat's Little theorem, remember the facts about 9s and you got a good start on it.

 

[HallsofIvy]

I don't know that you have to be that deep. When you divide 1 by n, at each step in the long division, there are only n possible remainders, 0 through n-1. If at any point you get the remaider 0, that is a terminating decimal. If you do not get remainder 0, there are only n-1 possible remainder, 1 through n-1. As soon as one of them repeats, because you "bring down" a 0 just as before, divide by n, just as before, every thing repeats. So- either you have a terminating decimal or the decimal begins repeating within the first n-1 divisions. By the "pigeon hole principle", if the fraction is not a terminating decimal, you will never have to divide more than n times before you get a repeat and so the repeating block cannot have more that n-1 digits.

 

[Meg D]

Hey HallsofIvy thanks for your help! that makes more sense to me i am in a math 113 class and this was an extra credit question but we talked about the pigeon hole principle in class so i get it now thanks again. and Robert thank you too, if i were more advanced in math I'm sure i would understand your answer.

 

[robert Ihnot]

Hey HallsofIvy thanks for your help! that makes more sense to me i am in a math 113 class and this was an extra credit question but we talked about the pigeon hole principle in class so i get it now thanks again. and Robert thank you too, if i were more advanced in math I'm sure i would understand your answer.

Thanks Meg D, and I surely must agree that HallsofIvy did a really great job with that problem!