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.

learn more… | top users | synonyms

18
votes
10answers
10k views

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

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
18
votes
2answers
555 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 ...
14
votes
3answers
249 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
3answers
2k 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 ...
12
votes
3answers
768 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 ...
11
votes
1answer
467 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 ...
8
votes
1answer
385 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 ...
8
votes
1answer
308 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 ...
7
votes
2answers
786 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 ...
7
votes
3answers
170 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) + ...
7
votes
1answer
208 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
6answers
991 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 ...
6
votes
2answers
651 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.
6
votes
2answers
194 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
89 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. ...
6
votes
1answer
104 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
155 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
243 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 ...
5
votes
4answers
741 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
2answers
122 views

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

I have the following exercise. I am supposed to show that for all natural numbers $n$, that the following equality holds $$\sum_{d|n}{\mu{(d)}d(d)}=(-1)^{\omega{(n)}}$$ Where $\mu$ is the Mobius ...
5
votes
1answer
87 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 ...
5
votes
1answer
151 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
3answers
1k 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)}$$
5
votes
2answers
168 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
151 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
1answer
202 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: ...
4
votes
4answers
4k 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 ...
4
votes
1answer
125 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
4
votes
1answer
133 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
77 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 ...
4
votes
1answer
134 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} ...
3
votes
1answer
74 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 ...
3
votes
2answers
69 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$
3
votes
1answer
352 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
100 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
1answer
1k 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$ is also multiplicative. This is what I have: So, $f(n)$ is multiplicative means that if $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ ...
3
votes
3answers
177 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 ...
3
votes
1answer
52 views

Hints to compute if exists $\lim_{n\to\infty}\sum_{k=1}^n\sigma(k^2)/\sum_{k=1}^n\sigma(k)$, which $\sigma(n)=\sum_{d\mid n}d$, and other question

I would like receive hints at least for one of the following problems, these are going from experiments. Can you provide to me hints for at least one of the following problems? I will try put the ...
3
votes
1answer
105 views

Convolution identity involving the Möbius function $\sum_{d|n,d>0} |\mu(d)| = 2^{\omega(n)}$

I'm learning about the Möbius Inversion Formula but I'm stuck on an exercise which involves the Möbius function. Let $n\in\mathbb{Z}$ with $n>0$ and let $\omega(n)$ denote the number of distinct ...
3
votes
2answers
70 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 ...
3
votes
0answers
48 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, ...
3
votes
0answers
105 views

Show that the phi function is multiplicative $\phi(mn) = \phi(m)\phi(n)$ [duplicate]

Show that the phi function is multiplicative $$\phi(mn) = \phi(m)\phi(n)$$ Any nice way to prove this without using induction ? The textbook proof looks bit awkward to me, so I am trying to see if ...
3
votes
0answers
61 views

When is $f(n)=\sum\limits_{d\mid n}\sigma(d)$ prime?

When is $f(n)=\sum\limits_{d\mid n}\sigma(d)$ prime? Note, $f$ is multiplicative and $\sigma(n)>1, \;n>1$. Therefore $f(n)$ is prime only when $n=p^\alpha$, with $p$ prime, $\alpha\geq1$. ...
3
votes
0answers
240 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 ...
2
votes
3answers
439 views

$\sum_{d|n}(-1)^{\frac nd}\phi(d)={}$?

how to find $$\sum_{d|n}(-1)^{\frac nd}\phi(d)=?$$
2
votes
1answer
76 views

If $\varphi(mn)=\lambda \varphi(m)\varphi(n)$ what should be written for $\lambda$

Respected All. I am studying number theory where I came to know that $\varphi(n), \sigma(n)$ both are multiplicative function ; In other words, if $(m,n)=1$ then \begin{align} ...
2
votes
2answers
124 views

The multiplicative property of cofactor matrices

In this question, we just consider square matrices. The cofactor matrix $\mathrm{C}(\mathrm{A}) = (c_{ij})$ of a $n$-by-$n$ matrix $\mathrm{A} = (a_{ij})$ is a $n$-by-$n$ matrix ($n > 0$) with ...
2
votes
2answers
74 views

Orthogonality de Möbius

Does anyone know how prove that $$\sum_{n\leqslant x}\mu(n)\xi(n) =o(x)$$ when $\xi(n)$ is a multiplicative functions? I found one commentary that exist a connection of this problem with the Theory of ...
2
votes
2answers
115 views

Proof to a property of Euler's totient function

The property is $$\sum_{d|n}\phi(d) = n$$ And the proof provided is If $d$ divides $n$, let $C_d$ be the unique subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d$, and let $\Phi_d$ be the set of ...
2
votes
1answer
51 views

Möbius function on a finite poset (X, $\leq$)

I'm having some difficulties with the following problem: Give an example of a finite poset $(X, \leq)$ and elements $a,b \in$ X such that $\mu(a,b)=-4$ where $\mu$ is the Möbius function of $(X, ...