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

It looks harmsless enough

  1. Nov 15, 2005 #1

    benorin

    User Avatar
    Homework Helper

    Prove that every prime other that 2 and 5 divides infinitely many of the numbers 1, 11, 111, 1111, 11111, 111111, ...

    THIS IS NOT A HOME WORK PROBLEM! So don't hold back, just put 'em out there.
     
  2. jcsd
  3. Nov 15, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Homework or no, you're only a couple getting hints for now :smile:

    If you get one of them divisible by p, you can use it to produce infinitely many.

    Consider the term with p*(p-1) 1's in it. (This won't be the first one on the list, but it's the first one I thought of how to prove is divisible by p without much effort)
     
  4. Nov 15, 2005 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Silly me, here's a much simpler way- the nth term in your sequence is just [tex]\frac{10^n-1}{9}[/tex]
     
  5. Nov 15, 2005 #4

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    then what? little fermat? (with n = p-1)
     
  6. Nov 16, 2005 #5

    benorin

    User Avatar
    Homework Helper

    I love you guys!
     
  7. Nov 16, 2005 #6
    Suppose p is a prime that is not 2 nor 5.
    A = {1, 11, 111, ...} is an infinite set.
    Let B = {1 mod p, 11 mod p, 111 mod p , ...}.
    B is a finite set.
    Let f : A -> B be the natural function mapping each element of A to an element of B.
    Since A is infinite and B is finite, there exist x > y in A such that f(x) = f(y). (Pigeon hole's principle)
    Then p must divide x - y.
    For example, if x is 1111111 and y is 111, then x-y is 1111*1000, so p divides 1111, because 1000 is relatively prime to p.

    conclusion: p divides at least one element of A.
     
  8. Nov 16, 2005 #7
    For a more stronger conclusion, let m denote 111. we denote mm = 111111, mmm = 111111111, etc.

    A = {m, mm, mmm, ...} is an infinite set.
    Let B = {m mod p, mm mod p, mmm mod p , ...}.
    B is a finite set.
    Let f : A -> B be the natural function mapping each element of A to an element of B.
    Since A is infinite and B is finite, there exist x > y in A such that f(x) = f(y). (Pigeon hole's principle)
    Then p must divide x - y.
    For example, if x is mmmmmmm and y is mmm, then x-y is mmmm*1000000000, so p divides mmmm, because 1000000000 is relatively prime to p.

    conclusion: p divides a number of the form mmm...mm. But mmm...mm is of the form 111...11 and is greater than m = 111. Therefore p divdes a number in A greater than 111.

    general conclusion: p divides a number in A greater than any given number.

    the general conclusion means that p divides infinitely many numbers in A.
     
  9. Nov 16, 2005 #8
    The only proof needed, is that if x is a prime number that is not equal to 2 or 5, b is not a finite number.

    10/x = b

    If b would be a finite number, with d number of digits, when multiplied by [tex]10^{d-1}[\tex] the result would be an integrer. Since b = 10/x, this means that [tex]\frac_{10^{d-1}(10)}{b}[\tex] would be an integrer wich imply the fact that 10^d-1 can be devided by x. Since a power has the same factors than its roots, this is impossible and thus 10/x cannot give a finite awnser. Each of these number (1,11,111...) is equal to the sum of consecutive powers of 10, such as 111 = 10^0 + 10^1 + 10^2. If devided by x, the result will be equal to the sum 10^0/x + 10^1/x + 10^2/x. By the same kind of proof, the result has to be infinite.
     
  10. Nov 16, 2005 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    It seems like you're trying to show you never get an integer and therefore prove these numbers are never divisible by primes? This is obviously false.

    Knowing each of the terms 10^0/x, 10^1/x, 10^2/x is a non-terminating decimal (<-this is the terminology, not "infinite") does not tell you their sum is a non-terminating decimal, just take x=3 for a counterexample.
     
  11. Nov 16, 2005 #10
    Alright, thanks, you made realize the exeptions. To develop on that, It would be better to proove that if a and b have no common factor, the result of a/b, let say c is non-terminating, to the exeption of a = 2, 5 and b = 2, 5
    a/b = c
    If c is terminating, with d number of digits, it would mean
    10^d-1 a/b is an integrer
    which means that 10^d-1 has b as one of its factors. Since a power has the same factors than its roots, and 10 = 5*2, this is not possible. Thus a/b cannot be an integrer.
    Taking the case of the set {1, 11, 111...}
    Each one of this number is equal to 1 + 10^1 + 10^2...10^n and thus equal to
    [tex]\frac{10^n-1}{9}[/tex]
    Thus, if devided by a, the result is
    [tex]\frac{10^n-1}{9a}[/tex]
    Since a is prime, in order for this to be terminated is that [tex]\frac{10^n-1}{9}[/tex] has a as one of its factor. So The numbers that do exeptions to the rule are the numbers that satisfy this condition.
     
    Last edited: Nov 16, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: It looks harmsless enough
  1. Looking for a (Replies: 2)

  2. Looking for a formula (Replies: 6)

  3. Looking for a curve (Replies: 4)

Loading...