Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Showing that a series of numbers has an infinite amount of composites

  1. Oct 7, 2012 #1
    1. The problem statement, all variables and given/known data

    Show that infinitely many of the numbers

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

    are composite

    2. Relevant equations



    3. 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[itex]^{n}[/itex]+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.
     
  2. jcsd
  3. Oct 7, 2012 #2
    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....
     
  4. Oct 7, 2012 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
    Last edited: Oct 7, 2012
  5. Oct 7, 2012 #4
    I understand your first two questions, so I think to answer the third I need to use prime factorization, which is what im working on now
     
  6. Oct 7, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Oct 7, 2012 #6
    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?
     
  8. Oct 7, 2012 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
    Last edited: Oct 7, 2012
  9. Oct 7, 2012 #8
    When I claim n is odd haven't I taken care of all of those cases?
     
  10. Oct 7, 2012 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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."?
     
  11. Oct 7, 2012 #10
    I should've erased that part before I sent that last message. Thanks so much for your guidance!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook