Prove 101 the Only Prime

Date: 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/