I would like to know if there is a formula for f(n^k) where n is a prime number. I Think we can prove that f(ab)= f(a)f(b) when a and b are relatively prime.From here we can decompose every number in a product of powers of prime numbers and see how the funtion behaves.But i am really getting stucked here.

I showed that f(n^k) = (n-1)kn^(k-1) + n^k where n is prime and k naturel number (number of functions between two finite sets) If we can prove a), then by writing every number as a product of powers of primes and using part a) we can reach the solution of part b). For the complete proof ,many powers with indices are used and to type this am training on the Latex.

You can prove the multiplicativity easily by the chinese remainder theorem: Let $x,y$ be coprime. Then $\gcd(z,xy) = \gcd(z,x)\gcd(z,y) = \gcd(z \mod x,x)\gcd(z \mod y,y)$, and so $\gcd(r(a,b),xy))=\gcd(a,x)\gcd(b,y)$ (here $r(a,b)$ denotes the smallest natural number that fulfills $r(a,b) \equiv a \mod x,r(a,b) \equiv b \mod y$) Since in $f(xy)=\gcd(1,xy)+...+\gcd(xy,xy)$ and in $f(x)f(y) = (\gcd(1,x)+...+\gcd(x,x))(\gcd(1,y)+...+\gcd(y,y)) =$ $= \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy)$ every residue class $\mod xy$ (on the left side of the $\gcd$) occurs exactly one time, so they are identical. Now use senouy's formula to get $f(2^{2n})=(n+1)\cdot 2^{2n}$, so a) is solved Now $f(p^n)$ is only divisible by $p^n$ iff $p|n$ and then ($n=pk$) you get $\frac{f(p^n)}{p^n}=(p-1)k+1$ So if $n=sq$ with an odd prime factor $q$, set $r:=\frac{q-1}{2}$ and you will get $f(2^{2(s-1)}3^{3r})=n 2^{2(s-1)}3^{3r}$, so there are at least two solutions. Let be $n=2^s$ now. For an odd prime $p$ also $f(p^k)$ is odd, so if $d$ is odd, by multiplicativity also $f(d)$ is odd. Assume $f(2^id)=2^s \cdot 2^i d$, where $d$ is odd. Then by the formula for powers of primes and multiplicativity you get $2^{i-1}(i+2) f(d) = 2^s \cdot 2^i d \implies (i+2) f(d) = 2^{s+1} d$, but since $f(d)$ is odd, you need that $i+2 = 2^{s+1} m$ with some (odd) $m$. But this gives $m f(d) =d$, which is because of $f(x)>x$ for all $x>1$ only possible if $m=d=1$, so there is only one solution for this case. So also b) is solved.

As promised in Würzburg, I am posting my alternative solution to the problem. Problem. Let $\mathbb{N}=\left\{1;\;2;\;3;\;...\right\}$ be the set of all positive integers. Define the function $f: \mathbb{N}\to\mathbb{N}$ as follows: $f\left(n\right)=\sum_{i=1}^n\gcd\left(i;\;n\right)$. (a) Prove that the function $f$ is multiplicative. (b) Prove that for every positive integer $a$, the equation $f\left(x\right) = ax$ has a solution $x\in\mathbb{N}$. (c) Prove that, for a positive integer $a$, the equation $f\left(x\right) = ax$ has exactly one solution $x\in\mathbb{N}$ if and only if $a$ is a power of $2$ (where $1=2^0$ is also considered as a power of $2$). Solution. First we note that $f\left(1\right)=\sum_{i=1}^1\gcd\left(i;\;1\right)=\gcd\left(1;\;1\right)=1$. For every $n > 1$, we have $f\left(n\right)=\sum_{i=1}^n\gcd\left(i;\;n\right)>\gcd\left(n;\;n\right)=n$. Now, in order to prove part (a), we recall some notations: For two functions $\alpha: \mathbb{N}\to\mathbb{N}$ and $\beta: \mathbb{N}\to\mathbb{N}$, the Dirichlet convolution $\gamma=\alpha\bigstar\beta$ of $\alpha$ and $\beta$ is defined as the function $\gamma: \mathbb{N}\to\mathbb{N}$ such that $\gamma\left(n\right)=\sum_{d\mid n}\alpha\left(d\right)\beta\left(\frac{n}{d}\right)$. Further, we denote by $\nu: \mathbb{N}\to\mathbb{N}$ the function given by $\nu\left(n\right)=n$, and by $\phi: \mathbb{N}\to\mathbb{N}$ the Euler $\phi$ function. Now consider the function $f$ defined by $f\left(n\right)=\sum_{i=1}^n\gcd\left(i;\;n\right)$. Fix $n \in \mathbb{N}$. You can split the set of numbers $\left\{1;\;2;\;...;\;n\right\}$ into classes characterized by the greatest common divisor with $n$: For every number $k$ in the set $\left\{1;\;2;\;...;\;n\right\}$, the number $\gcd \left(k;\;n\right)$ is a divisor of $n$. Conversely, for every divisor $d$ of $n$, there are exactly $\phi\left(\frac{n}{d}\right)$ numbers $k$ in the set $\left\{1;\;2;\;...;\;n\right\}$ such that $\gcd \left(k;\;n\right) = d$ (in fact, there are exactly $\phi\left(\frac{n}{d}\right)$ numbers in the set $\left\{1;\;2;\;...;\;\frac{n}{d}\right\}$ which are coprime with $\frac{n}{d}$; multiplying them with $d$, we get exactly all numbers $k$ in the set $\left\{1;\;2;\;...;\;n\right\}$ such that $\gcd \left(k;\;n\right) = d$). Hence, the sum $f\left(n\right)=\sum_{i=1}^n\gcd\left(i;\;n\right)$ can be considered as a sum of divisors of $n$, with each divisor $d$ of $n$ occuring exactly $\phi\left(\frac{n}{d}\right)$ times. Hence, we can write $f\left(n\right)=\sum_{d\mid n}\phi\left(\frac{n}{d}\right)\cdot d=\sum_{d\mid n} d\cdot \phi\left(\frac{n}{d}\right)=\sum_{d\mid n} \nu\left(d\right)\cdot \phi\left(\frac{n}{d}\right)$. Thus, the function $f$ is the Dirichlet convolution of the functions $\nu$ and $\phi$. In other words, $f=\nu\bigstar\phi$. Since the functions $\nu$ and $\phi$ are multiplicative, it follows that the function $f$ is multiplicative, too. This solves part (a) of the problem. Since the function $f$ is multiplicative, the function $g$ defined by $g\left(n\right)=\frac{f\left(n\right)}{n}$ must be multiplicative, too. In the above we found that $f\left(1\right) = 1$; thus, $g\left(1\right) = 1$. Also, in the above, we saw that $f\left(n\right) > n$ for every $n > 1$; this becomes $g\left(n\right) > 1$ for every $n > 1$. For any prime p and any $a\geq 0$, we have $f\left(p^a\right)=\sum_{d\mid p^a} d\cdot \phi\left(\frac{p^a}{d}\right)=\sum_{0\leq k\leq a} p^k\cdot \phi\left(\frac{p^a}{p^k}\right)$ (since all divisors of $p^a$ have the form $p^k$ for some k such that $0\leq k\leq a$) $=\sum_{0\leq k\leq a} p^k\cdot \phi\left(p^{a-k}\right)=\sum_{0\leq k<a} p^k\cdot \phi\left(p^{a-k}\right)+p^a\cdot\phi\left(p^{a-a}\right)$ $=\sum_{0\leq k<a} p^k\cdot \phi\left(p^{a-k}\right)+p^a=\sum_{0\leq k<a} p^k\cdot p^{\left(a-k\right)-1}\left(p-1\right)+p^a$ $=\sum_{0\leq k<a} p^{a-1}\left(p-1\right)+p^a=ap^{a-1}\left(p-1\right)+p^a$, so that $g\left(p^a\right)=\frac{f\left(p^a\right)}{p^a}=\frac{ap^{a-1}\left(p-1\right)+p^a}{p^a}=\frac{a\left(p-1\right)+p}{p}$. In particular, $g\left(2^a\right)=\frac{a\left(2-1\right)+2}{2}=\frac{a+2}{2}$. Hence, for every positive integer a, we have $g\left(2^{2a-2}\right)=\frac{\left(2a-2\right)+2}{2}=a$. Since $g\left(2^{2a-2}\right)=\frac{f\left(2^{2a-2}\right)}{2^{2a-2}}$, this yields $f\left(2^{2a-2}\right)=a\cdot 2^{2a-2}$. Thus, the equation f(ax) = ax has a solution $x\in\mathbb{N}$, namely $x=2^{2a-2}$ (we have $x\in\mathbb{N}$, since $2a-2\geq 0$, since $a\geq 1$). Hence, part (b) of the problem is solved. Now remains to solve part (c) of the problem. Since $g\left(n\right)=\frac{f\left(n\right)}{n}$, the equation f(x) = ax rewrites as g(x) = a; hence, part (c) of the problem asks us to show that, for a positive integer a, the equation g(x) = a has exactly one solution $x\in\mathbb{N}$ if and only if a is a power of 2. In order to show this, it is enough to verify the following two assertions: Assertion 1. If a is a power of 2, then the equation g(x) = a has exactly one solution $x\in\mathbb{N}$. Assertion 2. If a is not a power of 2, then the equation g(x) = a has more than one solution $x\in\mathbb{N}$. Proof of Assertion 1. Let a be a power of 2. We have to show that the equation g(x) = a has exactly one solution $x\in\mathbb{N}$. This is trivial for a = 1 (in fact, g(1) = 1, while for any n > 1, we have g(n) > 1, so that x = 1 is the only solution of the equation g(x) = 1). Hence, in the following, it will be enough to consider the case when a > 1. In order to show that the equation g(x) = a has exactly one solution $x\in\mathbb{N}$, we consider an arbitrary solution $x\in\mathbb{N}$ of this equation. If x is a power of 2, say $x=2^t$, then $a=g\left(x\right)=g\left(2^t\right)=\frac{t+2}{2}$, so that t = 2a - 2. Hence, we get the solution $x=2^{2a-2}$. Now, in order to show that this is the only solution of the equation g(x) = a, we have to show that if x is not a power of 2, then the equation g(x) = a cannot hold. And this can be showed as follows: Since we have set that x is not a power of 2, we can write x in the form $x=2^t\cdot p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_r^{a_r}$, where t is an integer $\geq 0$, where $p_1$, $p_2$, ..., $p_r$ are odd primes (i. e. primes > 2) and $a_1$, $a_2$, ..., $a_r$ are positive integers. Then, since the function g is multiplicative, $g\left(2^t\cdot p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_r^{a_r}\right)=g\left(2^t\right)\cdot g\left(p_1^{a_1}\right)\cdot g\left(p_2^{a_2}\right)\cdot ...\cdot g\left(p_r^{a_r}\right)$. Since $x=2^t\cdot p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_r^{a_r}$, we thus have $g\left(x\right)=g\left(2^t\right)\cdot g\left(p_1^{a_1}\right)\cdot g\left(p_2^{a_2}\right)\cdot ...\cdot g\left(p_r^{a_r}\right)$. Since $p_1^{a_1}>1$, we have $g\left(p_1^{a_1}\right)>1$. On the other hand, $g\left(p_1^{a_1}\right)=\frac{a_1\left(p_1-1\right)+p_1}{p_1}$. Since $p_1$ is odd, $p_1-1$ is even; thus, $a_1\left(p_1-1\right)$ is also even, so that $a_1\left(p_1-1\right)+p_1$ is odd again. Hence, the fraction $\frac{a_1\left(p_1-1\right)+p_1}{p_1}$ has an odd numerator and an odd denominator. In other words, the number $g\left(p_1^{a_1}\right)$ can be written as a fraction with odd numerator and odd denominator. We also know that this number is > 1. Similarly, same holds for the numbers $g\left(p_2^{a_2}\right)$, $g\left(p_3^{a_3}\right)$, ..., $g\left(p_r^{a_r}\right)$: They can also be written as fractions with odd numerators and odd denominators, and are > 1. Thus, the product $g\left(p_1^{a_1}\right)\cdot g\left(p_2^{a_2}\right)\cdot ...\cdot g\left(p_r^{a_r}\right)$ of all of these numbers is also a fraction with odd numerator and odd denominator, and is > 1. Multiplying this product with $g\left(2^t\right)=\frac{t+2}{2}$, we eventually kick some factors out of the denominator (in fact, some of the factors which divide t + 2), maybe we even get the number integer, but we surely won't get rid of the odd prime factors in the numerator. Hence, the number $g\left(x\right)=g\left(2^t\right)\cdot g\left(p_1^{a_1}\right)\cdot g\left(p_2^{a_2}\right)\cdot ...\cdot g\left(p_r^{a_r}\right)$ is a fraction with odd prime factors in the numerator. Hence, it cannot be a power of 2 (greater than 1). Thus, since a is a power of 2 (greater than 1), the equation g(x) = a cannot hold. And thus, Assertion 1 is proven. Proof of Assertion 2. The proof of Assertion 2 will be mostly the same as given by ZetaX in post #4: If a is not a power of 2, then a has an odd divisor > 1; in other words, we can write a in the form a = s (2r + 1), where $s\geq 1$ and $r\geq 1$ are integers (actually, $r\geq 1$ because the odd divisor 2r + 1 should be > 1). Then, because of the multiplicativity of the function g, we have $g\left(2^{2\left(s-1\right)}\cdot 3^{3r}\right)=g\left(2^{2\left(s-1\right)}\right)\cdot g\left(3^{3r}\right)$ $=\frac{2\left(s-1\right)+2}{2}\cdot\frac{3r\left(3-1\right)+3}{3}=s\left(2r+1\right)=a$. On the other hand, as we saw above, $g\left(2^{2a-2}\right)=a$. Since $2^{2\left(s-1\right)}\cdot 3^{3r}\neq 2^{2a-2}$ (in fact, since $r\geq 1$, the number $2^{2\left(s-1\right)}\cdot 3^{3r}$ is divisible by 3, while the number $2^{2a-2}$ is not), the equation g(x) = a thus has, at least, two solutions $x\in\mathbb{N}$. And Assertion 2 is proven. This completes the solution of the problem. EDIT: Part (a) of this problem was also discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=16599 . Darij

