Results 1 to 5 of 5

Math Help - n has divisor 1<d<sqrt(n)

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    66

    Post n has divisor 1<d<sqrt(n)

    Here is the problem. Let n be a positive integer, not = 1, and not prime, prove n has a divisor d such that 1<d<sqrt(n)

    The way i began attacking this was by saying n is either even or odd. If n is even and not prime then n >= 4 and 2|any even integer and 1<2<sqrt(4). They problem im having is on the odd case there is no number like 2 that will divide all odd numbers so i dont know how to show a divisor would fall in this interval
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Let d be a divisor of n. Then \frac n d is also a divisor of n; if both are less than \sqrt n we have n = d \times \frac n d < (\sqrt n)^2=n which is clearly impossible.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    the conclusion is false.
    the case when n=9 is a counterwexample.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    As Shanks said, this is wrong, the interval should be 1 < d \leq \sqrt{n}, otherwise perfect squares ( 4, 9, 16, ...) fall short of the interval. I'll use the interval I mentioned.

    Let us conjecture that n is not prime, greater than one, and has not got any factor (divisor, whatever) d such as 1 < d \leq \sqrt{n}.

    Then, since n is not prime, it is composite and clearly has two divisors. Denote its two divisors d_1 and d_2, that is, ( d_1 d_2 = n).

    Since d_1 and d_2 are not in (1, \sqrt{n}], we must conclude that d_1 > \sqrt{n} and d_2 > \sqrt{n}. Thus we must conclude that d_1 d_2 > \sqrt{n}^2, that is, d_1 d_2 > n. However we know that d_1 d_2 = n, so there is a contradiction.

    \therefore n composite has at least one divisor in (1, \sqrt{n}]. Thus, if d is any divisor of n, 1 < d \leq \sqrt{n}.


    ________________________



    EDIT : actually this proof is complete, because d_1 and d_2 needn't be prime, and any composite number can be represented as the product of two composite numbers. Correct me if I am wrong.
    Last edited by Bacterius; January 15th 2010 at 06:14 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Bruno J. View Post
    Let d be a divisor of n. Then \frac n d is also a divisor of n; if both are less than \sqrt n we have n = d \times \frac n d < (\sqrt n)^2=n which is clearly impossible.
    Haha, oops. I didn't prove the right thing, but as Bacterius noticed we can just turn the proof around. And obviously we have to include \sqrt n in the range (my mistake).

    When n is composite it has both a divisor 1 < d_1 \leq \sqrt n and a divisor \sqrt n \leq d_2 < n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: March 12th 2011, 06:16 PM
  2. Replies: 2
    Last Post: September 22nd 2010, 02:48 PM
  3. Prove Q(\sqrt{2}+\sqrt{3})=Q(\sqrt{2},\sqrt{3})
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 11th 2010, 04:52 PM
  4. Replies: 11
    Last Post: January 6th 2008, 09:33 AM
  5. prove sqrt(3) + sqrt (5) is an irrational number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 6th 2006, 06:48 PM

Search Tags


/mathhelpforum @mathhelpforum