Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...
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}\...
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 ...
3
votes
3answers
361 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 $\...
13
votes
1answer
886 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 ...
22
votes
2answers
837 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 ...
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
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^...
6
votes
1answer
543 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)$\...
5
votes
1answer
315 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} \...
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 ...
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$ ...
8
votes
3answers
866 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) +...
1
vote
1answer
73 views

Optimal multiplying method

Karatsuba gave the optimal way for multiplying two polynomials of degree 1. He reduced the number of multiplications from 4 to 3. Let the imput for $f$ be the degree of a polynomial and the output ...
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$ ?
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 ...
6
votes
2answers
842 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
2answers
360 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
2answers
173 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 ...
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-...
2
votes
1answer
106 views

How to reformulate a multiplicative formula (with two primes, perhaps like totient-function)?

In the work on another question in MSE I have a formula $f(n)$ whose pattern depending on $n \in \Bbb N$ I want decode into an algebraical formula (see a short rationale of $f(n) at the end). ...
2
votes
2answers
784 views

Showing $\sum_{d\mid n} \mu(d)\tau(n/d)=1$ and $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$ [closed]

Need some help on this question from Victor Shoup Let $\tau(n)$ be the number of positive divisors of $n$. Show that: $\sum_{d\mid n} \mu(d)\tau(n/d)=1$; $\sum_{d\mid n} \mu(d)\tau(d)=(-1)...
0
votes
1answer
163 views

Does the Mobius Inversion Theorem hold when sum function is over multiples instead of divisors

Does the Mobius Inversion Theorem hold when the sum function is over multiples instead of divisors. Formally, are the following two expressions equivalent: $$ f(n) = \sum_{k:n|k}h(k) * \mu\left(\...
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) $$=\...
1
vote
2answers
492 views

Dirichlet Convolution of the Mobius Function with Itself

I am attempting to find a formula for $$(\mu * \mu)(n)$$ where * represents the Dirichlet Convolution operator. I know this can be expressed as $$\sum_{d|n} \mu(d)\mu(\frac{n}{d})$$ but I'd like the ...
0
votes
1answer
229 views

The group of number theoretic functions

Let $(G,*)$ be the group of number theoretic functions $f$ with $f(1)\not =0$. 1)Show that if $f$ is a multiplicative function and $f$ is not identically zero, then $f\in G$. 2) Show that the ...
0
votes
2answers
266 views

Multiplicative inverse of polynomial

Question: Determine the multiplicative inverse of $x^2 + 1$ in $GF(2^4)$ with $$m(x) = x^4 + x + 1.$$ My confusion is over the $GF (2^4)$.