ZetaX wrote: You can prove the multiplicativity easily by the chinese remainder theorem: Let $x,y$ be coprime. Then $\gcd(z,xy) = \gcd(z,x)\gcd(z,y) = \gcd(z \mod x,x)\gcd(z \mod y,y)$, and so $\gcd(r(a,b),xy))=\gcd(a,x)\gcd(b,y)$ (here $r(a,b)$ denotes the smallest natural number that fulfills $r(a,b) \equiv a \mod x,r(a,b) \equiv b \mod y$) Can you show me how to get it or its proof

Then $\gcd(z,xy) = \gcd(z,x)\gcd(z,y)$ because $x,y$ are coprime. $\gcd(z,x) = \gcd(z \mod x,x)$ and $\gcd(z,y) = \gcd(z \mod y,y)$ by Euklid's calculation of the $\gcd$, so by $\gcd(a,b) = \gcd(a-k\cdot b,b)$ for all $k$. Then $\gcd(r(a,b),xy))=\gcd(a,x)\gcd(b,y)$ by setting $z=r(a,b)$ into the above. (here $r(a,b)$ denotes the smallest natural number that fulfills $r(a,b) \equiv a \mod x,r(a,b) \equiv b \mod y$) Is it clear now¿

Thanks for reply Zetax ZetaX wrote: $ f(xy) = \gcd(1,xy) + ... + \gcd(xy,xy)$ and in $ f(x)f(y) = (\gcd(1,x) + ... + \gcd(x,x))(\gcd(1,y) + ... + \gcd(y,y)) =$ $ = \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy)$ every residue class $ \mod xy$ (on the left side of the $ \gcd$) occurs exactly one time, so they are identical. Sorry for asking again this is also mis understandable for me can you explain how did you show $ f(xy) = f(x)f(y)$ Abdurashid

$ f(xy) = \gcd(1,xy) + ... + \gcd(xy,xy)$ by definition. $ f(x) = (\gcd(1,x) + ... + \gcd(x,x))$ and $ f(y) = (\gcd(1,y) + ... + \gcd(y,y))$ also by definition, thus $ f(x)f(y) = (\gcd(1,x) + ... + \gcd(x,x))(\gcd(1,y) + ... + \gcd(y,y))$. $ (\gcd(1,x) + ... + \gcd(x,x))(\gcd(1,y) + ... + \gcd(y,y)) =$ $ = \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ...$ $ ... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy)$ by the equality $ \gcd(r(a,b),xy)) = \gcd(a,x)\gcd(b,y)$ shown before. Claim (then we are done): $ \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ...$ $ ... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy) =$ $ = \gcd(1,xy) + ... + \gcd(xy,xy)$ To see this: when $ a \in \{ 1,2,...,x\}$ and $ b \in \{ 1,2,...,y\}$ vary, the value of $ r(a,b)$ gets everything from $ 1$ to $ xy$ exactly once; this is true since: $ r(a,b) = r(c,d)$ iff $ a \equiv c \mod x$ and $ b \equiv d \mod y$, so (since $ a,c \in \{ 1,2,...,x\}$ and $ b,d \in \{ 1,2,...,y\}$) also iff $ a = c$ and $ b = d$. This shows that every value is achieved once and only once, giving the desired equality.

I unnderstood your steps but the problem ıs hereç sorry for asking a lot ZetaX wrote: $f(xy)=\gcd(1,xy)+...+\gcd(xy,xy)$ by definition. $(\gcd(1,x)+...+\gcd(x,x))(\gcd(1,y)+...+\gcd(y,y))=$ $= \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ...$ $... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy)$ by the equality $\gcd(r(a,b),xy))=\gcd(a,x)\gcd(b,y)$ shown before. here we have some terms two times as $\gcd(r(2,1),xy)$ is an example can you show how to substitute them , other purts ok. Abdurashid

There is no term two times...

$g$ is mutiplicative function. a open question with $f(n)=\sum_{d|n}{g(gcd(m,n))}$

What do you want to say¿

Note that $$\frac{f(n)}{n}=\sum_{d \mid n} \frac{\phi(d)}{d}$$for all $n \in \mathbb{N}$. Thus, we see that $$\frac{f(n)}{n}=\prod_{p \mid n, \, p\, \text{prime}} \left(1+v_p(n)\left(1-\frac{1}{p}\right)\right)$$for all $n \ge 1$, solving (a). For each $a \ge 1$, put $x=4^{a-1}$, solving (b). For (c), we claim that any $n$ other than powers of $2$ admits multiple solutions to $f(x)=nx$. Indeed, if $n \ne 2^k$ then there exists $p \mid n$ an odd prime and $q \in \mathbb{N}$ such that $n=pq$. Then $x=2^{2(q-1)}3^{3\left(\frac{p-1}{2}\right)}$ and $x=4^{n-1}$ are solutions of $f(x)=nx$. If $n=2^k$ for $k \ge 1$, ($n=1$ is trivial), then for any $x \ne 4^{n-1}$ we have $$n=\frac{f(x)}{x}=\prod_{p \mid x, \, p\, \text{prime}} \left(1+v_p(n)\left(1-\frac{1}{p}\right)\right).$$Note that $2 \mid x$ and $v_2(x)$ is even, else RHS is odd. Delete the factor $\left(1+\tfrac{1}{2}v_2(x)\right)$ as it is a power of $2$. Note the new RHS is not an empty product as $x \ne 4^{n-1}$. All the terms on the RHS are rational numbers with odd numerator and denominator, so we get a contradiction!

darij grinberg wrote: (a) Prove that the function $f$ is multiplicative. (b) Prove that for every positive integer $a$, the equation $f\left(x\right) = ax$ has a solution $x\in\mathbb{N}$. (c) Prove that, for a positive integer $a$, the equation $f\left(x\right) = ax$ has exactly one solution $x\in\mathbb{N}$ if and only if $a$ is a power of $2$ (where $1=2^0$ is also considered as a power of $2$).[/color] Um... what about a=6?

Solution from Twitch Solves ISL: Let $g(n) = f(n) / n$, so we are interested in the outputs of $g$. We start with: Claim: The function $g$ is multiplicative and satisfies \[ g(p^e) = \frac{p-1}{p} \cdot e + 1 \]for any prime power $p^e$. Proof. First, write \[ f(n) = \sum_{d \mid n} d\varphi(n/d) = \operatorname{id} \ast \varphi \]to get that $f$ is multiplicative (as the Dirichlet convolution of two multiplicative functions). Thus $g(n) = f(n)/n$ is multiplicative too. Now note that for any prime power $p^e$, we have \[ g(p^e) = \frac{f(p^e)}{p^e} = \frac{p^e \cdot 1 + p^{e-1}(p-1) + \dots + 1 \cdot (p^e-p^{e-1})}{p^e} = e + 1 - \frac ep \]so the second part is true too. $\blacksquare$ In particular, we have \[ g(2^{2a-2}) = a \]so we already know every $a$ has the solution $x = 2^{2a-2}$. We now show that this is the only solution if and only if $a$ is a power of $2$. First, if $q > 1$ is any odd divisor of $a$, then writing $a = q \cdot b$, one can note that \begin{align*} g(2^{2b-2}) &= b \\ g(3^{\frac32(q-1)}) &= q \end{align*}and in this way we generate a new solution to the given equation. This shows the solution we found is not unique when $a$ is not a power of $2$. Conversely, suppose $a = 2^\ell$ is a power of $2$ and $x$ is an integer with \[ g(x) = a = 2^\ell. \]Note that if $y$ is an odd prime power, then $\nu_2(g(y)) = 0$, and $g(y) > 1$. So by measuring $\nu_2$, we get $\nu_2(g(x)) = \ell \implies \nu_2(x) = 2a-2$ matching the solution we found before. But then for size reasons, we must have $x = 2^{2a-2}$, as desired.

@v_Enhance loved the streams on Twitch they are awesome, I highly recommend them. Thank you for the initiave.

By CRT, the multiset \[\{\gcd(k,mn):1\le k\le mn\} = \{\gcd(a,m)\gcd(b,n):1\le a\le m, 1\le b\le n\},\]so (a) follows. Note that for a prime $p$, \begin{align*} f(p^e) &= (p^e-p^{e-1})\cdot 1+(p^{e-1}-p^{e-2})\cdot p+\cdots+(p-1)\cdot p^{e-1}+p^e \\ &= p^e\left[e(1-\tfrac{1}{p})+1\right], \end{align*}so we may now extend to all $n$ using (a). This also shows that $x=2^{2a-2}$ is a solution, proving (b). We now need to find all $a$ for which there is no solution besides $x=2^{2a-2}$. Suppose $a$ has an odd factor $t\ge 3$. Then, $x=3^{3(t-1)/2}2^{2(a/t-1)}$ works, so we must have that no such $t$ exists, so $a$ must be a power of $2$. In this case, suppose $f(x)=ax$ has a solution for $x$ where $p\mid x$ and $p\ge 3$. Let $e=v_p(x)$, and let $x=2^ty$ where $y$ is odd. We have a factor of \[p^e\left[e(1-\tfrac{1}{p})+1\right],\]in $f(y)$, which is odd and bigger than $1$, and since it divides $ax$, it must actually divide $y$. This shows that $f(y)\mid y$, which is a size contradiction unless $y=1$, so $x$ is also a power of $2$. It is easy to check that $x=2^{2a-2}$ is the only solution in this case. Thus the answer to (c) is all powers of $2$.

oops multiplicativity exists $\textbf{Claim: }$ If $n=p_{1}^{e_1}p_{2}^{e_2}\dots p_{k}^{e_k},$ for primes $p_i,$ then $$\frac{f(n)}{n}=\prod_{i=1}^{k}\left(e_i+1-\frac{e_i}{p_i}\right).$$ $\emph{Proof: }$ Consider a prime $p\mid n$ with $\nu_p(n)=e.$ We have \begin{align*} f(n) &= \sum_{d\mid n}(d\cdot\varphi(n/d))\\ &= \sum_{d\mid n,\hspace{3pt} \nu_p(d)=e}(d\cdot\varphi(n/d))+\sum_{k=0}^{e-1}\left(\sum_{d\mid n,\hspace{3pt} \nu_p(d)=k}(d\cdot\varphi(n/d))\right)\\ &= p^e\sum_{d\mid n/p^e}(d\cdot\varphi(n/d))+\sum_{k=0}^{e-1}\left((p-1)p^{e-1}\sum_{d\mid n/p^e}\right)\\ &=p^{e-1}((e+1)p-e)f(n/p^e). \end{align*}Repeating for all $p$ yields the desired statement. $\blacksquare$ a) Check that $x=2^{2a-2}$ works. b) Since we want $\frac{f(x)}{x}$ to be an integer, we must have $e_i=m_{i}p_{i}$ for all $i.$ Then, $\frac{f(x)}{x}$ is a product of terms of the form $$m_{i}p_{i}+1-m_i=m_{i}(p_{i}-1)+1.$$This expression is even if and only if $p_i=2.$ Thus, the solution to $f(x)=ax$ will be unique if and only if $a$ has no odd factors, i.e. $a$ is a power of $2.$

Let $Q(n)=\frac{f(n)}{n}$ Then $Q(n)=\frac{f(n)}{n}=\sum_{d|n} \frac{\phi(d)}{d}$ or $f(n)=n \sum_{d|n} \frac{\phi(d)}{d}$ a)Clearly $f(mn)=mn \sum_{d|n} \frac{\phi(d)}{d}=m \cdot n \cdot \sum_{d_1|n,d_2|m} \frac{\phi(d_1 d_2 )}{d_1 d_2}=n \sum_{d_1|n} \frac{\phi(d_1)}{d_1} m \sum_{d_2|m} \frac{\phi(d_2)}{d_2}=f(m) \cdot f(n)$ b)Since the function is multiplicative,it suffices to show the result for $X=p^e$ Plugging in gives,$Q(X)=\sum_{i=0}^e \frac{\phi(p^i)}{p^i}=\frac{p-1}{p} \cdot e + 1 $ and clearly this works for $N=2^{2(a-1)}$ c)The answer is all $a=2^F$ which clearly works. If $a$ has an odd factor then $n=pq$. Then $x=2^{2(q-1)}3^{3\left(\frac{p-1}{2}\right)}$ and $x=4^{n-1}$ are solutions of $f(x)=nx$,a contradiction so we are done.

Observe that for some $d\mid n,$ we have $\gcd(k,n)=d$ if and only if $k=d\cdot l$ and $\gcd(l,n/d)=1.$ That is, for $\varphi(n/d)$ values. Thus \[f(n)=\sum_{k=1}^{n} \gcd(k,n)=\sum_{d\mid n}d\cdot\varphi\bigg(\frac{n}{d}\bigg)=(\text{id}*\varphi )(n).\]For the first part, we will prove a stronger result which will, of course, solve our problem as well, since $\text{id}$ and $\varphi$ are multiplicative Lemma: For any multiplicative functions $f,g$ their Dirichlet Convolution, $f*g,$ is also multiplicative. Proof: Simply manipulate $f*g$ as follows: \[(f*g)(mn)=\sum_{d\mid mn}f(d)g\bigg(\frac{n}{d}\bigg)=\sum_{a\mid m}\sum_{b\mid n}f(a\cdot b)g\bigg(\frac{m}{a}\cdot\frac{n}{b}\bigg)=\]\[=\sum_{a\mid m}\sum_{b\mid n}f(a)f(b) g\bigg(\frac{m}{a}\bigg)g\bigg(\frac{n}{b}\bigg)=\sum_{a\mid m}f(a)g\bigg(\frac{m}{a}\bigg)\sum_{b\mid n}f(b)g\bigg(\frac{n}{b}\bigg)\]and the latter is clearly equal to $(f*g)(m)\cdot (f*g)(n).$ Hence, if $f$ and $g$ are multiplicative, then so is $f*g.$ Before moving on to the best parts, let's compute out function some more. Observe that \[f\big(p^k\big)=\sum_{i=0}^k p^i\cdot\varphi\big(p^{k-i}\big)=\cdots=p^k\bigg(\frac{p-1}{p}\cdot k+1\bigg).\]This already solves the second part of our problem, since $f(4^{n-1})=4^{n-1}\cdot n.$ Now, moving on to the third part, by the muliplicability of $f$ and the latter formula, we can deduce that \[\frac{f(n)}{n}=\prod_{p}\bigg(\frac{p-1}{p}\cdot\nu_p(n)+1\bigg).\]Assuming that $n=(2k+1)\cdot m$ for some $k>1$ then other than $f(4^{n-1})=4^{n-1}\cdot n$ we also have \[f(4^{m-1}\cdot 3^{3k})=\bigg(\frac{2-1}{2}\cdot (2m-2)+1\bigg)\bigg(\frac{3-1}{3}\cdot 3k+1\bigg)=n.\]Hence, if there exists a unique solution to $f(x)/x=n$ then $n=2^k.$ A simple check of $\nu_2$ will yield that indeed, all powers of two, have a unique solution.

a) By CRT, we know that for $k=1$ to $mn$, $k$ goes through all the different possible pairs of remainders mod $m$ and mod $n$ exactly once. Therefore, it is clear that $$f(mn)=\sum_{k=1}^{mn}\gcd(k,mn)=\sum_{k=1}^m\gcd(k,m)\sum_{k=1}^n\gcd(k,n)=f(m)f(n).$$b) Let $g(n)=\frac{f(n)}{n}$. It is clear that $g(1)=1$ and that $g(mn)=g(m)g(n)$ for relatively prime $m,n\in\mathbb{N}$. We will look at powers of a prime $p$, say $p^k$. It is easy to show that $$f(p^k)=pf(p^{k-1})+\frac{p-1}{p}p^{k}$$simply from how the definition of $f(n)$ works. Dividing both sides by $p^k$, we get $$g(p^k)=g(p^{k-1})+\frac{p-1}{p}.$$As $k=0$ gives $1$, we know that $$g(p^k)=1+k\cdot\frac{p-1}{p}.$$It is now clear that $x=2^{2a-2}$ satisfies the requested condition. c) First, it is clear that $g(n)=1$ only at $n=1$, so $a=1$ is unique. We can express any positive integer $x>1$ as $x=\prod{p_i}^{e_i}$, and therefore, $$g(x)=g\left(\prod{p_i}^{e_i}\right)=\prod g\left({p_i}^{e_i}\right)=\prod\left(1+e_i\cdot\frac{p_i-1}{p_i}\right).$$Note that if we simply set $e_i=p_i$ for a certain $i$, we would be multiplying by $p_i$. Therefore, if we had $a$ be any number that is not a power of $2$, we can take any prime factor of $a$ that is not $2$, set that as $p_i$ and $e_i$, and let $p_1=2$ do the rest of the work, giving us an unwanted second way to construct $g(x)=a$. However, if $a$ was a power of $2$, assume FTSOC that there is this other $y$ such that $g(y)=a$ and $y$ is not a power of $2$. We can see that if we were to take the product besides the term for $p_i=2$, the numerators are all odd, and the denominators are all odd. The numerator is clearly greater than the denominator, and that part of the numerator clearly cannot be cancelled out from the $p_i=2$ term. Therefore, $g(x)$ would have some factor that is not a power of $2$ that the denominator cannot cancel out, meaning that it does not evaluate to a power of $2$, contradiction. Therefore, our answer is $$\boxed{a=2^k,k\in\mathbb{Z}^{\ge0}}.$$

We claim that if $c\equiv a\pmod m$ and $c\equiv b\pmod n$ then $\gcd(c,mn)=\gcd(a,m)\gcd(b,n).$ Since $\gcd(a,m)=\gcd(c,m)$ and $\gcd(b,n)=\gcd(c,n)$ by the euclidean algorithm, and $\gcd(c,m)\gcd(c,n)=\gcd(c,mn)$ so our claim holds. By CRT, there is a bijection between $(a,b)$ and $c$ so $f(mn)=f(m)f(n)$ Note that $f(1)=1$ and $f(2^{k+1})=2f(2^k)+2^k$, so by induction, $f(4^k)=(k+1)4^k.$ We claim that the answer is powers of two. Suppose $p\mid a$ where $p$ is an odd prime. Already $4^{a-1}$ is a solution, but also let $a=pq,$ and we have $f(4^{q-1})=q.$ We claim that \[f\left(27^{\frac{p-1}{2}}\right)=p\cdot \left(27^{\frac{p-1}{2}}\right).\]We can do this in much the same way as $f(4^k)=(k+1)4^k$ and since $f(m)f(n)=f(mn)$ we're done, as we have found another solution to the equation.

a) Note that every number $k$ from $1$ to $mn$ has a unique pair $(x,y)$ such that $k\equiv x\pmod m$ and $k\equiv y\pmod n$; this means that there is a bijection between values of $\gcd{(k,mn)}$ and values formed by multiplying $f(m)f(n)$ into $mn$ different summands. b) Note that \[f(p^k)=p^k(1)+p^{k-1}(p-1)+p^{k-2}(p^2-p)+\dots+p(p^{k-1}-p^{k-2})+1(p^k-p^{k-1})=p^k\left(k\left(\frac{p-1}{p}\right)+1\right)\]and so evidently $2^{2a-2}$ is a solution. c) Set $g(p,k)=k\left(\frac{p-1}{p}\right)+1$ and note that if $x=p_1^{e_1}\cdot p_2^{e_2}\cdots p_n^{e_n}$ then we have \[g(p_1,e_1)g(p_2,e_2)\dots g(p_n,e_n)=a.\]From part b) we know that $2^{2a-2}$ is a solution. Now suppose that $a=2^ko$ where $o>1$ is odd. Then set $x=2^{2^{k+1}-2}\cdot 3^{\tfrac{3o-3}{2}}$. This gives another solution. Then $a$ is a power of $2$. Then all powers of $2$ in $g(p_1,e_1)g(p_2,e_2)\dots g(p_n,e_n)$ must come from $g(2,2^{k+1}-2)$ where $a=2^k$ implying that $2^{2a-2}$ is the only solution so the answer is all powers of $2$. $\blacksquare$

If $d$ divides $n$, then the number of times $d$ shows up in $f(n)$ is the number of $q$ with $1\leq q\leq \tfrac{n}{d}$ such that $dq\leq n$ and $\gcd(q,n)=1$. This is the number of units $\mod \tfrac{n}{d}$, or $\phi(\tfrac{n}{d})$. So if $d\mid mn$, $d$ shows up in $f(mn)$ exactly $\phi(\tfrac{nm}{d})$ times. If $e\mid d$ shows up in $f(n)$ and $\tfrac{d}{e}$ shows up in $f(m)$, then $e\mid n$ and $\tfrac{d}{e}\mid m$, so the number of times $e$ shows up in $f(n)$ is $\phi(\tfrac{n}{e})$ and the number of times $\tfrac{d}{e}$ shows up in $f(n)$ is $\phi(\tfrac{m}{d/e})$. Moreover, we know that $e=\gcd(n,d)$ and $\tfrac{d}{e}=\gcd(m,d)$, so the only values in $f(n)$ and $f(m)$ that multiply to $d$ are $\gcd(n,d)$ and $\gcd(m,d)$, respectively. So the number of terms in $f(n)\cdot f(m)$ that are equal to $d$ is $\phi(\tfrac{n}{e})\cdot \phi(\tfrac{m}{d/e})=\phi(\tfrac{nm}{d})$, since $m,n$ are coprime. Therefore for each $d\mid nm$, it shows up the same number of times in $f(mn)$ and $f(m)f(n)$. The number of terms in $f(mn)$ is the same as the number of terms in $f(m)f(n)$, thus if $\gcd(m,n)=1$, then $f(mn)=f(m)f(n)$, which solves part (a). We now find a formula for $f(n)$. If $k=\ell p^d$ where $1\leq \ell \leq p^{e-d}$, and $\gcd(\ell,p)=1$, then $\gcd(k,p^e)=p^d$, and there are $\phi(p^{e-d})$ values of $\ell $ satisfying this. Since $\gcd(k,p^e)\neq 1\implies p\mid k$, we know that \begin{align*} f(p^e)&=1\cdot \phi(p^e)+\sum_{d=1}^{e-1} p^d\cdot \phi(p^{e-d})+p^e\cdot \phi(1) \\ &= \sum_{d=0}^e p^d\cdot \phi(p^{e-d}) \\ &= \sum_{c\mid p^e} \phi(c)\cdot \frac{p^e}{c}. \end{align*}Then, evaluating $f(p^e)$ for $e\geq 1$ and prime $p$, we get $f(p^e)=p^{e-1}(p(e+1)-e)$. Now note that if $e=pr$ for some positive integer $r$, we get $f(p^{pr})=p^{pr}(r(p-1)+1)$. Setting $p=2$ and $e=2e_1$, we have $f(2^{2e_1})=2^{2e_1}(e_1+1)$. Thus $f(2^{2(a-1)})=a2^{2(a-1)}$ for all $a\in \mathbb{N}$. This solves part (b). Note that if $e=\tfrac{p^b-1}{p-1}\cdot p$, then $f(p^e)=p^e\cdot p^b$ for any $b\geq 1$, using our formula for $f(x)$. Since $f$ is multiplicative, if we let $a=p_1^{e_1}\cdots p_k^{e_k}$ be the prime factorization of $a$, then a solution to $f(x)=ax$ is $x=\Pi_{i=1}^k p_i^{d_i}$ where $d_i=\tfrac{p(p^{e_i}-1)}{p-1}$ for all $1\leq i\leq k$. If $a$ is not a power of $2$, then this value of $x$ is not $2^{2(a-1)}$, since it contains prime factors other than $2$. Suppose $a=2^e$, for some non-negative integer $e$, and suppose $x=p_1^{e_1}\cdots p_k^{e_k}$ is the prime factorization of a solution to $f(x)=2^e x$. Then $$f(x)=\prod_{i=1}^k p_i^{e_i-1}(p_i(e_i+1)-e_i)=2^e(p_1^{e_1}\cdots p_k^{e_k}),$$so $$\prod_{i=1}^k (p_i(e_i+1)-e_i)=2^e(p_1\cdots p_k).$$Each $p_i(e_i+1)-e_i$ that has $p_i\neq 2$ is odd, since $p_i>2$ by casework on the parity of $e_i$. Thus the only way $2^e\mid \Pi_{i=1}^k (p_i(e_i+1)-e_i)$ is if there is a $p_i$ that is $2$ (WLOG let $p_1=2$) and $2^e\mid 2(e_1+1)-e_1$. This implies that $2^e\mid e_1+2$ so $e_1+2=2^e\cdot m$ for some $m\in \mathbb{N}$. Also, since $p_1=2$, we have $2\mid m$, so $m=2m_1$ for some $m_1\in \mathbb{N}$. Then we have $$\prod_{i=2}^k ((p_i-1)e_i+p_i)\cdot m_1=p_2\cdots p_k.$$For each $i$, if $e_i>0$, then $(p_i-1)e_i>0$, which means that the LHS of the above equation is larger than the RHS, contradiction. Therefore for all $i$, we must have $e_i=0$. But then the solution $x=p_1^{e_1}\cdots p_k^{e_k}$ to $f(x)=2^e x$ must be of the form $2^{e_1}$, and as we have seen, $e_1=2^em-2$ for some $m$. We get $$f(2^{2^em-2})=2^{2^e-3}(2(2^em-1)-(2^em-2))=2^e\cdot 2^{2^em-2},$$which simplifies to $m=2$. Thus $x=2^{2(2^e-2)}$, meaning that $f(x)=ax$ has a unique solution if and only if $a=2^e$ for some $e\in \mathbb{Z}_{\geq 0}$.

By counting over values of $\gcd(k,n)$, we express $f$ as $$f(n)=\sum_{d \mid n} d\cdot\phi(n/d)=\mathrm{id} * \phi$$where $*$ denotes the usual Dirichlet convolution. From this, multiplicativity is immediate. For $p$ prime, we can then compute $$f(p^k)=(k+1)p^k-kp^{k-1}.$$We now present two methods of generating a solution to $f(x)=ax$ for any $a$ not a power of two, and prove that $f(x)=ax$ has a unique solution when $a$ is a power of two. For any $a$, we can simply take $x=2^{2a-2}$, in which case $$f(x)=f(2^{2a-2})=(2a-1)2^{2a-2}-(2a-2)2^{2a-3}=2^{2a-2}(2a-1-(a-1))=a2^{2a-2},$$as desired. On the other hand, from our formula for $f(p^k)$, fixing $p$ and setting $k=\tfrac{p^{a+1}-p}{p-1}$, we obtain $$f(p^k)=\frac{p^{a+1}-1}{p-1}\cdot p^k-\frac{p^{a+1}-p}{p-1}p^{k-1}=p^k\cdot \frac{p^{a+1}-p^a}{p-1}=p^ap^k.$$By multiplicativity, for some $a=p_1^{e_1}\ldots p_k^{e_k}$, taking $$x=\prod_{i=1}^k p_i^{\frac{p^{e_i+1}-p}{p-1}}$$satisfies $f(x)=ax$. Moreover, if $a$ is not a power of two, then this value of $x$ is different from $2^{2a-2}$ as it is divisible by some odd prime. If $a$ is a power of two, note that $x=2^{2a-2}$ can easily be seen to be the only power of two that yields $f(x)=ax$. Hence suppose we have some $x$ with $f(x)=ax$ that's a non-power of two, and suppose $\nu_2(x)=k$. For any $p>2$, $f(p^k)$ is odd, hence $\nu_2(f(x))=\nu_2(f(2^k))$. If $k$ is odd, then $\nu_2(f(2^k))=k-1$, but $\nu_2(ax)\geq k$: impossible. If $k$ is even, then from our previous results $\nu_2(f(2^k))=k+\nu_2(\tfrac{k}{2}+1)$, hence $\nu_2(\tfrac{k}{2}+1)=\nu_2(a) \implies k\geq 2a-2$, since $a$ is a power of two. Further, since $f(p^k)>p^k$ for any odd $p$, and $\tfrac{f(2^k)}{2^k}=k/2+1$ is increasing in $k$, we have $$\frac{f(x)}{x}=\frac{f(2^k)}{2^k}\cdot \frac{f(x/2^k)}{x/2^k}\geq \frac{f(2^{2a-2})}{2^{2a-2}}\cdot \frac{f(x/2^k)}{x/2^k}>\frac{f(2^{2a-2})}{2^{2a-2}}=a,$$which is a contradiction. Hence $x=2^{2a-2}$ is the unique solution to $f(x)=ax$, as desired. $\blacksquare$

(a) Note that if we are going from 1 to $mn$, by CRT, each possible pair of residues mod $m$ and $n$ shows up exactly once. If $m$ and $n$ are relatively prime $x\equiv a\pmod m$ and $x\equiv b\pmod n$, then $\gcd(x,mn)=\gcd(a,m)\cdot \gcd(b,n)$, so therefore, we have $$f(mn)=\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}(\gcd(i,m)\cdot \gcd(j,n))$$$$=\sum_{i=0}^{m-1}(\gcd(i,m)\cdot \sum_{j=0}^{n-1}(\gcd(j,n)))$$$$=\sum_{i=0}^{m-1}(\gcd(i,m)\cdot f(n))$$$$=f(n)\sum_{i=0}^{m-1}\gcd(i,m)$$$$=f(m)f(n).$$ (b) We first claim that if $p$ is a prime and $k$ a positive integer, then $$f(p^k)=(k+1)p^k -kp^{k-1}.$$We will use induction. For $k=1$, we obviously have $f(p)=2p-1.$ Now consider $f(p^{k+1})$ given $f(p^k)$. Note that the values in the summation for $f(p^{k+1})$ is almost the same as $f(p^k)$ repeated $k$ times, but with the final term being $p^{k+1}$ rather than $p^k$ again. Therefore, we have the recurrence $$f(p^{k+1})=pf(p^k)+p^{k+1}-p^k,$$from which it follows by induction that $$f(p^k)=(k+1)p^k -kp^{k-1}.$$ In particular, we have $$f(2^k)=(k+1)2^k -k\cdot 2^{k-1}$$$$\frac{f(2^k)}{2^k}=k+1-\frac{k}{2}=\frac{k}{2}+1,$$so we can obtain any positive integer value of $f(x)/x$ by plugging in a power of 4 (possibly 1). (c) We claim that the answer is all powers of 2. If $a$ is not a power of 2. consider the number $2^{2n}\cdot 3^{3m}.$ Since $f$ is multiplicative, and again using our prime power formula from earlier, we can obtain that $$\frac{f(2^{2n}\cdot 3^{3m})}{2^{2n}\cdot 3^{3m}}=(n+1)(2m+1).$$If $a$ is not a power of 2, we can make $m$ a positive integer to make the required odd factor, then adjust $n$ to get all the remaining factors of 2, so there is a way to achieve $a$ using at least one factor of 3. However, we also know from earlier that we can achieve any value of $a$ using only factors of 2, so there is more than one way to achieve $a$ if $a$ is not a power of 2. To show that there is only one way to achieve powers of 2, consider the following. Let $n$ be a positive integer. Then, since the function is multplicative, we have $$\frac{f(n)}{n}=(\frac{1}{2}v_2(n)+1)(\frac{2}{3}v_3(n)+1)(\frac{4}{5}v_5(n)+1)(\frac{6}{7}v_7(n)+1)\cdots$$Consider how we could get a power of 2 from this function. Note that $$(\frac{2}{3}v_3(n)+1)(\frac{4}{5}v_5(n)+1)(\frac{6}{7}v_7(n)+1)\cdots\geq 1.$$Moreover, if $n$ has any prime factor other than 2, i.e. if any of $v_3(n),v_5(n),$ etc. are positive, then $$(\frac{2}{3}v_3(n)+1)(\frac{4}{5}v_5(n)+1)(\frac{6}{7}v_7(n)+1)\cdots$$will be greater than 1 and have an odd numerator, which will prevent the expression from being a power of 2. Therefore, the only way for $f(n)/n$ to be a power of 2 is if $n$ itself is a power of 2, so if $a$ is a power of 2, there is only one way to achieve it, so we are done.

Can someone please tell me where I am going wrong in the proof for $\textbf{part (b)}$ T__T . We firstly have that $\varphi * 1=\operatorname{id}\iff\varphi=\operatorname{id}*\mu$. The $d(n)$ is the number of divisors of $n$, $\sigma(n)$ is the sum of divisors of $n$, $\varphi(n)$ is the Euler Totient Function, $\operatorname{id}$ is the identity function and $\mu(n)$ is the Mobius Function. So after getting $f(n)=\varphi *\operatorname{id}$, we can get the following $f(n)=(\operatorname{id}*\mu)*\operatorname{id}=\operatorname{id}*(\operatorname{id}*\mu)=(\operatorname{id}*\operatorname{id})*\mu=F*\mu$ where $F(n)=nd(n)$. We can use Mobius Inversion again to get $f*1=F$.

. Thanks to @a_n for pointing out where I went wrong .

We first consider for how many occurrences of $k$ for which we have $\gcd(k,n)=d$, where $d$ is a divisor of $n$. We must have $d\mid k$, and $\gcd(\frac{k}{d},\frac{n}{d})=1$. That is, $\frac{k}{d}$ is coprime to $\frac{n}{d}$. So, there are $\phi(\frac{n}{d})$ occurrences of $k$. Our sum then becomes \[f(n)=\sum_{k=1}^n\gcd(k,n)=\sum_{d\mid n}d\phi(\frac{n}{d})=(I*\phi)(n)\]where $I$ denotes the identity function. This immediately gives us (a), since $f$ is multiplicative as a consequence of being the Dirichlet convolution of two multiplicative functions. For a prime $p$, we have $f(p^k)=\sum_{e=0}^{k}p^e\phi(p^{k-e})=p^0(p-1)p^{k-1}+p^1(p-1)p^{k-2}+\dots + p^{k-1}(p-1)p^0+p^k=k(p-1)p^{k-1}+p^k$. Now consider the function $g(n)=\frac{f(n)}{n}$, which is obviously multiplicative. We have $g(p^k)=\frac{k(p-1)p^{k-1}+p^k}{p^k}=k\frac{p-1}{p}+1$. For each positive integer $a$, we have $g(2^{2(a-1)})=2(a-1)\frac{1}{2}+1=a$. This proves (b). We claim for (c) that the answer is all $a$ which are a power of $2$. Suppose that $a$ is not a power of $2$. Then $a$ has an odd factor greater than $1$ and can be written as $c(2d+1)$ for some positive integers $c$ and $d$. We have already that $g(2^{2(a-1)})=a$, and here we have also $g(2^{2(c-1)}3^{3d})=g(2^{2(c-1)})g(3^{3d})=c(3d\frac{2}{3}+1)=c(2d+1)=a$. So, for all $a$ which are not a power of $2$, $g(n)=a$ has more than one solution. We now show that when $a$ is some power of $2$ $2^r$, $g(n)=a$ has only one solution. Observe that for all odd primes $p$, $f(p^k)=k(p-1)p^{k-1}+p^k$ is odd. Consider $f(n)=2^ln$ and let $s=\nu_2(n)$. $\nu_2(f(n))=\nu_2(2^ln)=l+s$. Thus, we must have that $2^{l+s}$ divides $g(2^s)=s2^{s-1}+2^s$. So, $s2^{s-1}+2^s\geq 2^{l+s}$. Dividing both sides by $2^s$ we get $\frac{s}{2}+1\geq 2^l$ and $s\geq 2(2^l-1)$. Considering $2^l=g(n)=g(2^s)g(3^{\nu_3(n)})g(5^{\nu_5(n)})\dots$, we note that $g(p^k)=k\frac{p-1}{p}+1$ is increasing in $k$ for all primes $p$. We have also that $g(2^{2(2^l-1)})=2^l$. We deduce that $s=l$ and $\nu_p(n)=0$ for all odd primes $p$. Thus, $g(n)=2^l$ has only the solution $n=2^{2(2^l-1)}$, which proves our answer for (c).

