Results 1 to 2 of 2

Math Help - Prove that p divides infinitely many numbers...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    34

    Prove that p divides infinitely many numbers...

    Let p>5 be a prime. Prove that p divides infinitely many numbers of the (base ten) form:

    1, 11, 111, 1111, 11111, 111111, ...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Let  \displaystyle a=\phi(p)=p-1 .

    Define  \displaystyle x=\sum_{i=0}^{a-1} 10^i = \underbrace{11\cdots 1}_a .

    Note  \displaystyle 9x=9\sum_{i=0}^{a-1} 10^i = 10^a-1 \equiv 0 \mod{p} , since  \displaystyle (10,p)=1 i.e.  \displaystyle p \neq 2,5 .
    Thus  \displaystyle p\neq 3 \implies x\equiv 0 \mod{p} .


    Now let  \displaystyle x_i = x\cdot 10^{i\cdot a}
    and define  \displaystyle S=\left\{\sum_{i=0}^{n} x_i | n\in\mathbb{N}\right\} .

    Observe if  \displaystyle b=\sum_{i=0}^{n} x_i \in S , then  \displaystyle b=\underbrace{11\cdots1}_{(n+1)\cdot a} .

    But  \displaystyle b=\sum_{i=0}^{n} x\cdot 10^{i\cdot a} = x\sum_{i=0}^{n}10^{i\cdot a} \equiv 0 \mod{p} since  \displaystyle x\equiv 0 \mod{p} .
    Hence  \displaystyle b\equiv 0 \mod{p} \; \forall \; b\in S .

    Since  \displaystyle S is not a finite set, we are done.
    Last edited by chiph588@; February 5th 2011 at 09:45 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prove there are infinitely many daffodil numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 16th 2011, 06:08 PM
  2. Replies: 2
    Last Post: February 5th 2011, 06:43 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 gcd(a,b) divides lcm[a,b]
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 15th 2010, 07:44 PM
  5. prove by induction 6 divides n^3 -n
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 1st 2008, 04:08 AM

Search Tags


/mathhelpforum @mathhelpforum