Results 1 to 3 of 3

Math Help - Prove prime p divides infinitely many members of 1, 11, 111, 1111...

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Prove prime p divides infinitely many members of 1, 11, 111, 1111...

    Prove that if p is prime and p > 5, then infinitely many members of the sequence 1, 11, 111, 1111, ... are divisible by p.


    I think I can do most of it. Since p > 5, I used Fermat's little theorem to show 10^(p-1) - 1 ≡ 0 mod p. Then 99...99 ≡ 0 mod p (p-1 nines), which means 11...11 ≡ 0 mod p (p-1 ones) since p > 5 so gcd(p,9) = 1.

    That shows one member of the sequence is divisible by p, but how do I go from here to show there are infinitely many?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I think the rest is indeed easy. Let m = 11...11 (p-1 ones). Suppose n = 11...11 ≡ 0 (mod p). Then 10^(p-1) * n + m ≡ 0 (mod p).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by uberbandgeek6 View Post
    Prove that if p is prime and p > 5, then infinitely many members of the sequence 1, 11, 111, 1111, ... are divisible by p.


    I think I can do most of it. Since p > 5, I used Fermat's little theorem to show 10^(p-1) - 1 ≡ 0 mod p. Then 99...99 ≡ 0 mod p (p-1 nines), which means 11...11 ≡ 0 mod p (p-1 ones) since p > 5 so gcd(p,9) = 1.

    That shows one member of the sequence is divisible by p, but how do I go from here to show there are infinitely many?
    You actually did most of it...

    Note that the numbers 9, 99, 999, ... are exactly the numbers of the form 10^k-1, where k is a positive integer.
    As you've pointed out the (p-1)th member in the sequence is divisible by p .

    But what about any k th member, where k is a multiple of p-1?

    We see that 10^k\equiv1\pmod p since p-1 divides k and so 10^k-1\equiv0\pmod p. Lastly, since (9,p)=1 we may divide by 9 to get (10^k-1)/9\equiv0\pmod p.

    It works for every prime p not equal to 2 or 5 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. phi(n) divides n-1 implies n is prime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 6th 2012, 05:09 AM
  2. Replies: 3
    Last Post: November 25th 2011, 01:52 AM
  3. Prove that ab divides c.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 3rd 2010, 09:42 AM
  4. Prove that p divides infinitely many numbers...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 04:55 PM
  5. Prove that gcd(a,b) divides lcm[a,b]
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 15th 2010, 07:44 PM

Search Tags


/mathhelpforum @mathhelpforum