21
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is $1$ a prime? what is $f(1)$? $\endgroup$ – Mirko Mar 11 '16 at 16:48
  • 3
    $\begingroup$ 1 is not prime... $\endgroup$ – Martigan Mar 11 '16 at 16:48
  • 1
    $\begingroup$ @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$) $\endgroup$ – vrugtehagel Mar 11 '16 at 16:50
  • 3
    $\begingroup$ @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$ $\endgroup$ – Empy2 Mar 11 '16 at 17:07
  • 3
    $\begingroup$ Is it true that $f(n)=n$ for all $n$? $\endgroup$ – Marco Disce Mar 11 '16 at 17:23
10
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ How do you determine $f(11) = f(5) + f(6)$? $\endgroup$ – Marc Mar 11 '16 at 17:03
  • $\begingroup$ Very much annoyed I didn't see this sooner. Thank you. $\endgroup$ – Cataline Mar 11 '16 at 17:05
  • 5
    $\begingroup$ 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$. $\endgroup$ – lulu Mar 11 '16 at 17:05
  • $\begingroup$ oops... (I swapped multiplication with addition) thanks for the correction ! $\endgroup$ – Fnacool Mar 11 '16 at 17:08
  • 1
    $\begingroup$ Is it possible that $f(n)\ne n$ for some $n$? $\endgroup$ – DanielWainfleet Mar 11 '16 at 20:03
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Mar 11 '16 at 20:02
  • 2
    $\begingroup$ @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) $\endgroup$ – fleablood Mar 11 '16 at 20:57
  • $\begingroup$ @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) $\endgroup$ – DanielWainfleet Mar 12 '16 at 0:29
  • $\begingroup$ Why if $n$ is prime then $n+3$ falls under case1? $2^k-3$ is never prime? $\endgroup$ – Marco Disce Mar 12 '16 at 18:33
  • $\begingroup$ @MarcoDisce good catch! I made an edit to address that case. $\endgroup$ – Nate Mar 13 '16 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.