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.

0
votes
0answers
50 views

A strange multiplicative function

I have a function that looks like $$f_n(i) = \max\left(\left\lfloor \frac{i-n}{2} \right \rfloor + 1, 0\right)$$ and I would like to write it as a nice arithmetic function. To give an idea, another ...
2
votes
2answers
88 views

Sum of divisors, a congruence

Let $\sigma_r(n)=\sum_{d|n}d^r$ where the sum is over all the integers $d=1,\dots,n$ which divide $n$. I am conjecturing $$\sum_{m=1}^{p-1}m^2 \sigma_3(m)\sigma_3(p-m)\not\equiv 0\pmod{p^2}$$ for ...
0
votes
2answers
107 views

Multiplicative Functions and Totient Function

I have two questions. If $f$(n) is a multiplicative function defined on the positive integers, is $g(n)=$$\frac{f(n)}{n}$ multiplicative as well? I think the answer is yes, but I don't know how ...
2
votes
1answer
95 views

Does $\sigma(\frac{m}{n})=\frac{\sigma(m)}{\sigma(n)}$ where $\sigma$ is the sum of divisor function?

My question is the same as with the title. Kindly help me prove the statement below if it is true. What I tried: For specific value of $m$ and $n$ the equality seems to hold. Does $\sigma(\frac{m}{...
1
vote
1answer
64 views

Two Dirichlet characters $\chi$, $\chi'$ are equal if $\chi(p) = \chi'(p)$ for almost all primes

I want to prove the following: Let $\chi, \chi'$ be two primitive Dirichlet-characters of conductor $N$. Suppose that $\chi(p) = \chi'(p)$ for all but a finite number of primes $p$. Then $\chi = \chi'$...
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 ...
1
vote
1answer
143 views

Let $k$ be a fixed positive integer. Prove $f(n)=gcd(n,k)$ is multiplicative.

This is what I have to far... Let $f(x)=g \implies gcd(x,k)=g$ We can then write, $ax+bk=g$ Let $f(y)=h \implies gcd(y,k)=h$ We can write, $cy+dk=h$ Multiplying, $(ax+bk)(cy+dk)=gh$ $\...
0
votes
1answer
33 views

Solve de equation: σ(∅(n))=2^n

Solve de equation: $$\sigma(\phi(n))=2^n$$ I got $$\sigma(n)={2^{n+1}}$$ Then, if $n=p^a$, $$\sigma(n)=\frac{{p^{a+1}}-1}{p-1}={2^{n+1}}$$ Then I got stuck... I don't know how to find this prime, I ...
0
votes
1answer
51 views

Number Theory problem [closed]

Prove that if $n \equiv 23 \pmod{24}$ then $\sigma (n) \equiv0\pmod{24}$.
0
votes
0answers
177 views

Showing a nonzero multiplicative arithmetic function satisfies $f(1) = 1$

let $f$ be multiplicative arithmetic function. if there exist a positive integer $n$ such that $f(n)$ is not equal to $0$ (so $f$ is not identically zero) prove that $f(1)=1$. I got that $gcd(1,n)=1$ ...
1
vote
2answers
491 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 ...
1
vote
1answer
104 views

Verifying $\mathbb T$ a subgroup of the multiplicative group of non-zero complex numbers

Question: Let $\mathbb T$={$z\in$ $\mathbb Z$ :$\vert z\vert$=$1$}. Verify $\mathbb T$ is a subgroup of the multiplicative group of non-zero complex numbers?I do not know what this type of $\mathbb T$ ...
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'...
1
vote
1answer
195 views

Is every jordan homomorphism a ring homomorphism

Let $A$ and $B$ be Banach algebras. A linear map $\phi: A\longrightarrow B$ is called a Jordan Homomorphism if $\phi(a^2)=\phi(a)^2$ for every $a\in A$. And $\phi$ is a ring Homomorphism if $\phi(ab)=\...
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
1answer
149 views

If $F$ is multiplicative, then show that $f$ is multiplicative (without the Mobius inversion formula)

I have $F(n) = \sum_{d\mid n} f(d)$ where $F$ is multiplicative. I need to prove that $f$ is multiplicative, without the Mobius inversion formula, which is introduced in a later chapter. The ...
0
votes
2answers
432 views

Prove that function is multiplicative [closed]

Prove that if $f(n)$ is multiplicative, so is $g(n) = \sum\limits_{d/n}f(d)$. Any ideas? Thanks
2
votes
0answers
22 views

Relation for multiplicative functions

I have some problems understanding relations between convolutions and Euler product. I want to express as a convolution or an additive formulation for: $$N\varphi(N) \prod_{p | N} (1+p^{-1})$$ ...
2
votes
2answers
782 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)...
2
votes
3answers
158 views

Composition of multiplicative functions which is not multiplicative

A function $f\colon\mathbb N\to\mathbb C$ is called multiplicative if $f(1)=1$ and $$\gcd(a,b)=1 \implies f(ab)=f(a)f(b).$$ It is called completely multiplicative if the equality $f(ab)=f(a)f(b)$ ...
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 ...
2
votes
2answers
112 views

Closed form for $\sum\limits_{d|n}\sigma(d)$?

Is there any closed form for $$\sum\limits_{d|n}\sigma(d)$$? I knew that $\sum\limits_{d|n}1=\sigma(n)$ therefore we must have $\sum\limits_{d|n}\sigma(d)=\sum\limits_{d|n}\sum\limits_{r|d}1$ but how ...
0
votes
1answer
105 views

Dirichlet character modulo $k$

Let $f$ be a completely multiplicative function. If there exists $k$ such that $$f(n+k) = f(n)$$ for any $n \in \mathbb{N}$, then there exists $k_0$ such that $f$ is a Dirichlet character modulo $k_0$....
1
vote
4answers
418 views

Multiplicative Inverse using Fermats theorm

Which of the following is a multiplicative inverse of $11^{23}$ modulo $59$? $11^{21}$ $11^{22}$ $11^{25}$ $11^{35}$ $11^{60}$ I assume that I'm supposed to use Fermat's little theorem in order to ...
2
votes
1answer
439 views

show that $ \sum_{p \leq x} \log p \big( \log x - \log p\big) = O(x) $

Show that: $$ \sum_{p \leq x} \log p \big( \log x - \log p\big) = O(x) $$ This is not an exercise. This is implied in one line of proof by Atle Selberg. Additionally the paper asks to show: $$ \...
0
votes
1answer
45 views

Modular Multiplicative inverse of exact multiples

How to calculate the inverse of $23$ with respect to mod 138. I am having difficulty because $138$ is an exact multiple of $138$. If anybody could help me.
0
votes
3answers
415 views

Example on Euler Totient function

I was given in the exam to calculate $\phi(27)$, so I answered like this as I learned: $\phi(27) = 3^2.3 = (3^2-3^1).(3^1-3^0) = 6-2 = 12$ I got shocked that the answer was supposed to be 18. Can ...
0
votes
1answer
39 views

Is there any way to simplify this function?

Let $\mu(x)$ be the mobius function and $\Lambda(x)$ be the vonmangolt function. $$ f(n) = \sum_{d|n} \mu(d-1)\Lambda(d - 1)$$. Is there a way to simplify or estimate this function. $f(3) = -\log(2)$ ...
4
votes
2answers
349 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 ...
2
votes
1answer
565 views

Show that $f(n) = \gcd(a,n)$ is a multiplicative function [closed]

I want to show that $f(n) = \gcd(a,n)$ where a is any natural number, is a multiplicative function. I know I need to show that $f(mn)=f(n)*f(m)$, but I do not know how to do this.
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(\...
0
votes
3answers
42 views

What is the largest (if any) multiplicative modulo group with all prime elements?

Here's what I've been able to find out so far to address this question: 1) $C^*_2$ = {1}, $C^*_3$ = {1, 2}, $C^*_4$ = {1, 3}, $C^*_6$ = {1, 5}, $C^*_8$ = {1, 3, 5, 7}, and $C^*_{12}$ = {1, 5, 7, 11}, ...
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^...
1
vote
0answers
43 views

Infinite Product for Multiplicative Functions

Do there exist closed form functional representations for the following products?: $$ f(x,\alpha) = \prod_{n=1}^\infty \left( 1 + \alpha (n) \ x^n \right) $$ Where $\alpha$ is some multiplicative ...
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 ...
1
vote
1answer
65 views

Uniqueness of $f( x y - 1) = f(x-1)f(y-1),f(1) = A,f(1+n)>f(n)$?

Let $ f(x)$ be defined for $x \ge 1$ Also it is analytic in $]1,\infty[$. For all integers $n>0$ : $ f(n+1) > f(n) $ $f(1) = A $ where $A$ is an integer $>1$. $f(n)$ is always a positive ...
3
votes
2answers
266 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,...
0
votes
1answer
102 views

Isomorphism between multiplicative group modulo n and that of its factors

I am not entirely sure if this is true, but if it is, I would be done with a very important proof. Let $a$, $b$ and $d$ be pairwise coprime. Prove that: $$|(\mathbb{Z}/ab\mathbb{Z})^*/<d>_{ab}| ...
0
votes
1answer
310 views

A multiplicative property of the Euler totient function $\phi$ [duplicate]

How can I show that if $\gcd(a,b)=d$, then $$ \phi(ab)= {\phi(a) \phi(b) d \over\phi(d)} $$ I know I have to use the fact that $$\phi(m)= m \cdot\prod_{p|m} (1-\frac1p),$$ where the $p$ ranges ...
0
votes
0answers
70 views

Proving the existence of a real number in a finite measure of a translation invariant

Someone please explain this: Presume that for each $x \in \mathbb{R}$ and $A \subseteq \mathbb{R}$, that $x + A = \big\{ x + a \mid a \in A \big\}$. Here, A and x + A are Borel sets for all $x \in \...
0
votes
1answer
50 views

Cardinality of the set of either completely multiplicative or multiplicative functions defined on $\mathbb N$ and which take values in $\mathbb N$

Suppose that $S$ is a set of functions such that $f \in S$ if and only if $f$ is either multiplicative or completely multiplicative and every $f \in S$ is defined on the set of natural numbers and ...
0
votes
0answers
55 views

How do I use something related to mobius inversion to solve this problem?

The problem is given below: For two sequences of complex numbers $\{a_0, a_1, \cdots, a_n, \cdots\}$ and $\{b_0, b_1, \cdots, b_n, \cdots\}$ show that the following relations are equivalent: $$a_n = \...
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 ...
0
votes
1answer
90 views

Proof of inequality involving multiplicative function?

The identity below seems true for the examples I've considered. I thought I had proven it using induction but found a mistake and removed my attempted proof since it is not helpful. Given: $P(z)$ is ...
1
vote
0answers
47 views

Can't find the error with the following sum involving multiplicative functions

I apologize for this question which might be trivial but I'm stuck with this issue and I'm probably doing some mistake over and over again. Here's the framework. Let $f$ and $h$ be two multiplicative ...
3
votes
1answer
67 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 ...
-1
votes
1answer
52 views

Counting divisors of a number

Let m be any positive integer and consider $\Sigma_{d|m} \frac{1}{d} $. I wish to ask whether there is a closed form expression for the above sum.
5
votes
1answer
125 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}(...
0
votes
7answers
153 views

How to compute $8x \equiv 33 \pmod{35}$?

How to compute $8x \equiv 33 \pmod{35}$? I followed this video to solve this problem. Is there a better way? My solution steps: Divide both sides by 8: $$x \equiv \frac{33}{8}^{-1} \pmod{35}$$ $$...
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 ?