Number Theory proof linked to decimals

In summary, rational numbers have periodic decimal expansions because there exists a natural number n such that (10^n)-1 is divisible by p.
  • #1
lugita15
1,554
15
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.
 
Physics news on Phys.org
  • #2
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 (10n -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 (10n -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)
 
  • #3
Hurkyl said:
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 (10n -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 (10n -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.
 
  • #4
lugita15 said:
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!
 
  • #5
lugita15 said:
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.
 
  • #6
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:

[tex]10^n \equiv 10^m \bmod p[/tex]. So that [tex]10^{n-m}\equiv 1 \bmod p [/tex]
 
Last edited:

1. What is Number Theory proof linked to decimals?

Number Theory is a branch of mathematics that deals with the properties and relationships of numbers. A proof linked to decimals in Number Theory is a mathematical argument that demonstrates the truth of a statement or theorem related to decimals.

2. How are decimals used in Number Theory proofs?

Decimals are used in Number Theory proofs to represent numbers with fractional values. They are often used to show the relationship between different types of numbers, such as rational and irrational numbers, or to demonstrate patterns and properties of numbers.

3. What are some common examples of Number Theory proofs involving decimals?

Some common examples of Number Theory proofs involving decimals include proving the irrationality of certain numbers, such as pi or the square root of 2, and demonstrating the divisibility patterns of decimals in repeating or terminating decimals.

4. What is the importance of Number Theory proofs linked to decimals?

Number Theory proofs linked to decimals are important because they help us understand the fundamental properties of numbers and how they relate to each other. They also provide the foundation for many other branches of mathematics, such as algebra and calculus, and have practical applications in fields such as cryptography and computer science.

5. How can I improve my understanding of Number Theory proofs linked to decimals?

To improve your understanding of Number Theory proofs linked to decimals, it is important to have a strong foundation in basic mathematical concepts and to practice solving problems and proofs. Reading textbooks and consulting with a math tutor or teacher can also be helpful in gaining a deeper understanding of this subject. Additionally, actively engaging with the material and seeking out real-world applications of Number Theory can enhance your understanding and appreciation of this field.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Linear and Abstract Algebra
Replies
8
Views
858
  • Precalculus Mathematics Homework Help
Replies
1
Views
749
  • General Math
Replies
7
Views
432
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
Replies
4
Views
607
  • Linear and Abstract Algebra
Replies
2
Views
917
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
13
Views
1K
Back
Top