f:[Natual No.] -> [Natual No.]
f(ab) = f(a)f(b) where a and b are co-prime
f(p+q) = f(p) + f(q) where p and q are primes

Find all possible values of f(2002).

There is no real technique as such to these. However it is often useful to see what you can deduce about f(n) for small values of n, and see if you can spot any patterns. Then you can try and prove that the patterns hold in general using induction.

So let's have a look at your example. Can we get f(1)? Well this is quite easy. Just set m = n = 1. Since 1 is coprime to itself we have f(1) = f(1)² so f(1) = 1 (because f(1) is a positive integer).

Now what about f(2)? Well this isn't quite as obvious. But let's try plugging it into the first equation. Set n = 2 and suppose m is odd. Then m and 2 are coprime so f(2m) = f(2)f(m) for every odd m. Does this help? Well yes, because we can get another expression for f(2m) in the special case where m is prime. We have f(p+p) = f(p)+f(p) so f(2p) = 2f(p). So let m = p = 3 say and our equations give f(6) = 2f(3) and f(6) = f(2)f(3). In other words 2f(3) = f(2)f(3) so f(2) = 2 since f(3) is non-zero.

So we have got f(1) = 1 and f(2) = 2.

Here we hit a bit of a snag. How can we get f(3)? We can't write 3 as the sum of two primes, and we can't use the trick we used to get f(2) because our functional equation only tells us what happens when we add two primes together, not three.

However we can get equations for f(3) in terms of f(n) for higher odd values of n. Let's do that and hope this will eventually enable us to find f(3). This is really our only sensible hope of making progress. We need to use the equation f(mn) = f(m)f(n) (for m,n coprime) at some point, but it is not really that useful for m = 2 anymore. So we really hope to build up our knowledge of f(n) for odd values of n until we can use f(mn) = f(m)f(n) where m,n are odd numbers.

Let x = f(3).

Well what is f(5)? We have f(3+2) = f(3)+f(2) so g(5) = x+2. Also f(5+2) = f(5)+f(2) so f(7) = x+4 and f(7+2) = f(7)+f(2) so f(9) = x+6.

Can we get an equation for f(11)? Well we can write 14 as the sum of two primes in two different ways because 14 = 11+3 = 7+7. So f(14) = f(11)+f(3) = f(7)+f(7) so f(11) = 2f(7) - f(3) = 2(x+4) - x = x+8.

Now f(13) is easy. We have f(11+2) = f(11)+f(2) so f(13) = x+10. Also f(13+2) = f(13)+f(2) so f(15) = x+12.

Aha! 15 = 3*5 and 3,5 are coprime so we can use our functional equation. We have f(15) = f(3)f(5). So x+12 = x(x+2) so x² + x - 12 = 0. This has solutions x = 3 and x = -4 but x = f(3) > 0 so f(3) = 3.

This is good. We have f(1) = 1, f(2) = 2 and f(3) = 3. How much further can we go? Well f(2+2) = f(2)+f(2) so f(4) = 4. And f(5) = x+2 = 5, f(6) = f(2)f(3) = 6, f(7) = x+4 = 7, f(8) = f(5)+f(3) = 8, f(9) = x+6 = 9, f(10) = f(2)f(5) = 10, f(11) = x+8 = 11, f(12) = f(2)f(6) = 12, f(13) = x+10 = 13, f(14) = f(2)f(7) = 14, f(15) = x+12 = 15.

We actually now have everything we need. f(2002) = f(2*7*11) = f(2)*f(7*11) = f(2)*f(7)*f(11) = 2*7*11 = 2002. So 2002 is the only possible value of f(2002). It certainly is a possible value because the identity function f(n) = n satisfies the functional equations.

So that answers that problem. However it is natural to be curious about whether f(n) = n is the only solution to the functional equation. I tend to suspect it is - if you have some spare time you could try to prove f(n) = n by (strong) induction on n.

Hmmm. It's reasonably easy to make the induction work assuming Goldbach's conjecture. It is all but certain Goldbach is true, so f(n) = n really is the only solution.

I had a go at proving this without Goldbach but didn't manage it. The problem is dealing with prime powers. To be honest I'm not very optimistic about the existence of an easy proof. If we could prove f(n) = n is the only solution then we would also have shown that for every non-negative integer n there exists odd r such that r 2ⁿ is expressible as the sum of two primes (otherwise it is easy to construct a different function f satisfying the functional equations - can you see how?). This is something I have no idea how to prove. Also we would have shown that for every odd prime p and non-negative integer n there exists an integer r such that r,p are coprime and 2rpⁿ is expressible as the sum of two primes. This is also something I have no idea how to do. So proving f(n) = n is the only solution is going to be far from easy.

So I wouldn't worry too much about this. The point is that your actual question (find all values of f(2002)) is much easier, because as shown above f(2002) = 2002.

Thanks for helping me. Functional eqns seems to be an interesting topic. Does anyone has other such problems for me to try out, or any websites?

Hmm, does your definition of natural numbers include 0? If so, there is also a trivial solution fº 0.

