Track / Stage 4 / 186 of 340 #926 of 2444

Problem 926

AMC 12 late, AIME early

Algebra Difficulty 4.7 Prove it Brazilian Mathematical Olympiad · Brazil

Let $N$ be the natural numbers and $N' = N \setminus \{0\}$ . Find all functions $f: N' \to N$ such that $f(xy) = f(x) + f(y)$ , $f(30) = 0$ and $f(x) = 0$ for all $x \equiv 7 \pmod{10}$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

$f(30) = f(2) + f(3) + f(5) = 0$ and $f(n)$ is non-negative, so $f(2) = f(3) = f(5) = 0$ . For any positive integer $n$ not divisible by $2$ or $5$ we can find a positive integer $m$ such that $mn \equiv 7 \pmod{10}$ . But then $f(mn) = 0$ , so $f(n) = 0$ .
It is a trivial induction that $f(2^a 5^b n) = f(5^b n) = f(n)$ , so $f$ is identically zero.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.