Nice! (a) Note $f = id * \phi$, and since $id$ and $\phi$ is multiplicative, $f$ is multiplicative too. (b) Note that $f(p^k) = p^{k-1}((k+1)p-k)$, so we want, if possible, $(k+1)p-k = ap \implies p =1+ \frac{a-1}{k+1-a}$. Thus, we find that $k = 2a-2, p=2$ works and $f(2^{2a-2}) = a2^{2a-2}$. (c) Claim: All $a$ which are powers of 2(greater than 1) have exactly one solution Proof: This is because for $f(p^k) = p^{k-1}((k+1)p-k)$, we have that for $p>2$, $(k+1)p-k$ is odd. Since the function is multiplicative, in order for $a$ to be a power of 2, we have to have $x$ is a power of two in which there is a distinct soltuion. Claim: There is more than one solution when $a$ is odd Proof: Note that $f(3^{3k}) = (2k+1)3^{3k}$, proving our claim. Therefore, all even $a$ that are not powers of 2 can be created in two ways (either just using power of 2 or using power of 2 and power of 3). Thus, there is a unique solution for $a$ when $a$ is a power of 2 greater than 1.

Claim: $f = \phi \ast id$ and is thus multiplicative. Proof. Note that \[ f(n) = \sum_{k=1}^n \gcd(k,n) = \sum_{d \mid n} \phi\left(\frac{n}{d}\right) \cdot d. \]$\blacksquare$ We thus compute $f(p^e)$ \[ f(p^e) = \sum_{d=0}^e \phi(p^d) \cdot p^{e-d} = p^e + \sum_{d=1}^e p^{d-1} \cdot (p-1) \cdot p^{e-d} = p^e + ep^{e-1} \cdot (p-1). \]As such, \[ \frac{f(p^e)}{p^e} = 1 + e - \frac{e}{p}. \]This generalizes for $n = p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}$ as \[ \frac{f(n)}{n} = \frac{f(p_1^{e_1})}{p_1^{e_1}} \cdot \frac{f(p_2^{e_2})}{p_2^{e_2}} \cdots \frac{f(p_k^{e_k})}{p_k^{e_k}} \]For each integer $a$, we have that $f(2^{2(a-1)}) = a \cdot 2^{2(a-1)}$. If $a$ is a power of $2$, since $\frac{f(p^e)}{p^e}$ has an odd divisor of the numerator for $p \ne 2$, it only has one factor. Else, we also another construction as \[ \frac{f(3^e)}{3^e} = \frac{2e + 3}{3} \]which allows constructing all odds other than $1$.

Note that since \[ f(n) = \sum_{k-1}^n \gcd(k, n) = \sum_{d\mid n} d \cdot \phi \left(\frac{n}{d}\right) \]Thus $f = id * \phi$ and thus $f$ is multiplicative. This completes part a. $\square$ Now, note that for any positive integer $k$, \[ f(p^k) = p^k - p^{k-1} + p(p^{k-1} - p^{k-2}) + + p^2(p^{k-2} - p^{k-3}) + \dots + p^{k-1}(p-1) + p^k = k(p^k - p^{k-1}) + p^k = (kp+p-k)p^{k-1} \]In particular, note that if $p^k \mid (kp+p-k)p^{k-1}$ then $k = jp$, so \[ f(p^k) = (jp^2 + p - jp)p^{k-1} = (jp - j + 1)p^k = (j(p-1)+1)p^k \]This means that if $p = 2$ and $k = 2j$, then \[ \frac{f(2^{2j})}{2^{2j}} = j + 1 \]Thus, then $f(x) = ax$ always has a solution, by taking $n$ a power of $4$ and choosing the appropriate exponent. This completes part b. $\square$ Note also that for an odd prime $p$ and $k = jp$, then \[ f(p^k) = (kp+p-k)p^{k-1} = (jp+1-j)p^k = (j(p-1)+1) \]Then this means that \[ \frac{f(p^k)}{p^k} = j(p-1)+1 \]This value is always odd when $p>3$. Now, since \[ \frac{f(n)}{n} = \prod_{p\mid n} \frac{f(p^{\nu_p(n)})}{p^{\nu_p(n)}} \]if $\frac{f(n)}{n} = a$ and $a$ is divisible by a prime other than $2$, then we could use either $n = 2^b$ or $n = 2^b3^c$, where the $3^c$ can take care of the largest odd divisor of $a$. Thus, then the only $a$ with a unique solution is when $a$ is a power of $2$. $\blacksquare$

We have \[ f(n) = \sum_{d\mid n} d \cdot \varphi \left( \frac nd \right) \]because there are exactly $\varphi \left( \frac nd \right )$ positive integers in $k\in [1,n]$ with $\gcd(k,n) = d$. Hence by the Dirichlet convulution, since identity and $\phi$ are multiplicative, we must have $f$ multiplicative. Now, we also see that \[f(p^t) = \sum_{i=0}^t p^i \varphi (p^{t-i} ) = p^t + t(p-1) p^{t-1} \]for all positive integers $t$. Hence $\frac{f(p^t)}{p^t} = t \cdot \frac{p-1}{p} + 1$. We want to show that for all $a$, there exists $x$ with $\frac{f(x)}{x}= a$. Notice that if $p = 2$, then $\frac{f(2^t)}{2^t} = \frac{t}{2} + 1$. Choosing $t = 2(x-1)$ gives that $f(2^t) = x\cdot 2^t$. Claim: The answer to part (c) is $a$ is a power of $2$. Proof: For non powers of $2$, choose $x = 2^y \cdot 3^z$ so that $\frac{2z}{3} + 1 = m$ is the largest odd divisor of $a$ and $\frac y2 + 1 = \frac{a}{m}$. Now it remains to show that only one $x$ satisfies $\frac{f(x)}{x} = 2^e$ for each $e$. Notice that $\frac{f(p^t)}{p^t} \equiv 1\pmod q$ for any prime $q\mid p-1$. Hence $p-1$ cannot have any prime factors, so $p = 2$. But then $t = 2(2^e - 1)$, which means there is only one solution to $f(x) = 2(2^e - 1)$. $\square$

OG! A) It is easy to see $f(n)=\sum_{k=1}^n\gcd(k,n)=\sum_{d\mid n}d\phi(\frac{n}{d})$ now notice for any 2 coprime $m,n$ we have $f(m)f(n) = (\sum_{d\mid n}d\phi(\frac{n}{d}))(\sum_{c\mid m}c\phi(\frac{m}{c})) = \sum_{d\mid n, c\mid m}dc\phi(\frac{mn}{dc})$. Claim: there is bijection(one to one correspondence) between divisors of $mn$ and $dc$ over all possible $d,c$ Proof: $d|n$, $c|n \implies dc|mn$. For any integer $s$ such that $s|mn$, $s=uv$, where $u|n, v|n$, more specifically $u=gcd(s,n)$ and $v= gcd(s,m)$. The proof of this is easy. Thus $dc$ over all possible $d,c$ are only and all divisors $mn$, hence, $f(m)f(n) = (\sum_{d\mid n}d\phi(\frac{n}{d}))(\sum_{c\mid m}c\phi(\frac{m}{c})) = \sum_{d\mid n, c\mid m}dc\phi(\frac{mn}{dc})=(\sum_{t\mid nm}t\phi(\frac{mn}{t})) =f(mn)$ as desired. b) By definition of $f$, $f(2^{2a-2})= 2^{2a-2}. a$ as desired c)