Here is one for you to try (and this is a fundamental result):
Find all functions f from nonnegative reals to the reals satisfying f(xy)=f(x)f(y), x,y reals.
Warning: You will need some analysis to jump from the rationals to the reals.

Kerwin

Try these:

http://nrich.maths.org/public/viewer.php?obj_id=3472

http://nrich.maths.org/public/viewer.php?obj_id=3471

i had a pre-interview question:

given:

f(xy)=f(x)f(y) & f(x+y)=f(x)+f(y)

prove f(x)=x is the only possible non-trivial solution, without knowing that f(x) is continuous

...i couldn't do it...

Let

f(x+y)=f(x)+f(y) (2) First off, note, as you presumably have, that if f(1) ¹ 0, then f(n)=n for integer n. For, from (1), f(1)=f²(1), therefore f(1)=1 or 0. And, from (2) f(1+n)=1+f(n), and we may proceed on induction to prove f(n)=n for all integer n.

Similarly, for integers p and q, f(p/q)=p/q, as f(q·p/q)=f(q)f(p/q), or p=q·f(p/q).

Now, for all |x| < 1, |f(x)| < R for some constant R. Thus for all |x| < 1/n, f(x) < R/n (can you see why? - think about a contradiction to get a rigorous proof). And, given a numbera it may be approximated by a rational number p/q such that p/q=a+m,where |m| < 1/q. Thus,

|f(a)-p/q|=|f(a-p/q)|=|f(m)| < R/m.

And, |f(a)-p/q|=|f(a-a+m| ³ |f(a-a|-|m|=|f(a)- a|-1/q,

So |f(a)-a| < (R+1)/q, but we haven't defined q, so we can make it as large as we want,and thus f(a)=a for all real a.

If f(1)=0 then from (1), f is identically 0.
Brad

Brad - how did you prove that |f(x)| < R for some R, for all |x| < 1?

I suppose I more or less assumed it; if there is no supremum to f(x) in (-1,1), then f(x) obviously does not equal x. And, given nothing more than what's given in the problem, I suppose that f(x) could very well have no supremum...

Brad, where did the step |f(a)-p/q|=|f(a)-a+m| come from, after which i'm afraid i got lost - i'm simply not used to following this sort of inequality-ridden argument

also, what is a supremum?

but thanks anyway

if|x| £ 1/n, then f(x) £ R/n (i).

Forgeteverything I did after this; a good deal of it is wrong (sorry).

Now define p/q=a-m, where p/q is the closest fraction to a with a denominator of q (*). Note that |m| £ 1/q,which implies, from (i), that

|f(m)| £ R/n (ii).

We know from the triangle inequality |x|-|y| £ |x+y|, that

f(a)-a|-|m| £ |f(a)-a+m|=|f(a)-p/q|, (I)

where the last step was obtained by substituting (*). But,

|f(a)-p/q|=|f(a-p/q)|=|f(m)| £ R/q (II).

Combining (I) with (II) through substitution,

|f(a)-a|-|m| £ R/q,

or

|f(a)-a|\leqR/q+|m| £ (R+1)q,

and, again, q can be any integer, and so (R+1)/q may be made arbitrarily small, from which it follows that f(a)-a = 0.
(As a side-note, entirely non-essential with regard to the proof, most of the < 's in the original could have been left that way, but it's probably easier this way.)

Again, sorry; I typed the original message sometime around 2AM over here in America, so perhaps some of my errors can be forgiven...

Brad

BTW - if you want a defintion of supremum, or almost any term for that matter, try either mathworld, and/or the Nrich thesaurus.

Yes, the question should say if f: R-> R satisfies f(x+y) = f(x)+f(y) and f(xy) = f(x)f(y) then f(x) = 0 for all x or f(x) = x for all x.

The supremum (or sup) of a set S is the least upper bound of the set - that is a number x such that every element of S is < = x and there is no x' < x that has this property. If the sup of S belongs to S then it is called the maximum of S.

Brad - you can actually prove f is bounded on [-1,1] from the given conditions - this is part of the problem. The easiest approach is actually to prove directly that f is monotone increasing. And you already know that f is the identity on the rationals (unless it is identically 0) so f must be the identity on the reals.

Can you see how to prove f is monotone increasing?

We know that f(x+y) = f(x) + f(y). Monotonically increasing means, as you know, for larger x there is a larger f(x). So we want to show that if y is positive, then f(x+y) is larger, or at least not smaller, than f(x). We know that f(x+y) = f(x) + f(y), though, and so the task is reduced to proving f(y) is non-negative when y is non-negative.

Of course!! - thankyou! it all comes together now.

That's really nice. Does such a deduction about monotoneness for x being non-negative hold for x< 0 without further work?

(and is 'monotoneness' a real word? if not, what is the noun for monotone?)

Yes - because the proof Brad's given doesn't assume x is non-negative. He's shown that if y is non-negative then f(y) > = 0. Therefore for _any_ x we have f(x+y) = f(x)+f(y) > = f(x).