Multiplicative function

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

314,519 topics

9 users

TOPICS

No tags match your search

Multiplicative function

G H J

Reveal topic tags

function

number theory

greatest common divisor

equation

IMO Shortlist

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2004, number theory problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tales

16 posts

Tales

#1 h Mar 23, 2005, 2:50 AM • 6 Y

Y by Davi-8191, anantmudgal09, Adventure10, Mango247, and 2 other users

The function $f$ from the set $\mathbb{N}$ of positive integers into itself is defined by the equality $f(n)=\sum_{k=1}^{n} \gcd(k,n),\qquad n\in \mathbb{N}.$
a) Prove that $f(mn)=f(m)f(n)$ for every two relatively prime ${m,n\in\mathbb{N}}$ .

b) Prove that for each $a\in\mathbb{N}$ the equation $f(x)=ax$ has a solution.

c) Find all ${a\in\mathbb{N}}$ such that the equation $f(x)=ax$ has a unique solution.

This post has been edited 2 times. Last edited by djmathman, Aug 1, 2015, 2:54 AM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

senouy

181 posts

senouy

#2 h Mar 29, 2005, 10:41 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

senouy

181 posts

senouy

#3 h Apr 4, 2005, 11:07 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#4 h Apr 4, 2005, 2:16 PM • 6 Y

Y by A_Math_Lover, mijail, Adventure10, Adventure10, Mango247, and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

darij grinberg

6555 posts

darij grinberg

#5 h May 1, 2005, 8:30 PM • 7 Y

Y by PRO2000, Amir Hossein, Adventure10, Pratik12, Mango247, and 2 other users

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

This post has been edited 1 time. Last edited by darij grinberg, Jul 30, 2015, 6:29 PM
Reason: latex (at least in part (a))

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abdurashidjon

119 posts

abdurashidjon

#6 h Jun 6, 2006, 7:25 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

ZetaX wrote:

Can you show me how to get it or its proof

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#7 h Jun 6, 2006, 7:42 PM • 2 Y

Y by Adventure10, Mango247

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¿

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abdurashidjon

119 posts

abdurashidjon

#8 h Jun 7, 2006, 3:12 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#9 h Jun 7, 2006, 9:19 AM • 2 Y

Y by Adventure10, Mango247

$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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abdurashidjon

119 posts

abdurashidjon

#10 h Jun 8, 2006, 6:45 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#11 h Jun 8, 2006, 9:30 AM • 2 Y

Y by Adventure10, Mango247

There is no term two times...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dieuhuynh

266 posts

dieuhuynh

#12 h Jun 14, 2006, 3:27 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#13 h Jun 14, 2006, 10:26 AM • 4 Y

Y by codyj, AlastorMoody, Adventure10, Mango247

What do you want to say¿

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#14 h Aug 27, 2017, 7:30 PM • 5 Y

Y by rafayaashary1, A-Thought-Of-God, mijail, Adventure10, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pandadude

710 posts

pandadude

#15 h Aug 19, 2018, 2:12 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlastorMoody

2125 posts

AlastorMoody

#16 h Mar 24, 2020, 6:59 PM • 3 Y

Y by Mango247, Mango247, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6894 posts

v_Enhance

#17 h May 15, 2020, 9:33 PM • 6 Y

Y by oty, Mathematicsislovely, v4913, Pranav1056, metricpaper, Funcshun840

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.

This post has been edited 1 time. Last edited by v_Enhance, Jun 5, 2020, 8:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

oty

2332 posts

oty

#18 h May 15, 2020, 11:41 PM • 4 Y

Y by v_Enhance, Imayormaynotknowcalculus, Bassiskicking, SatisfiedMagma

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#19 h Feb 7, 2021, 11:30 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amuthup

779 posts

amuthup

#20 h Apr 4, 2021, 12:46 AM

Y by

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.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sprites

478 posts

Sprites

#21 h Aug 28, 2021, 9:00 AM • 3 Y

Y by Pranav1056, Mango247, Mango247

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.

This post has been edited 1 time. Last edited by Sprites, Aug 28, 2021, 9:01 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

oVlad

1746 posts

oVlad

#22 h Oct 23, 2021, 7:49 AM • 2 Y

Y by Chikara, Incentivized

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1939 posts

cj13609517288

#23 h Jun 11, 2022, 9:01 PM • 1 Y

Y by spiritshine1234

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}}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1780 posts

awesomeming327.

#24 h Jul 24, 2022, 2:55 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7584 posts

asdf334

#25 h Aug 1, 2022, 3:05 AM • 1 Y

Y by AnikaMehta

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

metricpaper

54 posts

metricpaper

#26 h Aug 4, 2022, 10:32 PM • 3 Y

Y by Mango247, Mango247, Mango247

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5006 posts

IAmTheHazard

#27 h Sep 14, 2022, 3:44 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4192 posts

john0512

#29 h Jan 3, 2023, 11:39 PM • 2 Y

Y by fuzimiao2013, Mango247

(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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

481 posts

kamatadu

#30 h May 3, 2023, 7:33 AM • 1 Y

Y by HoripodoKrishno

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$ .

Now for $\textbf{part (b)}$ , fakesolve part.

Thanks to @a_n for pointing out where I went wrong :-D

This post has been edited 3 times. Last edited by kamatadu, May 9, 2023, 6:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

monval

221 posts

monval

#31 h Jun 24, 2023, 1:47 AM

Y by

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

miguel00

601 posts

miguel00

#33 h Jul 18, 2023, 4:28 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1591 posts

YaoAOPS

#35 h Aug 17, 2023, 4:16 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

129 posts

abeot

#36 h Nov 27, 2023, 3:19 PM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5685 posts

megarnie

#37 h Feb 20, 2024, 2:27 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sansgankrsngupta

160 posts

sansgankrsngupta

#38 h Nov 13, 2024, 7:19 AM

Y by

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)

This post has been edited 1 time. Last edited by sansgankrsngupta, Nov 13, 2024, 7:37 AM
Reason: -

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

587 posts

Maximilian113

#39 h Feb 25, 2025, 7:22 PM

Y by

A) Suppose that $m, n \in \mathbb N$ are relatively prime. Then note that $\gcd(k, mn) = \gcd(k, m) \gcd(k, n).$ Suppose that $k \equiv p \pmod m, k \equiv q \pmod n.$ Then by the Euclidean Algorithm $\gcd(k, mn) = \gcd(p, m)\gcd(q, n)$ so there is a bijection between each term $\gcd(k, mn)$ to $\gcd(p, m)\gcd(q, n)$ by the Chinese Remainder Theorem. Hence $f(m, n) = \sum_{1 \leq p \leq m, 1 \leq q \leq n} \gcd(k, p) \cdot \gcd(k, q) = f(m)f(n),$ so we are done.

B) It suffices to show that $g(x)=f(x)/x$ is surjective over $\mathbb N.$ Observe that $g(x)$ is weakly multiplicative, so we wish to show that $g(x) = p^r$ always has a solution in $x$ for some prime $p$ and positive integer $r.$ Note that in general to calculate $f(p^r),$ in the sum $1$ is generated $\phi(p^r)$ times, $p$ is found $\phi(p^{r-1})$ times, and in general $p^k$ is generated $\phi(p^{r-k})$ times for each $0 \leq k \leq r.$ Therefore $f(p^r) = p^{r-1}(p-1) \cdot p^0+p^{r-2}(p-1) \cdot p^1 + \cdots + p(p-1)p^{r-2}+(p-1)p^{r-1} + p^r = rp^{r-1}(p-1)+p^r.$ So, $g(p^r) = r \left(1-\frac{1}{p} \right) + 1.$ Thus letting $r = \frac{p(p^k-1)}{p-1}$ yields $p^k,$ so $g(x)$ can attain all prime powers. But because it is multiplicative it follows that $g(x)$ can attain all natural numbers, so we are done.

C) Using the above formula for $g(p^r),$ we have that $g(2^r) = \frac{r}{2}+1.$ Therefore $g(2^{2k-2}) = k.$ It thus follows that for each $a$ not a power of $2,$ $g(x)=a$ has at least two solutions, $x=2^{2a-2}$ and $x = \displaystyle \prod_{p^k | a} p^{\frac{p(p^k-1)}{p-1}}.$

We now show that for $a=2^k$ the equation $g(x)=a$ has a unique solution. Suppose $x$ is a solution. Then for each prime power $p^r | x,$ with $r$ maximized, by multiplicativity $g(p^r) = 2^\ell$ for some positive integer $\ell$ ( $\ell \neq 0$ as the only solution to $g(x)=1$ is $x=1$ by size). Hence $r \left(1-\frac{1}{p} \right) + 1 = 2^\ell \iff (2^\ell-1)p=r(p-1).$ If $p$ is odd we have a contradiction as the LHS is odd while the RHS is even, hence $p=2.$ So, $x=2^r$ is necessary and from above we find that $r=\frac{p(p^\ell-1)}{p-1}$ is the only possible $r.$ Therefore only $a=2^k$ works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

253 posts

pie854

#40 h Mar 7, 2025, 6:31 PM

Y by

Note that $f(n)=\sum_{d\mid n} d \phi \left (\frac nd\right )$ . So $f$ is the dirichlet convolution of the identity function and $\phi$ , and is thus multiplicative. This proves (a).

We have $f(p^n)=\sum_{d\mid p^n} d \phi \left (\frac {p^n}d\right )=p^n \phi(1)+p^{n-1}\phi(p)+p^{n-2}\phi(p^2)+\dots+p^{n-n}\phi(p^n)=p^n+n \cdot p^{n-1}(p-1)=p^{n-1}(p+n(p-1)).$ In particular, this implies that $f(4^{n-1})=4^{n-1}n$ for every $n\geq 1$ . This proves (b).

Suppose $a$ is not a power of $2$ . Let $a=\prod p_i^{k_i}$ , where $p_i$ are primes. Now take $n=\prod p_i^{l_i}$ where $l_i=\frac{p_i^{k_i+1}-p_i}{p_i-1}$ . Then, $\frac{f(n)}n=\prod \frac{f(p_i^{l_i})}{p_i^{l_i}}=\prod \frac{p_i+l_i(p_i-1)}{p_i}=\prod \frac{p_i+(p_i^{k_i+1}-p_i)}{p_i}=\prod p_i^{k_i}.$ So $a=\frac{f(4^{a-1})}{4^{a-1}}=\frac{f(n)}n$ and thus non powers of $2$ don't work for (c).

Suppose $2^q=f(n)/n$ for some $q\geq 0$ . Let $n=2^k p_1^{k_1}\cdots p_l^{k_l}$ . It's easy to get that $k=2^{q+1}t-2$ for some $t\geq 1$ . But then we find that $t\prod_{i=1}^l \frac{p_i+k_i(p_i-1)}{p_i}=1,$ which is a contradiction since $\frac{p_i+k_i(p_i-1)}{p_i}>1$ if $k_i>0$ . Thus, $n$ must be a power of $2$ . Hence only powers of $2$ work for (c).

This post has been edited 1 time. Last edited by pie854, Mar 7, 2025, 7:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1347 posts

ezpotd

#41 h May 31, 2025, 12:28 PM

Y by

a) We have $\gcd(k_1, m)\gcd(k_2, n) = \gcd(k_1n ,m) \gcd(k_2m, n) = \gcd(k_1n + k_2m, m) \gcd(k_1n + k_2m, n) = \gcd(k_1n + k_2m, mn)$ . Thus $f(m)f(n) = \sum_{i,j} \gcd(mi + nj, mn)$ , the latter summation has $mn$ terms, and $mi_1 + nj_1 \equiv mi_2 + nj_2 \pmod {mn} \rightarrow i_1 \equiv i_2 \pmod n, j_1 \equiv j_2 \pmod m$ , so all the terms $mi + nj$ are distinct mod $mn$ , so the summation is just $f(mn)$ .

b) Since $f$ is multiplicative over relatively prime $m,n$ , so $\frac{f(m)}{m}$ .For prime power $p^k$ , we have $f(p^k) = 1 \cdot (p^k - p^{k - 1}) + p (p^{k - 1} - p^{k - 2}) + \cdots p^{k - 1} (p - 1) + p^{k} = k(p - 1)p^{k - 1} + p^k$ , so $\frac{f(p^k)}{p^k} = 1 + \frac{k(p -1)}{p}$ . Taking $p = 2$ , we have $f(2^k) = 1 + \frac k2$ , so we can clearly find solutions for any $a$ .

c) The answer is only powers of $2$ . We see that the product of the expressions of the form $\frac{f(p^k)}{p^k}$ for odd $p$ has $\nu_2$ equal to $0$ (observe $k(p - 1) + p, p$ are both always odd), since it is greater than $1$ it cannot be included in our product, thus any $x$ satisfying $\frac{f(x)}{x} = a$ must be a power of $2$ , from which it is then fixed. To show everything else works, we can take the one obvious representation using powers of $2$ , then divide out any odd prime using the fact that $\frac{f(p^p)}{p^p} = p$ , then use powers of $2$ again.

Z K Y

N Quick Reply