Prove 101 the Only PrimeDate: 12/14/2002 at 14:00:59 From: Omar Subject: I want to prove this In this sequence of integers, all in base 10: 101, 10101, 1010101, 101010101, 10101010101, .......,,,, etc. prove that 101 is the only prime in the sequence. Date: 12/14/2002 at 21:22:37 From: Doctor Paul Subject: Re: I want to prove this Think of 101010101 as: 1 + 10^2 + 10^4 + 10^6 + 10^8 This is the function f(x) = 1 + x^2 + x^4 + x^6 + x^8 evaluated at x = 10. If you can prove that the function f(x) is not irreducible, then you'll be on your way. Basically you need generalize this idea. You want to show that f(x) = 1 + x^2 + x^4 + x^6 + ... + x^(2*n) is always reducible whenever n is an integer greater than one. There is a pattern that should become obvious if you look at a few of the factorizations. I had a computer help me: ? factor(1+x^2) %1 = [x^2 + 1 1] ? factor(1+x^2+x^4) %2 = [x^2 - x + 1 1] [x^2 + x + 1 1] ? factor(1+x^2+x^4+x^6) %3 = [x^2 + 1 1] [x^4 + 1 1] ? factor(1+x^2+x^4+x^6+x^8) %4 = [x^4 - x^3 + x^2 - x + 1 1] [x^4 + x^3 + x^2 + x + 1 1] ? factor(1+x^2+x^4+x^6+x^8+x^10) %5 = [x^2 - x + 1 1] [x^2 + 1 1] [x^2 + x + 1 1] [x^4 - x^2 + 1 1] ? factor(1+x^2+x^4+x^6+x^8+x^10+x^12) %6 = [x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 1] [x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 1] ? factor(1+x^2+x^4+x^6+x^8+x^10+x^12+x^14) %7 = [x^2 + 1 1] [x^4 + 1 1] [x^8 + 1 1] Notice that x^2 + 1 is a factor every time we have n odd. When n is even, a different pattern occurs, but it can be generalized without much difficulty. If you plug x = 10 into each of these factorizations, you'll get nontrivial factorizations for each of the numbers in question. This shows that the only prime in the sequence is 101. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/