1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook