Results 1 to 8 of 8
Like Tree1Thanks
  • 1 Post By Link

Math Help - Natural divisors

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Prague
    Posts
    4

    Natural divisors

    Hi, I have recently encountered a problem I was unable to solve. I have tried everything and none of it worked.
    Please help. The problem goes like this:


    Prove that every natural odd number 'n' undividable by number 5, divides at least one of the numbers
    1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, ....... etc.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Natural divisors

    Let u(n) be 11...1 (n times)
    Let x be a natural odd number undividable by number 5. This implies x is relatively prime to any multiple of 10 because their divisors are only 5 and 2.
    Using the Pigeonhole principle - Wikipedia, the free encyclopedia there is p and q such that the remainders of x/u(p) and x/u(q) are the same so x divide a number written 11...100..0 (1's followed by 0's)
    x divide 11...1 * 10...0 and x is relatively prime to 10...0 so x must divide 11...1 using this lemma : If n|ab, and n is relatively prime to a, then n|b.
    Last edited by Link; December 3rd 2012 at 10:39 AM.
    Thanks from Randompn
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Natural divisors

    a little mistake in 2nd line : x is relatively prime to any power of 10 because their prime divisors are only 5 and 2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2012
    From
    Prague
    Posts
    4

    Re: Natural divisors

    Thank you very much. Last thing, could you please explain what 'relatively prime' means? I am a bit confused by that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Natural divisors

    a is relatively prime to b if they have no common divisor, for exemple 17 and 30. and this is equivalent to saying they have no common prime divisor.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2012
    From
    Prague
    Posts
    4

    Re: Natural divisors

    I see, thank you. =)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2012
    From
    Prague
    Posts
    4

    Re: Natural divisors

    Quote Originally Posted by Link View Post
    Using the Pigeonhole principle - Wikipedia, the free encyclopedia there is p and q such that the remainders of x/u(p) and x/u(q) are the same so x divide a number written 11...100..0 (1's followed by 0's)
    Last thing, how do you prove this part?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Natural divisors

    Sorry i meant u(p)/x and u(q)/x. Suppose u(p)>u(q) we have :

    u(p)=qx+r
    u(q)=q'x+r
    so u(p)-u(q)=(q-q')x. u(p)-u(q) is written 111...000... and x divide u(p)-u(q)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relitivly prime, unique divisors of divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 24th 2010, 09:40 AM
  2. simplify natural log times natural log
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 3rd 2010, 10:31 PM
  3. Sum of divisors of n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 03:39 PM
  4. Divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 19th 2007, 09:06 PM
  5. divisors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 27th 2005, 01:01 AM

Search Tags


/mathhelpforum @mathhelpforum