1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Don't understand the question help

  1. Sep 7, 2010 #1
    1. The problem statement, all variables and given/known data

    If n is a composite number, the n has prime factor nor exceeding sqrt(n)

    2. Relevant equations


    3. The attempt at a solution

    what did it mean by "nor exceeding sqrt(n)", is it, it must be less than sqrt(n)???
  2. jcsd
  3. Sep 7, 2010 #2
    i'd gues it meant "not"
  4. Sep 7, 2010 #3
    is it suppose to mean

    If n is a composite number, then n has prime factor not exceeding sqrt(n) ??
  5. Sep 7, 2010 #4


    User Avatar
    Science Advisor
    Homework Helper

    Yes. If p is the prime factor show p<=sqrt(n).
  6. Sep 7, 2010 #5
    can you check my proof please,

    since n is composite number, so n>3, so by fundamental theorem of arithmetic n can be written by product of primes, say [tex]pp_1p_2....p_k=n[/tex], so let [tex]p_1p_2....p_k=a\ ,\ where\ a<n[/tex] and assume [tex]p \leq a[/tex] without loss generality, so we get [tex]pa=n\ ,\ 3<p \leq a<n[/tex], so suppose [tex]p>\sqrt{n}[/tex], then [tex]a>\sqrt{n}[/tex] then [tex]ap>\sqrt{n}\sqrt{n}=n[/tex] contradiction. is it okay?

    but it seems something wrong when i assume [tex]p \leq a[/tex], because if [tex]a \leq p[/tex] we get [tex]3<a \leq p<n[/tex] and i can't conclude [tex]a>\sqrt{n}[/tex] right? help T_T
  7. Sep 7, 2010 #6


    User Avatar
    Science Advisor
    Homework Helper

    I don't why or how you want to assume p<=a. Or why the condition 3<p. Look, you got that if pa=n the either p<=sqrt(n) or a<=sqrt(n). Split into cases.
  8. Sep 7, 2010 #7
    i don't even tried/think to prove that, but thanks, thats a hint for me ;P, so I start to prove that first

    if [tex] p \leq \sqrt{n}[/tex] then it is proven, if not, suppose [tex]a>\sqrt{n}[/tex] then we have [tex]ap>\sqrt{n}\sqrt{n}=n[/tex], contradiction. then

    so If [tex] p \leq \sqrt{n}[/tex] then the question is proven,

    and If [tex]a \leq \sqrt{n}[/tex], so [tex]p_1p_2....p_k \leq \sqrt{n} [/tex] then
    [tex]p_1 \leq \sqrt{n} [/tex], then finished, is it ok now?
  9. Sep 7, 2010 #8


    User Avatar
    Science Advisor
    Homework Helper

    Yes, now it looks ok.
  10. Sep 7, 2010 #9
    k thank you very much ^^
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook