Showing that a series of numbers has an infinite amount of composites

[basik156]

Homework Statement

Show that infinitely many of the numbers

11, 101, 1001, 10001, 100001,...

are composite

Homework Equations

The Attempt at a Solution

So by inspecting these numbers, I notice that 11, 1001, 100001 are all divisible by 11.
The numbers can be represented at 10^{n}+1
and when n=2k+1 where k is an integer, this number is divisible by 11, thus having a proper divisor less than √n and thus being composite.

So I know this, but I don't think I've really shown that the number is divisible by 11, I have just noticed this fact. I attempted a solution by induction, but something tells me there is a better way to show this.

 

[basik156]

If I were able to prove that 10^n +1 has any proper divisor less than √10^n+1 then I have shown the claim. How to do this is where I'm at a wall...

 

[Dick]

1001=10^3+1. Can you show me that has a divisor of 11 without doing the numeric factorization? Big hint: do you know how to factor a^3+b^3? Can you show x^n+1 where n is odd has a factor of x+1 without even factorizing the polynomial?

 

[basik156]

I understand your first two questions, so I think to answer the third I need to use prime factorization, which is what I am working on now

 

[Dick]

I understand your first two questions, so I think to answer the third I need to use prime factorization, which is what I am working on now

No, you don't need prime factorization. You just need know how to find a factor of some polynomial expressions. The question doesn't have anything to do with 11 being prime.

 

[basik156]

I must be missing something big because I can't seem to show that x+1 would be a factor. I do know that any polynomial that has a zero at say x=k has a factor of (x-k).
So if x^(2k+1)+1 and by inspection , when x=-1 we have -1^n +1 where n is odd so -1^n+1 always equals zero. Thus x=-1 is a zero, thus x+1 is a factor.

Have I done the job?

 

[Dick]

I must be missing something big because I can't seem to show that x+1 would be a factor. I do know that any polynomial that has a zero at say x=k has a factor of (x-k).
So if x^(2k+1)+1 and by inspection , when x=-1 we have -1^n +1 where n is odd so -1^n+1 always equals zero. Thus x=-1 is a zero, thus x+1 is a factor.

Have I done the job?

You've got that part right! Now apply that to 10^3+1, 10^5+1 etc. If x+1 is factor of x^3+1 then 10+1 is a factor of 10^3+1, right?

 

[basik156]

When I claim n is odd haven't I taken care of all of those cases?

 

[Dick]

When I claim n is odd haven't I taken care of all of those cases?

Sure, now just sum up how the whole thing works. Why did you ask "I must be missing something big because I can't seem to show that x+1 would be a factor."?

 

[basik156]

I should've erased that part before I sent that last message. Thanks so much for your guidance!