Results 1 to 5 of 5

Thread: 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 $\displaystyle d$ be a divisor of $\displaystyle n$. Then $\displaystyle \frac n d$ is also a divisor of $\displaystyle n$; if both are less than $\displaystyle \sqrt n$ we have $\displaystyle 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 $\displaystyle 1 < d \leq \sqrt{n}$, otherwise perfect squares ($\displaystyle 4$, $\displaystyle 9$, $\displaystyle 16$, ...) fall short of the interval. I'll use the interval I mentioned.

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

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

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

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


    ________________________



    EDIT : actually this proof is complete, because $\displaystyle d_1$ and $\displaystyle 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; Jan 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 $\displaystyle d$ be a divisor of $\displaystyle n$. Then $\displaystyle \frac n d$ is also a divisor of $\displaystyle n$; if both are less than $\displaystyle \sqrt n$ we have $\displaystyle 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 $\displaystyle \sqrt n$ in the range (my mistake).

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

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: Mar 12th 2011, 06:16 PM
  2. Replies: 2
    Last Post: Sep 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: Apr 11th 2010, 04:52 PM
  4. Replies: 11
    Last Post: Jan 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: Oct 6th 2006, 06:48 PM

Search Tags


/mathhelpforum @mathhelpforum