Prove that a function is surjective

[bassflow]

Homework Statement

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.

Homework Equations

none

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...

 

[Dick]

Homework Statement

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.

Homework Equations

none

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...

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?

 

[bassflow]

Ok, yea that's right.

Is n = f(2n) because of the function definition that it outpours the largest distinct divisibe integer?

 

[Dick]

Ok, yea that's right.

Is n = f(2n) because of the function definition that it outpours the largest distinct divisibe integer?

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?

 

[bassflow]

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.

 

[Dick]

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.

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?