Intereting Posts

Finding the shortest distance between two lines
Variation of Pythagorean triplets: $x^2+y^2 = z^3$
What is the pmf of rolling a die until obtaining three consecutive $6$s?
Integral $\int_0^1\frac{\ln\left(x+\sqrt2\right)}{\sqrt{2-x}\,\sqrt{1-x}\,\sqrt{\vphantom{1}x}}\mathrm dx$
How many ways are there to define sine and cosine?
Deriving the addition formula of $\sin u$ from a total differential equation
Interlacing stopping times
Find all the linear involutions $f: E \to E$, where $E$ is a finite-dimensional real vector space
Weakest topology with respect to which ALL linear functionals are continuous
Two ambient isotopic curve segments, one has the length and the other does not
Diagonalisable or not?
Proposition 5.21 in Atiyah-MacDonald
Show that the direct sum of a kernel of a projection and its image create the originating vector space.
Find a>1 s.t. $a^x = x$ has a unique solution
Why does $a^n – b^n$ never divide $a^n + b^n$?

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.

- Why is Binomial Probability used here?
- Given that $xyz=1$, prove that $\frac{x}{1+x^4}+\frac{y}{1+y^4}+\frac{z}{1+z^4}\le \frac{3}{2}$
- Finding a diagonal in a trapezoid given the other diagonal and three sides
- No function $f:\mathbb{Z}\rightarrow \{1, 2, 3\}$ satisfying $f(x)\ne f(y)$ for all integers $x,y$ and $|x-y|\in\{2, 3, 5\}$
- Pythagorean triples and Pell numbers.
- Prove that $\sum_{k=1}^n \frac{2k+1}{a_1+a_2+…+a_k}<4\sum_{k=1}^n\frac1{a_k}.$

- Induction proof error
- Are there arbitrarily large gaps between consecutive primes?
- Proving if $a$ is not a multiple of prime $p$, then an integer $b$ exists such that $p^b - 1$ is a multiple of $a$
- Algorithm to find solution to $ax^2 + by^2 = 1$ in a finite field
- Prove that if $a$ and $b$ are relatively prime, then $\gcd(a+b, a-b) = 1$ or $2$
- Multiplication Table with a frame and picture of equal sum
- Minimum distance to reach opposite corner
- How many pairs of numbers are there so they are the inverse of each other and they have the same decimal part?
- Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?
- Prove $\gcd(a+b,a^2+b^2)$ is $1$ or $2$ if $\gcd(a,b) = 1$

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.

- A homotopy equivalence between spaces $B\Gamma$ and $K\Gamma$ for a graph of groups on a graph $\Gamma$
- Does every Cauchy net of hyperreals converge?
- How to test whether two group presentations are isomorphic
- How many $N$ digits binary numbers can be formed where $0$ is not repeated
- Integral $\int_0^{\pi/2}\arctan^2\left(\frac{6\sin x}{3+\cos 2x}\right)\mathrm dx$
- Why is 'abuse of notation' tolerated?
- De Rham cohomology of $\mathbb{RP}^{n}$
- solve $\sin(z)=-1$ in the set of complex numbers
- How do I isolate $y$ in $y = 4y + 9$?
- Sets question, without Zorn's lemma
- Cardinality of the infinite sets
- Prove that the centralizer is a normal subgroup.
- If $X$ is linearly independent, then $T(X)$ is also linearly independent?
- Does $G\oplus G \cong H\oplus H$ imply $G\cong H$ in general?
- Application of the Hahn- Banach theorem