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.

1
vote
2answers
98 views
+50

How to prove that the Legendre symbol is multiplicative?

The proof is given here in the answer Proving $(\frac{n}{p})$, a Legendre symbol, is multiplicative But I do not understand it, Also the definition in the book for Legendre symbol says that if $p|a$ ...
2
votes
0answers
25 views

Closed-form for $F(n) = \sum_{d|n} \omega_x(d) $

Given $x\in \mathbb{C}$ let's define the function $$\cases { \omega_x(n)=1, \quad n=1 \\ \omega_x(n)=x^r, \quad n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}}$$ a) Prove that $\omega_x(n) \colon \mathbb{...
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
3answers
44 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 ...
1
vote
1answer
54 views

Multiplicative functions and the sum of all divisors: $\sum_{d\mid2020}{\sigma(d)}$

Doing more practice for my final and I need some help with the following: Evaluate: $$\sum_{d\mid2020}{\sigma(d)}$$ where $\sigma(n)$ is the sum of all divisors of n. The hint given specifically ...
0
votes
0answers
17 views

Multiplicative function evaluated at prime decompositions

Say $f$ is multiplicative and $m = p^{\alpha}q^{\beta}$ where $p,q$ are prime. Then do we have $f(m) = f(p^{\alpha})f(q^{\beta})$? If so why?. I know this hold when the powers are 1 but have not been ...
2
votes
2answers
52 views

Summing a multiplicative function

$f(n)$ is a multiplicative function, meaning $f(m\cdot n)=f(m)\cdot f(n)$. I want to evaluate the sum: $$(1)\qquad\sum_{k=1}^{n}f(m\cdot k)$$ over a fixed $m$. Because $f$ is multiplicative, I can ...
32
votes
14answers
26k 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 ...
2
votes
1answer
35 views

How to generalize Newman's simplification of O-Tauberian theorem?

Can you prove the next theorem: Let $f$ be Dirichlet series with real, positive coefficients $(a_n>0)$. If $f$ is holomorphic on $\Re(z)\ge1$, but has one singularity at $z=1$, then $\lim_\limits{...
2
votes
1answer
58 views

Group automorphism of multiplicative group of real number field

Let $\mathbb{R}$ be the real number field and $\mathbb{R}^{\times}$ be the multiplicative group of it. $\mathrm{Aut}(\mathbb{R}^{\times})$ denotes the group automorphism of $\mathbb{R}^{\times}$. [...
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$ ...
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)...
1
vote
2answers
32 views

Is $n^{(p-1)/2}\equiv -1\pmod p$ implies $n$ is a primitive root modulo $p$?

Let $p$ be an odd prime, $n$ be any integer, if $$n^{(p-1)/2}\equiv -1\pmod p,$$ is it always true that $k=p-1$ is the smallest positive integer satisfy $$n^k\equiv 1\pmod p?$$ This is the little ...
1
vote
1answer
25 views

Proof Verification: Let $f(\chi)$ be the conductor of $\chi$, proof that $f(\chi)=f(\chi_1)\cdots f(\chi_r)$.

This is a detailed problem, let me write down the problem and the process I have done: Assume that $k=k_1k_2\cdots k_r$ where $k_i$ and $k_j$ are relatively prime for $i\neq j$. Let $\chi$ be a ...
2
votes
1answer
44 views

If $(a,k)=(b,m)=1$, prove that $(ab,km)=(a,m)(b,k)$.

I'm reading the proof of the multiplicative property of $$s_k(n)=\sum_{d|(n,k)}f(d)g\bigg( \frac kd\bigg)$$ The book wrote that in order to understand the proof, we need to know if $a,b,k,m$ are ...
2
votes
1answer
65 views

How to multiply the radical expressions and simplify your answer?

I am trying to multiply and simplify the following radical expression. $$(\sqrt{x}+5 - 4)(\sqrt{x}+5+4)$$ According to the book, the answer is $x - 11$ However, I am confused about how this even ...
0
votes
1answer
23 views

If f is multiplicative, then will $f\left(\frac{a}{b}\right)$ be multiplicative for coprime $a,b$?

Given that $a$ and $b$ are coprime integers, i.e $gcd(a,b)=1$ then for any multiplicative function $f$ will $f\left(\frac{a}{b}\right)$ be multiplicative? i.e Will following property hold $$f\left(...
0
votes
1answer
90 views

Since $\zeta(1) \neq 1$, does this mean that $\zeta$ is not multiplicative?

Let $\zeta(s)$ be the Riemann zeta function, that is, $$\zeta(s) = \sum_{n=1}^{\infty}{\frac{1}{n^s}}.$$ A function $g$ is said to be multiplicative if, whenever $\gcd(x,y)=1$, we have $$g(xy) = g(x)...
0
votes
1answer
493 views

How to prove if an arithmetic function is multiplicative?

I know that for an arithmetic function to be multiplicative then $f(nm)=f(n)f(m)$ for $(n,m)=1$ I have just proved that: $$f(n) = \left\{ \begin{array}{l l} 0 & \quad \text{if 10|n}\\ ...
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 $...
-1
votes
2answers
41 views

$f(n) = \Sigma_{d|n} \mu(n/d)F(d)$

The question says: If $F(n) = \Sigma_{d|n} f(d)$ for every positive integer $n$, prove that $f(n) = \Sigma_{d|n} \mu(n/d)F(d)$. What I know so far is that divisors of $n$ can be paired together. ...
3
votes
2answers
65 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 ...
2
votes
1answer
22 views

Cardinality set of multiples

Given an arbitrarily large set of natural numbers greater than one, S = {$p_0$, $p_1$, ... $p_n$} product of S = $\prod_{i=0}^n\ p_i$ define M as the set of all natural numbers that are multiples ...
0
votes
1answer
23 views

How much a variable contributed to the result of some cost function

I have this simple cost function: $\sum_{i=1}^n d_i\times h_i \times a_i$ I wanted to analyze, for example, how much the $a$ component/variable contributed to the final cost function. In other ...
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 ...
2
votes
0answers
65 views

Asymptotic estimate for the sum $\sum_{n\leq X}\mu(n)\tau(n)$?

Just trying to figure out what would be the asymptotic relation for the expression $\sum_{n\leq X}\mu(n)\tau(n)$, where $\tau$ corresponds to the number of divisors function (often named $\sigma_0$ ...
2
votes
1answer
66 views

Modulo Arithmetic: Proof of Basic Property

If a,b,c,k $\in\mathbb{Z\cap{(N\cup{0}})}$ and a$\equiv$b(mod c) then prove that a$^{k}\equiv$b$^{k}$(mod c). I know how to prove it using induction but I wanted to know if there is a method that only ...
2
votes
3answers
89 views

If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ [closed]

If $n$ is a positive integer, let $S(n)$ be the sum of all the positive divisors of $n$. If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ The function $S$ is multiplicative ...
1
vote
2answers
71 views

Is there an analytic proof of change of bases in logarithms?

Usually change of bases in logarithms is just observance $$x=b^{\log_bx}\implies \log_kx={(\log_bx)}{(\log_kb)}\implies \log_kb=\frac{\log_kx}{\log_bx}.$$ Supposing apriori we do not know inverse of ...
1
vote
1answer
42 views

Word to describe factor of x or 1/x

There is a well known video of a helicopter with 5 evenly spaced rotor blades where the rotor is synced with a digital camera's frame rate. Assuming the camera is at 60 hertz (60 frames per second), ...
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 ...
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$ ?
1
vote
1answer
51 views

Upper bound on coefficients of the logarithmic derivative of a certain Dirichlet series

For a multiplicative arithmetic function $f(n)$, we define $ F(s) = \sum_{n\ge1}^{} \dfrac{f(n)}{n^s}$. We then define the coefficients $\Lambda_f (n)$ by $$ -\dfrac{F'(s)}{F(s)} = \sum_{n\ge1}^{} \...
1
vote
1answer
62 views

Landau notation and a preliminary step in the computation of the average order of $\sigma(n)$

My question is to show that for all real numbers $x \ge 2$: $$\sum_{n \le x} \frac {\sigma (n)}{n} = \frac {\pi ^2}{6}x + O(\log x)$$ I think the first step is to break down the sigma function: $$\...
1
vote
2answers
80 views

If $f$ is an arithmetic function with $f(1)=1$ then $f$ is multiplicative

I'm studying analytic number theory for undergraduates and I read this theorem in Tom Apostol's book on the second chapter: Theorem 2.12. If $f$ is multiplicative then $f(1)=1$ And under need ...
1
vote
1answer
74 views

Looking applications for these statements involving multiplicative functions and Euler-Fermat theorem

It is well knwon that for positive integers such that $gcd(a,n)=1$, Euler-Fermat Theorem states than $a^{\phi(n)}\equiv 1 \mod n$, where $\phi(n)$ is the Euler totient function counting positive ...
1
vote
1answer
25 views

$g(m)$ is a multiplicative fuction.

$g(m)=\sum_{n=1, (n,m)=1}^{n=m} e^{2\pi i n /m}$ I tried but didnt able to show it. Also how to show that $g(p)=-1$ for $p$ prime. I tried it just by splitting the series and collecting the terms ...
4
votes
2answers
350 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 ...
12
votes
3answers
389 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 ...
0
votes
1answer
29 views

How to multiply two functions with two variables and manually build a plot

I am trying to learn how to work with functions and I have some things that I didn't fully understand. How do I multiply and plot a function that is the result of a multiplication of two other ...
0
votes
1answer
50 views

Proving that two multiplicative functions are equal

I need to prove the following statement: "Let 'f' and 'g' be two multiplicative functions such that f(pk) = g(pk) for each prime p and k $\geqslant$ 1. Prove that f = g" I have tried to approach ...
0
votes
1answer
57 views

Help in showing that a function is multiplicative

I am solving this same very question: For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ I want to approach this question via proving the multiplicativity of the ...
-4
votes
1answer
44 views

how do I solve this, $\tau(m) = 21$ [closed]

I know how to do this for an even number, but I don't understand how I would do it for an odd number, $\tau (m) = 21$.
0
votes
2answers
215 views

Order of operations for multiplying three matrices

If I have a $1\times 2$ matrix $A$, a $2\times 2$ matrix $B$, and a $2\times 2$ matrix $C$, and am asked to calculate ABC, is there a specific order in which I have to carry out the multiplication? ...
1
vote
3answers
48 views

How to calculate the multiplicator in a sum like sum += sum*(mulu^n)

In a section of a personal PHP project, I would like to calculate the spending factor in a rule where we spend Nth time the previous payment done. Here is an example of spending. ...
1
vote
3answers
200 views

How to do a sum of a function over all divisors of an integer with Maple?

I'd like to define sumdiv in Maple such that this: with(numtheory); f:=x->x^2; sumdiv(f(d)*mobius(100/d), d=1..100); would ...
0
votes
0answers
104 views
2
votes
2answers
93 views

Lower bound for sum of a multiplicative function based on lower bound on value of primes

Let $f$ be a non-negative multiplicative function. Suppose we have some bound on $\sum_{p \le x} f(p)$, where the summation is over primes. Is it possible to give a lower bound on $\sum_{n \le x} f(n)$...
2
votes
3answers
1k views
0
votes
1answer
34 views

Increment in multiplying

I want to calculate the total cost of an investment in a game. For each level, the costs is increased with 5000, i.e. lvl 1 costs 5000, lvl 2 costs 1000 and lvl 3 costs 1500 etc. At level 3, the ...