Nicolae's function

Putting $n=1$ we have $f(m) = f(m) + f(1) + kf(1)$ , and hence $(k+1)f(1)=0$ . There are two cases to consider:

1. If $k=-1$ , note that, for any prime $p$ , $f(p^a) = f(p^{a-1}) + f(p) - f(p) = f(p^{a-1}) \qquad a \ge 2$ Thus we deduce that $f(p^a) = f(p)$ for any prime $p$ and any $a \ge 1$ . Since $f(mn) = f(m) + f(n) - f(1) \qquad (m,n) = 1$ we deduce that $f\big(p_1^{a_1}p_2^{a_2} \cdots p_N^{a_N}\big) = f(p_1) + \cdots + f(p_N) - (N-1)f(1)$ for distinct primes $p_1,p_2,\ldots,p_N$ and $a_1,a_2,\ldots,a_N \ge 1$ . It is easy to check that this formula provides an acceptable definition of a function $f$ with the required property for any choice of integers $f(1)$ and $f(p)$ for each prime $p$ . There is no problem choosing $f(3),f(5),f(1)$ so that $f(135) = f(3^35) = f(3) + f(5) - f(1) = 3$ , and so $k=-1$ is a possible solution. A concrete example of $f$ in this case would have $f(p)=2$ for all primes $p$ , and $f(1)=1$ . In this case $f(n) = N_n + 1$ , where $N_n$ is the number of distinct prime factors in $n$ .

2. If $k \neq -1$ then $f(1)=0$ , and hence $f(mn) = f(m) + f(n)$ whenever $(m,n)=1$ , so that $f$ is multiplicative. Since $f(p^a) \; = \; f(p^{a-1}) + f(p) + kf(p) \; = \; f(p^{a-1}) + (k+1)f(p)$ whenever $a \ge 2$ and $p\ge 1$ we deduce that $f(p^a) \; = \; \big[(a-1)(k+1) + 1\big]f(p) \; = \; \big[a(k+1) - k\big]f(p)$ whenever $a \ge 1$ and $p\ge 1$ . But then $\begin{array}{rcl} f(p^4) & = & f(p^2) + f(p^2) + kf(p^2) = (k+2)f(p^2) \\ (3k+4)f(p) & = & (k+2)^2f(p) \\ (k^2+k)f(p) &=& 0 \end{array}$ for any $p\ge1$ . If $k \neq 0$ then $f(p)=0$ for all $p\ge 1$ , and so $f(135) \neq 3$ . Hence we deduce that $k=0$ , and hence that $f(p^a) \; = \; af(p) \qquad a \ge 1 \;,\; p \mbox{ prime}$ but then $f\big(p_1^{a_1} p_2^{a_2}\cdots p_N^{a_n}\big) \; = \; \sum_{j=1}^N a_jf(p_j)$ for distinct primes $p_1,p_2,\ldots,p_N$ and $a_1,a_2,\ldots,a_N \ge 1$ . Again it is easy to check that this last formula defines an acceptable function $f$ for any choice of integers $f(p)$ for any prime $p$ . There is no problem finding integers $f(3)$ and $f(5)$ so that $f(135) = 3f(3) + f(5) = 3$ , and hence $k=0$ is the only other acceptable value of $k$ . A concrete example of $f$ in this case would be to have $f(3)=1$ , and $f(p)=0$ for all other primes, so that $f(n)$ is the index of $3$ in $n$ .

Thus there are only two possible values of $k$ .

$f(9) = f(3) + f(3) + k \times f(3) = (k + 2) \times f(3)$ $f(27) = f(3) + f(9) + k \times f(3) = (2k + 3) \times f(3)$ $f(81) = f(9) + f(9) + k \times f(9) = (k + 2)^2 \times f(3)$

But also: $f(81) = f(3) + f(27) + k \times f(3) = (3k + 4) \times f(3)$

So $(k + 2)^2 = 3k + 4$ , hence $k(k + 1)$ = 0, so $k = 0$ or $k = -1$ . For both values we can come up with a function that works:

$k = 0$ : $f(n)$ is the number of factors $3$ in $n$ .

$k = -1$ : $f(n)$ is $3$ when $n$ is a multiple of $3$ , and $0$ otherwise.

$m=n=1$ gives $(k+1)f(1) = 0$ .

Let $p$ be a prime.

$m = p^a, n = p$ gives $f(p^{a+1}) = f(p^a) + (1+k)f(p)$ . It is easy to see, by induction, that $f(p^n) = (n + (n-1)k)f(p)$ .

Further, let $m = n = p^2$ . We see that $f(p^4) = (2+k)f(p^2) = (2+k)^2f(p)$ .

Hence, $f(p)((2+k)^2-(4+3k)) = 0$ . Therefore, $k=-1$ , $k=0$ or $f(p) = 0$ for all $p$ .

However, $m = 27, n = 5$ gives $3 = 0 + 0 + kf(1)$ . Hence, $f(1)$ is nonzero, so $k = -1$ , which is one of the other cases. Hence, $k = 0$ or $k = -1$ .

To show that $k = 0$ and $k=-1$ both work, we can exhibit:

$k = 0$ gives $f(x) = v_2(x)$ , the index of the maximal power of $2$ dividing $x$ .

$k = -1$ gives $f(x) = 3$ if $5 \mid x$ , $0$ otherwise.

It is easy to verify that these both work.

Putting $m=n$ , $f(m^{2})=2f(m)+kf(m)=(k+2)f(m)$

Hence, $f(m^{4})=(k+2)f(m^{2})=(k+2)^{2}f(m)$ .....(1)

Again, $f(m^{4})=f(m)+f(m^{3})+kf(m)=(k+1)f(m)+f(m^{3})$

Now, $f(m^{3})=f(m)+f(m^{2})+kf(m)=(k+1)f(m)+(k+2)f(m)$

So, $f(m^{4})=2(k+1)f(m)+(k+2)f(m)$ ......(2)

From (1) and (2),we get

$(k+2)^{2}=2(k+1)+(k+2)$

or, $2(k+1)=(k+2)(k+1)$

Hence, $k+1=0$ i.e, $k=-1$ or $k+2=2$ i.e, $k=0$ Using prime decomposition, $f$ can be defined suitably for these values of $k$ .

Let $P(m,n)$ be the statement $f(mn) = f(m) + f(n) + k f(\gcd(m,n))$ .

$P(m,1) \implies f(m) = f(m) + f(1) + kf(1) \implies (k+1)f(1) = 0$ , so either $k = -1$ or $f(1) = 0$ .

• Case 1: $k = -1$

Then let $f(n) = 3$ for all $n$ . This function certainly satisfies $P$ , as $P(m,n)$ reduces to $3 = 3 + 3 + (-1)3 \implies 3 = 3$ , and it also satisfies $f(135) = 3$ . So $k = -1$ is a solution.

• Case 2: $f(1) = 0$

$P(m,m) \implies f(m^2) = f(m) + f(m) + kf(m) = (k+2)f(m)$

$P(m^2, m) \implies f(m^3) = f(m^2) + f(m) + kf(m) = (k+2)f(m) + (k+1)f(m) = (2k+3)f(m)$

$P(m^3, m) \implies f(m^4) = f(m^3) + f(m) + kf(m) = (2k+3)f(m) + (k+1)f(m) = (3k+4)f(m)$

$P(m^2, m^2) \implies f(m^4) = f(m^2) + f(m^2) + kf(m^2) = (k+2)f(m^2) = (k+2)(k+2)f(m)$

So $(3k+4)f(m) = (k+2)(k+2)f(m)$ for all $m$ . Taking $m = 135$ , we have:

$(3k+4)(3) = (k+2)(k+2)(3)$

$3k+4 = k^2 + 4k + 4$

$0 = k^2 + k = k(k+1)$

So $k = 0$ or $k = -1$ . For the latter case, we already have a solution given in Case 1.

For the former, take the function $f(3^ab) = a$ for all nonnegative integer $a$ and positive integer $b$ not divisible $3$ . Since $P(m,n)$ reduces to $f(mn) = f(m) + f(n)$ , we only have to prove our function above satisfies $P$ . But this is immediate:

Let $m = 3^ac, n = 3^bd$ , where $a,b$ are nonnegative integers and $c,d$ are positive integers not divisible by $3$ . Then,

$f(mn) = f(3^{a+b}cd) = a+b$ since $cd$ doesn't have any factor of $3$ .

$f(m) + f(n) = f(3^ac) + f(3^bd) = a+b$ by definition.

So $f(mn) = f(m) + f(n)$ , and so $P$ is satisfied by our function.

Finally, as $135 = 3^3 \cdot 5$ , we have $f(135) = f(3^3 \cdot 5) = 3$ , satisfying the condition. So this is a function we seek, and so $k=0$ gives a solution.

So the number of $k$ that gives at least one solution is $\boxed{2}$ .

Case 1: k=-1 Define f(x) as 1+ the number of DISTINCT prime factors of x that are less than x If x=1 or is prime, then f(x)=1. Note that f(135)=3 because 135=3^3*5. To address f(mn)=f(m)+f(n)-f(gcd(m,n): Let A be the set of distinct prime factors of m and B be the set of distinct prime factors of n. The set of distinct prime factors of gcd(m,n) is the set (A intersect B). The set of distinct prime factors of mn is (A union B). We know from set theory that |(A union B)| =|A|+|B|-|(A intersect B)|. Thus, 1+|(A union B)| =(1+|A|)+(1+|B|)-(1+|(A intersect B)|). 1+|(A union B)| = f(mn), 1+|A| = f(m), 1+|B| = f(n), and 1+|(A intersect B)| = f(gcd(m,n)). Substituting then yields the desired result.

Case 2: k=0 Define f(x) as the number of 3's in the prime factorization of x. (3 (the number of 5's in the prime factorization of x) would also work. 135=3^3 5, so f(135)=3. The number of 3's in the prime factorization of mn is obviously equal to the number of 3's in the prime factorization of m + the number of 3's in the prime factorization of n. Thus f(mn)=f(m)+f(n)

We have now shown that k=-1 and k=0 work. Next is to show that no other value of k works. First note that f(n^s)=(s+(s-1)k) f(n) for integer s>0. Proof by induction: for s=1, f(n^1)=f(n). Assume f(n^t)=(t+(t-1)k) f(n). f(n^(t+1))=f(n^t)+f(n)+k f(gcd(n,n^t)). gcd(n,n^t)=n. thus f(n^(t+1))=(1+k) f(n)+f(n^t). Substitute (t+(t-1)k) f(n) for f(n^t): f(n^(t+1))=(1+k+t+(t-1)k) f(n)=((t+1)+t k) f(n)

Also note that unless k=-1, f(1) must be 0. Proof: x=1 x. Thus f(x)=f(1)+f(x)+k f(gcd(1,x)). gcd(1,x)=1. f(x)=(1+k) f(1)+f(x). (1+k) f(1)=0. Thus either k=-1 or f(1)=0.

Finally, consider the following: f(125 135)=f(25)+f(135 5)+k f(25)=(1+k) f(25)+f(135 5)=(1+k)(2+k)f(5)+(1+k)f(5)+f(135)=(k^2+4k+3) f(5)+3

Alternatively: f(125 135)=f(5^3)+f(135)+k f(gcd(125,135))=(3+2k) f(5)+3+k f(5)=(3+3k)*f(5)+3

Setting the two equal to each other: (k^2+4k+3) f(5)+3=(3+3k) f(5)+3 (k^2+k) f(5)=0 k (k+1)*f(5)=0 Thus k=0 or k=-1 OR f(5)=0

Now consider f(9 135) f(9 135)=f(9)+f(135)+k f(gcd(9,135))=(1+k) f(9)+f(135)=(1+k) (2+k) f(3)+3=(k^2+3k+2)*f(3)+3

Alternatively: f(9 135)=f(3^5)+f(5)+k f(gcd(5,3^5))=(5+4k)*f(3)+f(5)+f(1) We know that f(1)=0 unless k=-1 and we've already handles the case of k=-1, so assume k is not -1. Then f(1)=0

Setting both cases equal: (k^2+3k+2) f(3)+3=(5+4k) f(3)+f(5) add f(27)=(3+2k) f(3) to both sides. (k^2+5k+5) f(3)+3=(5+4k) f(3)+f(5)+f(27) substitute 3=f(135)=f(5)+f(27) (k^2+5k+5) f(3)+3=(5+4k) f(3)+3 (k^2+k) f(3)=0 thus k=0 or k=-1 OR f(3)=0

Now we have that k=0 or k=-1 or (f(3)=f(5)=0)

Last step, I promise! Assume k is neither -1 nor 0. Then f(1)=f(3)=f(5)=0 f(135)=f(27)+f(5)+f(1)=(3+2k)*f(3)+f(5)+f(1) f(1),f(3), and f(5) are all 0 Thus f(135)=0, but f(135)=3; a contradiction. Therefore the assumption is false and k must be either 0 or -1.

Sorry it was so long, just wanted to be thorough.

Note that $135 = 3 \times 45 = 9 \times 15 = 27 \times 5 = 135 \times 1$ , and $\gcd (3,45) = \gcd (9,15) = 3, \gcd (27,5) \ gcd(135, 1) = 1$

We have

$3 = f(135) = f(3) + f(45) + k \cdot f(3)$

$3 = f(135) = f(9) + f(15) + k \cdot f(3)$

$3 = f(135) = f(27) + f(5) + k \cdot f(1)$

$3 = f(135) = f(135) + f(1) + k \cdot f(1)$

Denote integers $a,b,c,d,e,f,g$ as the values of $f(1), f(3), f(5), f(9), f(15), f(27), f(45)$ respectively, then combining the first three equations,

$3 = b + g + bk = d + e + bk = f + c + ak$

And solve the fourth equation gives $a = 0$ and/or $k = -1$

$\Rightarrow b + g = d + e$ $\space \space \space \space \space \space \space \space \space (*)$

Similarly, let $m = 3, n = 1$

$f(9) = f(3) + f(3) + k \cdot f(3)$

$\Rightarrow d = b(2+k)$ $\space \space \space \space \space \space \space \space \space (**)$

And let $m=15, n=3$

$f(45) = f(15) + f(3) + k \cdot f(3)$

$\Rightarrow g = b(k+1) + e$ $\space \space \space \space \space \space \space \space \space (***)$

Substitute $(**)$ and $(***)$ into $(*)$ :

$b + b(k+1) + e = 2(b+k) + e \Rightarrow bk = 2k \Rightarrow k = 0$ and/or $b=2$

So the possible values of $k$ are $k = 0, -1$ . Answer is $\boxed{2}$