zschess wrote: Find all functions $ f:\mathbb{N} \rightarrow \mathbb{ N }_0 $ satisfy the following conditions: i) $ f(ab)=f(a)+f(b)-f(\gcd(a,b)), \forall a,b \in \mathbb{N} $ ii) For all primes $ p $ and natural numbers $ a $, $ f(a)\ge f(ap) \Rightarrow f(a)+f(p) \ge f(a)f(p)+1 $ Using induction in i), we get $f(p^k)=f(p)$ $\forall p$ prime. Using then $a=p$ in ii), we get $f(p)=1$ $\forall p$ prime. Back to i), we get that $\boxed{f(1)\text{ is any nonnegative integer and }f(n)=\text{ number of distinct prime divisors of }n\text{ }\forall n> 1}$, which indeed is a solution.

pco wrote: Back to i), we get that $\boxed{f(1)\text{ is any nonnegative integer and }f(n)=\text{ number of distinct prime divisors of }n\text{ }\forall n> 1}$, which indeed is a solution. Can you explain me more details of this step???

Pco, nice solution.

zschess wrote: Find all functions $ f:\mathbb{N} \rightarrow \mathbb{ N }_0 $ satisfy the following conditions: i) $ f(ab)=f(a)+f(b)-f(\gcd(a,b)), \forall a,b \in \mathbb{N} $ ii) For all primes $ p $ and natural numbers $ a $, $ f(a)\ge f(ap) \Rightarrow f(a)+f(p) \ge f(a)f(p)+1 $ Due to some questions in PM (thanks Korsgberg), here is a completed (and a little bit modified) correct [I hope] solution : Using induction in i), we get $f(p^k)=f(p)$ $\forall p$ prime. Using then $a=p$ in ii), we get $f(p)=1$ $\forall p$ prime. Back in i), we get $f(\prod_{i=1}^np_i)=n-(n-1)f(1)$ where $p_i$ are distinct prime numbers. And so $f(1)\in\{0,1\}$ in order previous RHS remains $\ge 0$ If $f(1)=0$ i) gives the result $\boxed{\text{S1 : }f(\prod_{i=1}^np_i^{n_i})=n}$ where $p_i$ are distinct prime numbers If $f(1)=1$ i) gives the result $\boxed{\text{S2 : }f(\prod_{i=1}^np_i^{n_i})=1}$ where $p_i$ are distinct prime numbers