Results 1 to 7 of 7

Math Help - interesting question

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    interesting question

    Prove that any number of the form 111...111 (k decimal places) is divisible by an prime p, where p cannot equal 5. Thanks for the help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,386
    Thanks
    1322
    Quote Originally Posted by htata123 View Post
    Prove that any number of the form 111...111 (k decimal places) is divisible by an prime p, where p cannot equal 5. Thanks for the help.
    I'm not sure what you are trying to prove. If it is that 111...111 is divisible by any prime other than 5,that's simply not true- there exist primes larger than that number itself! And, of course, 11 and 111 are themselves prime. It is trivial to prove that such a number is not divisible by 5. What, exactly, is it that you are trying to prove?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    I'm trying to prove that a number of the form 111....111 is divisible by any prime other than 5. I admit there are prime numbers greater than 111....111 but there is also a number 111.....111 which is greater than that prime. I got this question from one of the text books on number theory but can't seem to find an answer
    Follow Math Help Forum on Facebook and Google+

  4. #4
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    May be I don't understand your question but your number 1..11 must have some prime factors (fundamental theorem of arithmetic) and any of them are different from 5 (multiples of 5 are equal to 0 or 5 modulo 10). Also for 11, the only prime which divide it is itself
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    1
    It is still not true. For example 2 is a prime number. Do you think it divides 111...111?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Maybe he wanted to say the following :

    For any prime p>5 there's a number of the form 11...1 which is divisible by p (in fact there are infinitely many)

    I'll post 2 proofs.

    1) By the pidgeon-hole principle (or Dirichlet's principle)

    Consider 1; 11; ...; <br />
\underbrace {11...1}_{p+1 {\text{ 1's}}}<br />

    Since there are p remainders when dividing by p, and we have got p+1 numbers , 2 of these numbers, at least, must be leave the same remainder, hence <br />
\underbrace {11...1}_{k{\text{ 1's}}} - \underbrace {11...1}_{j{\text{ 1's}}} = \dot p<br />
for some p+2>k>j>0

    But: <br />
\underbrace {11...1}_{k{\text{ 1's}}} - \underbrace {11...1}_{j{\text{ 1's}}} = \underbrace {11...1}_{k - j{\text{ 1's}}}\underbrace {0...0}_{j{\text{ 0's}}} = 10^j  \cdot \underbrace {11...1}_{k - j{\text{ 1's}}}<br />
thus: <br />
p\left| {\left( {10^j  \cdot \underbrace {11...1}_{k - j{\text{ 1's}}}} \right)} \right.<br />
but since 10 is coprime to p it must be that <br />
p\left| {\underbrace {11...1}_{k - j{\text{ 1's}}}} \right.<br />

    ( As a side comment, it's enough to take p numbers, the reasoning would be, if any of the given numbers is multiple of p we are done, so suppose the contrary, then we have p-1 possible remainders and p numbers... and we get a contradiction )

    2) Note that: <br />
\underbrace {11...1}_{n{\text{ 1's}}} = \tfrac{{10^n  - 1}}<br />
{9}<br />
hence <br />
p\left| {\underbrace {11...1}_{n{\text{ 1's}}}} \right.\underbrace  \Leftrightarrow _{{\text{by (H) }}p > 5 \Rightarrow p \ne 3}p\left| {\left( {10^n  - 1} \right)} \right.<br />

    Now by Fermat's Little Theorem we have: <br />
\left( {10;p} \right) = 1 \Rightarrow 10^{p - 1}  \equiv 1\left( {\bmod .p} \right)<br />
and the rest follows. In fact we have shown that, if p is a prime and <br />
p > 5 \Rightarrow p\left| {\underbrace {11...1}_{p - 1{\text{ 1's}}}} \right.<br />
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    The second proof was the proof my professor gave me. thanks for your reply.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. interesting question
    Posted in the Business Math Forum
    Replies: 1
    Last Post: September 30th 2010, 11:26 PM
  2. interesting question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 12:41 PM
  3. Interesting question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 22nd 2009, 06:02 PM
  4. Interesting Question
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 12th 2008, 05:26 PM
  5. interesting question
    Posted in the Advanced Applied Math Forum
    Replies: 7
    Last Post: October 11th 2007, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum