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!

Prove that a function is surjective

  1. Feb 5, 2014 #1
    1. The problem statement, all variables and given/known data

    Let PosZ = {z ∈ Z : z > 0}. Consider the function f : PosZ → PosZ dened as follows:
    • f(1) = 1
    • If z ∈ PosZ and z > 1 then f(z) is the largest integer that divides z but is distinct from z. (For
    example f(41) = 1 and f(36) = 18.)
    Prove that f is surjective.

    2. Relevant equations


    3. The attempt at a solution

    I want to try and show that for every n > 1, n= f(z) for some z. So note that for all n > 1, n = f(2n). But don't know if that makes sense or how to do that. And in the case of f(41) = 1, it's not true...
  2. jcsd
  3. Feb 5, 2014 #2


    User Avatar
    Science Advisor
    Homework Helper

    But f(2*41)=41. How does f(41)=1 make f(2n)=n not true? f(2*2)=2, f(2*3)=3, f(2*4)=4, etc. Looks pretty surjective to me. How would you prove f(2n)=n?
  4. Feb 5, 2014 #3
    Ok, yea that's right.

    Is n = f(2n) because of the function definition that it outpours the largest distinct divisibe integer?
  5. Feb 5, 2014 #4


    User Avatar
    Science Advisor
    Homework Helper

    Is "outpours" a metaphor, or a translation? Either way I don't think that's a proof. An integer d divides 2n if 2n/d is an integer. If d=n then then 2n/d=2. Suppose there were a larger value d'>n such that 2n/d' is an integer. How does 2n/d' relate to 2? Is it greater than or less than?
  6. Feb 5, 2014 #5
    Sorry I meant outputs, autocorrect on my phone is silly.

    2n/d' would be less than 2. But it can only be 1 if it's an integer in which case d' = 2n anyway. I don't see yet how this advanced the proof though.
  7. Feb 5, 2014 #6


    User Avatar
    Science Advisor
    Homework Helper

    Well, "outpours" was kind of poetic. But, it's not only advanced the proof, it finished it. So if d' is a divisor of 2n greater than n, then 2n/d' is an integer less than 2. Which means the only possibility is 1, just as you said. So there are no divisors of 2n between n and 2n. Doesn't that finish it?
    Last edited: Feb 5, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted