Questions tagged [multiplicative-function]

In number theory, a multiplicative function is a function defined on positive integers such that f(ab)=f(a)f(b) for a,b coprime. E.g. Euler's totient function, sum of divisors and number of divisors are multiplicative functions.

32
votes
14answers
27k views

What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi(AB)=\varphi(A)\varphi(B)$, if $A$ and $B$ are two coprime positive integers? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel ...
22
votes
2answers
840 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
19
votes
5answers
6k views

Very elementary proof of that Euler's totient function is multiplicative

Well, I know two or three proofs of this fact $$\gcd(m,n)=1\implies \varphi(mn)=\varphi(m)\varphi(n)$$ where $\varphi$ is the totient function. My problem is this: I'd like to explain this to some ...
14
votes
3answers
1k views

On the mean value of a multiplicative function: Prove that $\sum\limits_{n\leq x} \frac{n}{\phi(n)} =O(x) $

There is a second part of the problem posted in Proving $ \frac{\sigma(n)}{n} < \frac{n}{\varphi(n)} < \frac{\pi^{2}}{6} \frac{\sigma(n)}{n}$, from Apostol's book, but I can't figure it out. It ...
14
votes
3answers
321 views

Series of the totient function

Good morning, I wonder if : $$\sum_{n} \frac{(-1)^n}{\varphi (n)}$$ converges or not. where $\varphi (n)$ is the Euler function. Do you have any idea ?
13
votes
1answer
890 views

Mean Value of a Multiplicative Function close to $n$ in Terms of the Zeta Function

Let $f(n)$ be a multiplicative function defined by $f(p^a)=p^{a-1}(p+1)$, where $p$ is a prime number. How could I obtain a formula for $$\sum_{n\leq x} f(n)$$ with error term $O(x\log{x})$ and ...
12
votes
3answers
390 views

Some convincing reasoning to show that to prove that Ramanujan tau function is multiplicative is very difficult

I am curious to know (some words or reasoning about how to justify) why to prove that the so-called Ramanujan $\tau$ is a multiplicative function is (was) very difficult. In this Wikipedia is showed ...
11
votes
4answers
2k views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
10
votes
5answers
15k views

How to find the nearest multiple of 16 to my given number n

If I'm given any random $n$ number. What would the algorithm be to find the closest number (that is higher) and a multiple of 16. Example $55$ Closest number would be $64$ Because $16*4=64$ Not $...
10
votes
1answer
645 views

A unsolved puzzle from Number Theory/ Functional inequalities

The function $g:[0,1]\to[0,1]$ is continuously differentiable and increasing. Also, $g(0)=0$ and $g(1)=1$. Continuity and differentiability of higher orders can be assumed if necessary. The ...
9
votes
1answer
406 views

Identity in Number Theory Paper

In this paper by Jerry Hu, he defines the function $$f_{s,k,i}\left(u\right)=\prod_{p\mid u} \left(1-\frac{\sum_{m=i}^{k-1}{s \choose m}\left(p-1\right)^{k-1-m}}{\sum_{m=0}^{k-1}{s \choose m}\left(p-...
8
votes
3answers
869 views

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ My try : Left hand side : $\begin{align} \sum_{d|p^k}\sigma (d) &= \sigma(p^0) + \sigma(p^1) + \sigma(p^2) +...
7
votes
6answers
3k views

Why doesn't $255 \times 255 \times 255 = 16777215$

Ok, I obviously understand basic multiplication and understand why those don't equal. But in web colors, therr is FFFFFF hexadecimal different colors (or rather $16,777,215$ in base $10$). This amount ...
7
votes
2answers
1k views

Asymptotic formula for $\sum_{n\leq x}\mu(n)[x/n]^2$ and the Totient summatory function $\sum_{n\leq x} \phi(n)$

I would like to show (for $x \ge 2$) that $$\sum_{n \le x}\mu(n)\left[\frac{x}{n}\right]^2 = \frac{x^2}{\zeta(2)} + O(x \log(x)).$$ I already have the identity $$\sum_{n \le x}\mu(n)\left[\frac{x}{n}\...
7
votes
4answers
3k views

Proving $ \phi(mn)=\phi(m)\phi(n) \frac k{\phi(k)}$

Suppose $m,n \in \Bbb N$, $k$ is product of all prime number such that divide $m,n$ How to prove that: $$ \phi(mn)=\phi(m)\phi(n) \frac k{\phi(k)}$$
7
votes
1answer
247 views

What is known about these arithmetical functions?

Let $n=\prod_p p^{c_p}$, $N\in \mathbb N$ and $$ \alpha_N(n)=\prod_p p^{c_p \bmod N}. $$ The function $\alpha_N$ is multiplicative since $\alpha_N(n)\alpha_N(m)=\alpha_N(nm)$ for co-prime $n$ and $m$ ...
6
votes
3answers
46 views

Explain why the following is or isn't a multiplicative function.

I'm working through practice problems for my exam in class and I need some help with the following problem: A function $f(n)$ is defined to be the greatest power of $2$ that divides $n$. For ...
6
votes
2answers
844 views

Prove that $\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)$

How can I prove: $$\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)?$$ Few observations : Left side is a sum function and the right side is a number of divisors function. Both the sides ...
6
votes
2answers
235 views

Sum of $n \sigma(n)$

What is known about the asymptotic behavior of $$ -\frac{\pi^2}{18}x^3+\sum_{n\le x}n\sigma(n) ? $$ It seems to be $O(x^{2+\varepsilon})$ but I cannot prove this.
6
votes
1answer
182 views

How prove this $\sum_{t|n}(d(t))^3=\left(\sum_{t|n}d(t)\right)^2$

show that $$\sum_{t|n}(d(t))^3=\left(\sum_{t|n}d(t)\right)^2$$ where $d(n)$ is the number of positive divisors of $n$. see this have simaler $$1^3+2^3+\cdots+n^3=\left(1+2+\cdots+n\right)^2$$ maybe ...
6
votes
2answers
279 views

Dirichlet series associated to squared Möbius

I would like to estimate the Dirichlet series of a multiplicative function. Consider the following: $$\sum_{m \leqslant X} \frac{\mu^2(m)}{m^s}$$ When does it converges when $X$ grows? What is an ...
6
votes
1answer
132 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $mn$ is a perfect cube. Prove ...
6
votes
1answer
122 views

$ g(n)= \sum_{d|n}\frac{\phi(d)}d=?$

how to find: $$f(n)=\sum_{d|n} d \phi(d)=? $$, $$ g(n)= \sum_{d|n}\frac{\phi(d)}d=?$$
6
votes
1answer
544 views

Euler's totient and divisors count function relationship when $[(\frac{\varphi(n)}{2}+1)\cdot(\frac{\tau(n)}{2}+1)] = n$

I am studying the Euler's totient function $\varphi(n)$ and the divisors count function, $\tau(n)$, also named $d(n)$, and recently opened a question (link here) about the following condition: (1)$\...
6
votes
1answer
286 views

$\tau(n)\phi(n)\ge n$

how to prove $\forall n \in \Bbb N$ $$\tau(n)\phi(n)\ge n$$ $\tau(n)$ is number of positive divisor of $n$ my efford: if $n=p$ is prime then $\tau(p)=2,\phi(p)=p-1,2p-2\ge p$ but how prove for ...
5
votes
2answers
125 views

Can $\sigma(p^k)=2^n$ for some $k>1$?

If $k=1$ then the only solutions to $$ \sigma(p^k)=2^n $$ are when $p$ is a Mersenne prime (of course $p$ is restricted to the primes). Is there a solution for larger $k$? It doesn't seem so but I can'...
5
votes
2answers
361 views

Prove $\sum_{k\mid n}{\mu(k)d(k)}=(-1)^{\omega{(n)}}$

I have the following exercise. Show that for all natural numbers $n$, the following equality holds $$\sum_{d|n}{\mu{(d)}d(d)}=(-1)^{\omega{(n)}}$$ Here, $\mu$ is the Möbius function, $d$ ...
5
votes
4answers
2k views

Euler's totient function of 18 - phi(18)

I am trying to find the phi(18). Using an online calculator, it says it is 6 but im getting four. The method I am using is by breaking 18 down into primes and then multiplying the phi(primes) $$=\...
5
votes
3answers
3k views

The sigma function (sum of divisors) multiplicative proof

I am trying to prove that $\sigma(p_1^a\cdot p_2^b) =\sigma(p_1^a)\cdot\sigma(p_2^b)$ where $p_1$ and $p_2$ are prime numbers. We know that $\sigma(p_1^a) = \frac{p_1^{a+1}-1}{p_1-1}$ and $\sigma(p_2^...
5
votes
1answer
279 views

Average order of $\mathrm{rad}(n)$

Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing n. Or equivalently, $$\mathrm{rad}(n)=\prod_{\scriptstyle p\mid n\atop p\text{ ...
5
votes
1answer
126 views

Average Order of $\frac{1}{\mathrm{rad}(n)}$

Again a question about $\mathrm{rad}(n).$ Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing $n$. Or equivalently, $$\mathrm{rad}(...
5
votes
1answer
205 views

To estimate $\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$

How may we estimate $$\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$$ where for every positive integer $m$ , $d(m)$ denotes the number of positive divisors of $m$ ?
5
votes
1answer
316 views

Dirichlet Series and Average Values of Certain Arithmetic Functions

If an arithmetic function $f(n)$ has Dirichlet series $\zeta(s) \prod_{i,j = 1} \frac{\zeta(a_i s)}{\zeta(b_j s)}$, for which values of $a_{i}$ and $b_{j}$ is the following true? That \begin{align} \...
5
votes
1answer
177 views

Bounding this arithmetic sum

I am interesting in bounding the arithmetic sum $$ \sum_{n \leq x} \frac{\mu(n)^2}{\varphi(n)}$$ (The motivation is that this is a sum that comes up a lot in sieving primes, in particular in the ...
5
votes
2answers
174 views

How to show $\sum_{d\mid n} \frac{\mu^2(d)}{d} =\prod_{p|n} \left(1+\frac{1}{p}\right)$?

how to prove: $$\sum_{d\mid n} \frac{\mu^2(d)}{d} =\prod_{p|n} \left(1+\frac{1}{p}\right)$$ $\mu : \Bbb N\rightarrow \Bbb R$ $\mu(1)=1$ $ \mu(n)= \begin{cases} 0 &,\;\;\; \text{if $\,n\,$ is ...
4
votes
1answer
153 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
4
votes
2answers
79 views

how to find $n\in \Bbb N$ such that: $\tau(n)$is odd

how to find $n\in \Bbb N$ such that: $\tau(n)$is odd $\tau(n)$ is number of positive divisor of $n$
4
votes
1answer
2k views

if $f(n)$ is multiplicative prove that $f(n)/n$ is also multiplicative.

The question asks that if $f(n)$ is multiplicative to prove that $f(n)/n\qquad$ is also multiplicative. This is what I have: So, $f(n)\quad$ is multiplicative means that if $p_1^{e_1}p_2^{e_2}\cdots ...
4
votes
2answers
352 views

Formula for square of the number of divisors $\sum_{r\mid n} d(r^2) = d^2(n)$

I am trying to prove or disprove the following statement: $$\sum_{r|n} d(r^2) = d^2(n),$$ where $d$ is the number of divisors function. Computing it for small numbers yields equality, so I at least ...
4
votes
1answer
149 views

Writing product $\prod_{i=1}^m (p_i^{n_i}-1)$ as a sum

Suppose I have an integer $N$ with prime decomposition $N=\prod_{i=1}^m p_i^{n_i}$. How can I write $$\prod_{i=1}^m (p_i^{n_i}-1)$$ as a sum that only depends on $N$, and not it's prime ...
4
votes
1answer
139 views

Closed formula for a multiple Dirichlet convolution of the 1-function with the identity

For two multiplicative arithmetic functions $f,g$ the Dirichlet convolution is defined by $(f\ast g) (n)=\sum\limits_{ab=n}f(a)g(b)$. Convoluting any arithmetic function with the $1$-function ($1(n)=1$...
4
votes
1answer
64 views

A follow-up number-theory question on the deficiency function $D(x) = 2x - \sigma(x)$

This question is a follow-up to these previous posts: MSE1 and MSE2. Let $x, y$ be positive integers. We call $\sigma(x)$ the sum of the divisors of $x$. Let the deficiency function $D(x)$ be ...
4
votes
0answers
146 views

Minimal value of summatory function of completely multiplicative functions taking values -1 and 1

Here is a very nice paper http://www.ams.org/journals/tran/2010-362-12/S0002-9947-2010-05235-3/S0002-9947-2010-05235-3.pdf which led me to thinking about the problems below. Define the Liouville ...
4
votes
0answers
362 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that $f(n)=n$ ...
3
votes
2answers
267 views

Is $\sum_{d | n} f(d)$ completely multiplicative if $f$ is completely multiplicative?

In these excellent notes by Pete L. Clark, it is claimed that if $f(n)$ is a multiplicative function, then $F(n) = \sum_{d|n} f(d)$ is multiplicative as well. I understand the proof of this statement,...
3
votes
1answer
98 views

Let rad(n) = $\Pi_{primes, p|n}$ p.

Let $\operatorname{rad}(n) = \displaystyle\prod_{\stackrel{p|n}{p \text{ prime }}}p$ . I have proven that $\operatorname{rad}(n)$ is a multiplicative arithmetic function. I have also proven that $F(...
3
votes
2answers
67 views

About The Sum of Positive Divisors of $n$

The question says: Find the smallest positive integer $n$ so that $\sigma(x)=n$ has no solution, exactly two solutions, exactly three solutions. I could not come up with a good way to solve this ...
3
votes
2answers
983 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
3
votes
2answers
685 views

Why f(1)=1 for every multiplicative function f?

If $f$ is a multiplicative function with $f(1)\ne0$, then why is $f(1)$ necessarily equal to $1$?
3
votes
3answers
362 views

Prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.

I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$. It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that $\...