Number Theory proof linked to decimals

[lugita15]

I am trying to understand (I've already seen the rigorous proof in a real analysis class) why exactly rational numbers have periodic decimal expansions. I have basically boiled it down to proving a seemingly simple statement of number theory (I say seemingly because I don't know any number theory): For all prime numbers p>5, there exists a natural number n such that (10^n)-1 is divisible by p. However, I have absolutely no idea how to prove it.

I don't know anything about modulo arithmetic, so if possible please try to give me an explanation which doesn't involve it. If necessary it would be helpful if you explained any modulo arithmetic I would need.

Any help would be greatly appreciated.
Thank you in advance.

P.S. The reason why this statement is related to periodic decimal expansions is that all real numbers between 0 and 1 with periodic decimal expansions can be written as a fraction the denominator of which is a number of the form (10^n)-1. (For simplicity I'm excluding the case of decimal expansions which have an initial segment then become periodic, like .38578787878...) So in order for a/b, where a<b, to have a periodic decimal expansion, a/b must equal m/((10^n)-1) for some natural numbers m and n. In other words, (a/b)*((10^n)-1) must be a natural number for some n. Therefore, assuming that a/b is written in simplest form, ((10^n)-1)/b must be an integer for some n, and thus (10^n)-1 must be divisible by b for some n. But the question of whether a number is divisible by a composite number can be answered by considering whether the first number is divisible by each of the prime factors of the second number. Hence my question.

 

[Hurkyl]

Well, it's worth learning modular arithmetic if you find the time.

Maybe you can get by with just Fermat's Little Theorem?


A more interesting exercise might be to find a different argument that long division should either terminate or be periodic... and then see if you can reverse the argument you were trying to make!

I.E. write a proof whose outline is:
1. If long division is periodic, then (10ⁿ -1)/p must be an integer for some positive integer n
2. Long division terminates or is periodic
3. Therefore, there exists a positive integer n with (10ⁿ -1)/p.


I wonder if it's possible to use this as an alternate proof of Fermat's Little Theorem? (e.g. by using long division w.r.t. other bases)

 

[lugita15]

Well, it's worth learning modular arithmetic if you find the time.

Maybe you can get by with just Fermat's Little Theorem?A more interesting exercise might be to find a different argument that long division should either terminate or be periodic... and then see if you can reverse the argument you were trying to make!

I.E. write a proof whose outline is:
1. If long division is periodic, then (10ⁿ -1)/p must be an integer for some positive integer n
2. Long division terminates or is periodic
3. Therefore, there exists a positive integer n with (10ⁿ -1)/p.I wonder if it's possible to use this as an alternate proof of Fermat's Little Theorem? (e.g. by using long division w.r.t. other bases)

I did some reading about Fermat's little theorem, and you can't prove Fermat's Last Theorem just using this line of reasoning. Doing the proof you outlined would only prove that n exists, not that n=p-1.

Incidentally, the proof that long division terminates or becomes periodic is very simple:
If we divide a by b, where both are natural numbers, then the largest possible remainder we can get is b-1. So the total range of remainders we can get is from 0 to b-1. If the remainder becomes 0 at some step during the long division, then it terminates and we are done. So suppose the remainder never becomes zero. Then there are b-1 values the remainder can take. Thus after b-1 steps either the same remainder will have occurred twice, which means the long division repeats and we're done, or b-1 distinct values of the remainders will have occurred, so all the values for the remainder have been used. Then the very next step will have to use a remainder that's already been used, which means that the long division repeats and we are done. Q.E.D.

As I said in my original post, I already knew this proof, so I knew the statement I was trying to prove was definitely true. I was just trying to provide a proof only using reasoning about natural numbers. But know it turns out that this statement, for arbitrary bases, is just Fermat's Little theorem. So I guess if I really want to understand why rational numbers are periodic, I have to find an intuitive proof of Fermat's little theorem. This is becoming an exponentially harder problem.

Any further help would be greatly appreciated.
Thank You in Advance.

 

[CRGreathouse]

I am trying to understand (I've already seen the rigorous proof in a real analysis class) why exactly rational numbers have periodic decimal expansions.

If analysis and number theory aren't enough for you, you can try comp.sci. When dividing a/b, at each step (except possibly the first) you have a number in the range 0 to 10b - 1 'under the quotient bar', so this is really a finite-state machine. There are only 10b possible states, so by 10b digits you must either have halted (terminating decimal) or you must loop back to an earlier state. But then you must continue to loop because you're in the same state as before!

 

[Hurkyl]

I did some reading about Fermat's little theorem, and you can't prove Fermat's Last Theorem just using this line of reasoning. Doing the proof you outlined would only prove that n exists, not that n=p-1.

True -- more work is required. It can be done, though!

Incidentally, the proof that long division terminates or becomes periodic is very simple:

There are other simple ones too. The one I worked out when I was young focused entirely on the long division algorithm, and didn't make use of any arithmetic at all! (Beyond what you need to use the algorithm, of course)




I expect most proofs are going to boil down to a very weak form of the pigeonhole principle -- if you keep picking things from a finite set, you eventually have to pick one twice.

 

[robert Ihnot]

I did some reading about Fermat's little theorem, and you can't prove Fermat's Last Theorem just using this line of reasoning. Doing the proof you outlined would only prove that n exists, not that n=p-1.

It depends on how the proof starts, but you only need as much as written above.

Hurkyl: I expect most proofs are going to boil down to a very weak form of the pigeonhole principle -- if you keep picking things from a finite set, you eventually have to pick one twice.
__________________
In other words, if we look at the powers of n in 10^n modulo p, then since there are only p-1 possible choices as n increases; we must find a case such that (since for prime p division is allowed) considering n>m:

10^n \equiv 10^m \bmod p. So that 10^{n-m}\equiv 1 \bmod p