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

2 Answers 2

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
  • 6
    $\begingroup$ How do you determine $f(11) = f(5) + f(6)$? $\endgroup$
    – Marc
    Mar 11, 2016 at 17:03
  • $\begingroup$ Very much annoyed I didn't see this sooner. Thank you. $\endgroup$
    – Cataline
    Mar 11, 2016 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, 2016 at 17:05
  • $\begingroup$ oops... (I swapped multiplication with addition) thanks for the correction ! $\endgroup$
    – Fnacool
    Mar 11, 2016 at 17:08
  • 1
    $\begingroup$ Is it possible that $f(n)\ne n$ for some $n$? $\endgroup$ Mar 11, 2016 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$
5
  • $\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$ Mar 11, 2016 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, 2016 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$ Mar 12, 2016 at 0:29
  • $\begingroup$ Why if $n$ is prime then $n+3$ falls under case1? $2^k-3$ is never prime? $\endgroup$ Mar 12, 2016 at 18:33
  • $\begingroup$ @MarcoDisce good catch! I made an edit to address that case. $\endgroup$
    – Nate
    Mar 13, 2016 at 3:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .