Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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

    n/a

    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

    Dick

    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

    Dick

    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

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, now it looks ok.
     
  10. Sep 7, 2010 #9
    k thank you very much ^^
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook