A valuation-like function $w: \mathbb{N}^{+} \rightarrow \mathbb{N}$ is a $p$-adic valuation? This question is a variant of problem 4, pg. 21, from Birkhoff and Maclane, A Survey of Modern Algebra. 

Given a function $w: \mathbb{N}^+ \rightarrow \mathbb{N}$  that behaves like a valuation function, i.e., 
(1) $ w(ab) = w(a) + w(b) $
(2) $ w(a+b) \geq \min(w(a), w(b)).$
Show that it is either
  
  
*
  
*constant $0$ function, $w(a) = 0$
  or 
  
*a multiple of a $p$-adic valuation, in other words $\forall a \in \mathbb{N}^+, w(a) = k v_p(a)$ for some $p, k$ with $v_p(p^\alpha d) = \alpha $ when $(p, d) = 1 $.
  

Note that this problem is relatively simple if $w$ is defined over $\mathbb{Z}\backslash \{0\}$ instead of $\mathbb{N}^+$ which is the problem listed in the book. My question is whether the stronger statement above is also true. 
My current proof attempt is incomplete.
If $\forall a,\ w(a) = 0$ we are done. Otherwise let $n$ be the least number s.t. $w(n) \neq 0$. Easy to show from (1) that $n \neq 1$ since $w(1) = 0$ and that $n$ is prime.
By unique factorisation theorem and (1) to get the result I need only prove that for all primes $p$, $p\neq n \implies w(p) = 0$.
I tried to proceed using well founded induction. If $p \lt n$ done. Otherwise $p \gt n$. If $n \gt 2$ then $n, p$ are odd and $n+p$ is even hence $n+p=2q$. Now $n \nmid p$ so $n \nmid n + p$. If $n \gt 2$ we have $n \nmid q$. Since $q \lt p$ the induction hypothesis gives us $w(q) = 0$ and since $n \gt 2$, $w(2) = 0$. Thus $w(n+p) = w(2q) = w(2) + w(q) = 0 \ge \min(w(n), w(p))$. This gives us that $w(p) = 0$. 
I can't see how to solve the $n=2$ case. Is the case where $n=2$ solvable or is there a counterexample? 
Some perhaps useful facts. 
If $w(2) \neq 0$ and any other $w(p')=0$ for $p'$ prime, $p'\neq 2$ then $w(p) =0$ for all primes $p\neq2$. Easy to prove since every prime $p$ is an even multiple less than some power $r$ of $p'$ and by (1) $w(p^r) = 0$ and then by (2) $w(p) = 0$.
It can't be the case that $w$ behaves identically on all primes, i.e. $w(p) = k$ for all primes $p$ since it is easy to compute counterexamples, e.g. $2^2*5^2 + 3^5 = 7^3$ that will contradict (2).
Thus it must be distinct at some two primes $p_1, p_2$. This gives two distinct relatively prime numbers where w is equal, $ p_1^{w(p_2)} $ and $p_2^{w(p_1)}$. I hoped that this would lead to a contradiction but haven't found a way forward yet.
 A: Let $w$ be as in the question, and assume it is nonzero for two distinct primes. As already mentioned by user33433 in the comments, this implies $w(n)>0$ for all $n>1$, since every sufficiently large number is a positive linear combination of the two primes. We can in fact use a similar argument to estimate the rate of growth of $w$:
Lemma 1: If $a,b>1$ are coprime and $n>1$, then
$$\frac{\log n}{w(n)}\le\frac{\log a}{w(a)}+\frac{\log b}{w(b)}.$$
Proof:
Let $k$ be a large integer, and $l=\lceil k(w(b)\log a+w(a)\log b)/\log n\rceil$. Since $a^{w(b)k}$ and $b^{w(a)k}$ are coprime, and $n^l\ge a^{w(b)k}b^{w(a)k}$, there are $u,v\ge0$ such that $n^l=ua^{w(b)k}+vb^{w(a)k}$, thus
$$\left(1+\frac{k(w(b)\log a+w(a)\log b)}{\log n}\right)w(n)>w(n^l)\ge \min\{w(a^{w(b)k}),w(b^{w(a)k})\}=kw(a)w(b).$$
Multiplying by $(\log n)/kw(a)w(b)w(n)$, we obtain
$$\frac{\log n}{kw(a)w(b)}+\frac{\log a}{w(a)}+\frac{\log b}{w(b)}>\frac{\log n}{w(n)}.$$
The lemma follows by letting $k$ go to infinity. QED
Consequently, $c:=\sup\{(\log n)/w(n):n>1\}$ is finite (and positive), we have
$$w(n)\ge\frac{\log n}c$$
for every $n$, and
$$w(p)\le\frac{2\log p}c$$
for all but possibly one prime $p$.
This is about as far as I got. The problem seems rather difficult to me, and it seems to be connected more to additive number theory (such as the Waring–Goldbach problem) than to valuation theory. As a case in point, let $\alpha>1$ be a real constant, and define
$$w_\alpha(p)=\lceil\alpha\log p\rceil$$
for all primes $p$, extended to $\mathbb N^+$ using (1). Note that $\alpha\log n\le w_\alpha(n)\le\alpha\log n+\Omega(n)$ for every $n$, where $\Omega(n)\le\log_2n$ is the number of prime divisors of $n$. Does $w_\alpha$ satisfy (2)? Unlikely, because one can presumably find a prime $q$ that can be written as $q=a+b$, where $a,b$ are of similar magnitude, and each of them has many prime factors $p$ for which $\alpha\log p$ is not close to an integer, in which case the errors add up to get $w_\alpha(a),w_\alpha(b)>w_\alpha(q)$. However, I’m not sure how to prove this formally, and it is even more unclear how to generalize it to arbitrary $w$ of roughly logarithmic growth. I wouldn’t be surprised if a counterexample exists after all.
EDIT: The $w(n)=\lceil\alpha\log n\rceil$ example is in fact ruled out by the following additional properties. Let
\begin{align*}
\alpha_0&=\liminf_{\substack{p\to\infty\\p\text{ prime}}}\frac{w(p)}{\log p},\\
\alpha_1&=\limsup_{\substack{p\to\infty\\p\text{ prime}}}\frac{w(p)}{\log p}.
\end{align*}
Lemma 2: $w(n)\ge\alpha_0\log n$ for every $n$.
Proof: It suffices to show $w(p)/\log p\ge\alpha_0$ for every prime $p$. Let $\epsilon>0$ and $m\in\mathbb N$, we will prove that there is a prime $q\ge m$ such that
$$\frac{w(q)}{\log q}\le(1+\epsilon)\frac{w(p)}{\log p}.$$
Let $s$ be the product of all primes below $m$ distinct from $p$. Fix $k$ such that $k>3w(2)/\epsilon w(p)$, and $p^k>3s/\epsilon$. Put $a_0=p^k-s$, $a_1=p^k+s$. Then $a_0+a_1=2p^k$, hence by (2),
$$(1+\tfrac\epsilon3)\frac{w(p)}{\log p}\ge
\frac{w(2)+kw(p)}{k\log p}\ge\min\left\{\frac{w(a_0)}{k\log p},\frac{w(a_1)}{k\log p}\right\}\ge(1+\tfrac\epsilon3)^{-1}\min\left\{\frac{w(a_0)}{\log a_0},\frac{w(a_1)}{\log a_1}\right\},$$
hence
$$(1+\epsilon)\frac{w(p)}{\log p}\ge\frac{w(a_i)}{\log a_i}$$
for some $i=0,1$. Since $w(a_i)/\log a_i$ is a convex combination of the values $w(q)/\log q$ for prime divisors $q$ of $a_i$, we have
$$(1+\epsilon)\frac{w(p)}{\log p}\ge\frac{w(q)}{\log q}$$
for some $q\mid a_i$. Moreover, the choice of $a_i$ ensures that $a_i$ is coprime to $p$ and $s$, hence $q\ge m$. QED
Lemma 3: $w(p)\le\alpha_1\log p$ for all but possibly one prime $p$.
Proof:
Let $p\ne q$ be primes, $\epsilon>0$, and $m\in\mathbb N$, we will find a prime $r\ge m$ such that
$$(1+\epsilon)\frac{w(r)}{\log r}\ge\min\left\{\frac{w(p)}{\log p},\frac{w(q)}{\log q}\right\}.$$
Let $s$ be the product of primes below $m$ other than $p,q$. Choose a sufficiently large $k$, let $l$ be such that $p^k\le sq^l\le p^{k+1}$,
and consider $a=p^k$, $b=sq^l$, $n=a+b$. Note that
$$\frac{\log n}{\log p^k},\frac{\log n}{\log q^l}
\le\frac{\log n}{\log(p^k/s)}\le1+\frac{\log((p+1)s)}{k\log p-\log s}\le1+\epsilon$$
if $k$ is large enough, in which case
$$\frac{w(n)}{\log n}(1+\epsilon)\ge\min\left\{\frac{kw(p)}{k\log p},\frac{lw(q)}{l\log q}\right\}.$$
As in the proof of Lemma 2, the same inequality is then satisfied by a prime divisor $r\mid n$, which is coprime to $pqs$, hence $r\ge m$. QED
Lemmas 2 and 3 tell us that all but one $w(p)$ are sandwiched between the curves $\alpha_0\log p$ and $\alpha_1\log p$, which they both approach arbitrarily close infinitely often, hence $w(p)$ oscillates. Also, if $\lim_{p\to\infty}w(p)/\log p$ exists (i.e., $\alpha_0=\alpha_1$), we must have $w(n)=\alpha\log n+\beta v_{p_0}(n)$ for some $\alpha,\beta\ge0$ and a prime $p_0$; this function does indeed satisfy (1) and (2), but most of its values are not integers. Thus, integer-valued $w(n)$ must have $\alpha_0<\alpha_1$.
