Intereting Posts

The radical of a monomial ideal is also monomial
Maximal subgroup and representations (principal part)
Does the limit $\lim _{x\to 0} \frac 1x \int_0^x \left|\cos \frac 1t \right| dt$ exists?
Prove $\lim\limits_{n\to\infty}\frac{1}{\sqrt{n!}}=0$
What kind of book would show where the inspiration for the Laplace transform came from?
Computing an awful integral
Probability Theory – Fair dice
How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$
Entropy of a natural number
Integral involving Clausen function ${\large\int}_0^{2\pi}\operatorname{Cl}_2(x)^2\,x^p\,dx$
Proving that if $G/Z(G)$ is cyclic, then $G$ is abelian
Getting better at proofs
Existence of a sequence of continuous functions convergent pointwise to the indicator function of irrational numbers
Finite Element Method for a Two-Point Problem
Isotropy over $p$-adic numbers

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.

- How find all positive $a^3=b^2+2000000$
- Uniformly distributed probability problem
- Prove that $\pi>3$ using geometry
- How do people come up with difficult math Olympiad questions?
- Irrational painting device
- Inequality with five variables

- Proving the congruence $p^{q-1}+q^{p-1} \equiv 1 \pmod{pq}$
- How are the integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ related to the parity of $n$?
- Derive a formula to find the number of trailing zeroes in $n!$
- Infinite intersection between a arbitrary set of integers and a set of floor powers
- How to prove if this equation provides an integral solution divisible by $3$?
- Fermat's last theorem fails in $\mathbb{Z}/p\mathbb Z$ for $p$ sufficiently large
- Linear Diophantine Equations in Three Variables
- Prove that neither $A$ nor $B$ is divisible by $5$
- How to prove that $z\gcd(a,b)=\gcd(za,zb)$
- How can I prove that all rational numbers are either terminating decimal or repeating decimal numerals?

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

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.

- Prove that every triangle is the orthogonal projection of an equilateral one
- Prove if $f: \rightarrow \mathbb{R}$ is integrable, then so is $|f|$ and $\left|\int_{a}^{b}f(x)dx\right| \leq \int_{a}^{b}|f(x)|dx$
- Proof: A loop is null homotopic iff it can be extended to a function of the disk
- The space $C^0(,\mathbb{R})$ of all continuous, real-valued functions on $$ is not reflexive.
- Is there a similar concept for a sigma algebra like a base for a topology?
- Parametrizing implicit algebraic curves
- Can't find the limit of the following
- Notation for: all subsets of size 2
- Fibonorial of a fractional or complex argument
- Group theory text
- Is the numerator of $\sum_{k=0}^n \frac{(-1)^k}{2k+1}\binom{n}{k}$ a power of $2$?
- How are $2\mathbb{Z}\ncong3\mathbb{Z}$ different as rings?
- About Mellin transform and harmonic series
- Write an expression for $(\cos θ + i\sin θ)^4$ using De Moivre’s Theorem.
- Using $O(n)$ to determine limits of form $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$?