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
4answers
652 views

How to find all elements in Z/80 that have multiplicative inverses.

I need to find all the elements in Z/80 that have multiplicative inverses. Z/80 is not a field, so I know not every element will have an inverse. Is there a shorter way than just writing out the ...
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$...
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$?
0
votes
1answer
218 views

Multiplicative inverses and co-primes

I'm working out some examples on multiplicative inverses. I understand how to solve for a multiplicative inverse using the Extended Euler's algorithm, but I don't understand the principles which ...
6
votes
1answer
183 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 ...
0
votes
0answers
50 views

Summatory Function $F(n) = 1 $ for all $n$ odd, and $F(n) = 2$ for all n even

So, I have this summatory function $$ F(n)=\sum_{d\mid n}f(n)$$ that goes $F(n) = 1$ for $2\nmid n$, and $F(n)=2$ for $2\mid n$. This summatory function is multiplicative. I need to describe the ...
0
votes
1answer
1k views

Prove that if d = gcd(m,n) then $\phi(mn)=\phi(m)*\phi(n)/d$ [duplicate]

So if m and n are relatively prime, then the $\phi(mn)=\phi(m)*\phi(n)$ but what happens when $d > 1$?
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.
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 $\...
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) $$=\...
0
votes
0answers
130 views

Conjecture related to the Erdős discrepancy problem

Conjecture: If $k \in \mathbb{N}$ and $S$ is an infinite set of primes, then the multiplicative $\pm$-sequence generated by $S$ contains $+^k$ as a substring infinitely often. (If $S$ is allowed to ...
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 ...
0
votes
2answers
268 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)$.
1
vote
1answer
959 views

Proof that the euler totient function is multiplicative, correctness?

I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong? Proof: We try to ...
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(...
2
votes
2answers
90 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 ...
0
votes
1answer
229 views

Figuring out a factor of modulo multiplication knowing other factors

So the problem is this - we have a simple equation: (A * B) % N = X All numbers are large integers. We know B, N and X, is it possible for us to figure out the last factor A without checking every ...
0
votes
2answers
114 views

How to calculate $2^{mn-1}/(2^n-1) \bmod{(10^9+7)}$

I was trying to solve Magical Five problem on codeforces. I have correctly formed an equation which I need to solve via program such that resulting number don't overflow. Answer can be Python or C++ ...
5
votes
2answers
175 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 ...
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$ ?
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
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 ...
2
votes
3answers
1k views

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

how to find $$\sum_{d|n}(-1)^{\frac nd}\phi(d)=?$$
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$
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)}$$
0
votes
2answers
150 views

Composing Morphisms with Morphisms

Prove that the result of any such nested composition is independent of the placement of the parentheses. So this is what I have so far. Proof by induction I want to show that for any such choice for ...
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
vote
1answer
109 views

calculating storage based upon on eps?

If an organization collects an average of $20,000$ EPS over eight hours of an ongoing incident, that will require sorting and analysis of $576,000,000$ data records. Using a $300$ byte average size, ...
0
votes
1answer
1k views

inverse,multiplicative inverse and Congruence of a prime field

I am dealing with ECC in these days which heavily based on finite fields. I want to how to find a inverse of a value in finite field and what is multiplicative inverse and also Congruence F29- {0,1,2,...
1
vote
0answers
487 views

Modular multiplicative inverse and coprime numbers needed.

I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
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 ...
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 ...
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.
4
votes
0answers
366 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$ ...
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} \...
13
votes
1answer
892 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 ...
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 ...
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}\...
2
votes
1answer
122 views

Error in Bell series of arithmetic functions

I want to prove that $$\frac{n}{\varphi(n)} = \sum_{d|n} \frac{\mu(d)^2}{\varphi(d)}.$$ First clear denominators to get $$n = \sum_{d|n} \mu(d)^2 \varphi(n/d).$$ Next I replaced $\mu(d)^2$ with $\...