# Prove that $f(1999)=1999$

A function $f$ maps from the positive integers to the positive integers, with the following properties: $$f(ab)=f(a)f(b)$$ where $a$ and $b$ are coprime, and $$f(p+q)=f(p)+f(q)$$ for all prime numbers $p$ and $q$. Prove that $f(2)=2, f(3)=3$, and $f(1999)=1999$.

It is simple enough to prove that $f(2)=2$ and $f(3)=3$, but I'm struggling with $f(1999)=1999$. I tried proving the general solution of $f(n)=n$ for all $n$ with a proof by contradiction: suppose $x$ is the smallest $x$ such that $f(x)<x$. I'm struggling find a way to show that no such $x$ exists if $x=p^m$ for $p$ a prime.

Can anyone help me finish off the $p^m$ case, or else show me another way of finding the answer? Computers and calculators are not allowed.

• is $1$ a prime? what is $f(1)$? – Mirko Mar 11 '16 at 16:48
• 1 is not prime... – Martigan Mar 11 '16 at 16:48
• @Mirko, $1$ is not prime in the usual sense, but we can easily find $f(1)$ by setting $a=b=1$ in the first property so $f(1^2)=f(1)^2$ implying $f(1)=1$ (since $f:\mathbb{N}\to\mathbb{N}$, so $f(1)\neq 0$) – vrugtehagel Mar 11 '16 at 16:50
• @vrugtehagel,$f(4)=f(2)+f(2)=4,f(12)=f(3)f(4)=4f(3)=f(5)+f(7)=3f(2)+2f(3)$, so $f(3)=3$ – Empy2 Mar 11 '16 at 17:07
• Is it true that $f(n)=n$ for all $n$? – Marco Disce Mar 11 '16 at 17:23

2002= 1999+3, both 1999 and 3 are primes, so $f(2002)=f(1999)+f(3)$.

The prime factorization of 2002 is: 2002=2*7*11*13.

Therefore

$f(2002) = f(2)f(7)f(11)f(13)$

Now $f(7) = f(5+2) = f(5)+f(2) = f(2)+f(3)+f(2) = 7$,

$f(14) = f(11)+f(3)$ but also $f(14) = f(2) f(7)=14$, therefore $f(11)=11$ (thank you @lulu for the correction).

Finally,

$f(13)=f(11)+f(2) = 13$, and we have

$$f(2002)=2002$$

It follows that $f(1999) = f(2002)-f(3)=1999$.

• How do you determine $f(11) = f(5) + f(6)$? – Marc Mar 11 '16 at 17:03
• Very much annoyed I didn't see this sooner. Thank you. – Cataline Mar 11 '16 at 17:05
• If you know $f(2)=2,f(3)=3$ then: $f(5)=5\implies f(7)=7\implies f(14)=14$ but then $14=f(14)=f(11+3)=f(11)+3\implies f(11)=11$. – lulu Mar 11 '16 at 17:05
• oops... (I swapped multiplication with addition) thanks for the correction ! – Fnacool Mar 11 '16 at 17:08
• Is it possible that $f(n)\ne n$ for some $n$? – DanielWainfleet Mar 11 '16 at 20:03

Here's a sketch of a "proof" that $f(n) = n$ for all $n$.

Let's prove it by strong induction on $n$, where the small cases are in various comments.

Case 1: $n$ is composite, not a prime power. Write $n = ab$ with $a, b$ coprime. Applying the first equation gives: $f(n) = f(a)f(b)$, which is $ab=n$ by induction.

Case 2: $n$ is prime (and large enough since we have base cases) then $n+3$ is composite and we can run the same argument as case 1 to that (without needing to know that $f(n)=n$) and see that $f(n+3) = n+3$. Now the second equation gives $f(n)=n$ as desired.

Edit: Case 2b: Marco Disce pointed out in the comments that I missed the case where $n$ is prime and $n+3$ is a power of $2$, in this case we can run the same argument as case $2$ but with $n+5$ instead of $n+3$ (they can't both be powers of 2).

Now for the remaining cases I will need a small lemma, the proof of which I will leave as an exercise to the reader:

Lemma: The Goldbach conjecture holds.

Case 3: $n = 2^k$, write $n = p+q$ for odd primes $p,q$ and use the second equation.

Case 4: $n = p^k$ for some odd $p$ and $k>1$. Write $2n = q+q'$ with $q,q'$ prime and $q' < n$. We still need to check that $f(q) = q$, but we can now apply the same argument as case 2 to see this, with the caveat that if $q' = 3$ we should instead show that $f(q+5)=q+5$ so as to avoid needing the $n$ case.

• Did I miss something? The Goldbach conjecture is a simple lemma? Although it certainly has no counter-examples below some very large number a lot bigger than 1999. – DanielWainfleet Mar 11 '16 at 20:02
• @user254665 adjust your humor meter. Nate was making a joke. f(n) = n if the Goldbach Conjecture holds. If it doesn't ... well, then it doesn't have to. (I think) – fleablood Mar 11 '16 at 20:57
• @fleablood. I knew he couldn't possibly be serious.I thought it would be easy to prove f(n)=n for all n by induction, and I ran into trouble, and saw the Goldbach Conjecture would be useful, maybe necessary, and I stopped. Do u think it would be a good one to post ? ( i mean if f(n) must be n for all n) – DanielWainfleet Mar 12 '16 at 0:29
• Why if $n$ is prime then $n+3$ falls under case1? $2^k-3$ is never prime? – Marco Disce Mar 12 '16 at 18:33
• @MarcoDisce good catch! I made an edit to address that case. – Nate Mar 13 '16 at 3:51