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

0
votes
2answers
51 views

Proving that a summation is multiplicative

I have been give a project for number theory: For $m>0$ , let $f(m) = \sum_{r=1}^m \frac{m}{\gcd(m,r)}$ . Evaluate $f(m)$ in terms of the prime factorization of $m$. So far, I have found a formula ...
2
votes
1answer
27 views

Multiplying fractions with an x value

$\left(\sqrt{4+\frac{1}{x}}-2 \right) \cdot \left(\sqrt{4+\frac{1}{x}}+2\right)$ I get $\large\frac{1}{x}$ because the square roots go away and the $2$s multiply to make $-4$, so it's: $4 + ...
1
vote
1answer
24 views

$a\cdot(b^{-1}\bmod m)$ Can be be solved using modular multiplication

Does $a\cdot(b^{-1}\bmod m) = (a\bmod m) \cdot(b^{-1}\bmod m).$ where $\bmod$ represents remainder left on division with $m$. $b^{-1} \bmod m$ is multiplicative inverse.
1
vote
1answer
101 views

Prove $\lambda(n)=\sum_{d^2|n}\mu(n/d)^2$ and $\mu^2(n)=\sum_{d^2|n}\mu(d)$

$\lambda(n)$= $\sum_{d^2|n}$ $\mu(n/d)^2$ and $\mu^2(n)$= $\sum_{d^2|n}$ $\mu(d)$ Having a little bit of trouble here.Can I use the fact that $\sum_{d|n}\lambda(n)$ is a characteristic function for ...
0
votes
1answer
26 views

Number of zeros of a polynomial modulo n is a multiplicative function

Let $f$ be a polynomial with integer coeffcients. For $n\geq1$ let $N_f(n)$ denote the number of pairwise incongruent solutions of $f(x)=0$ mod n. I need help proving that $f$ is a multiplicative ...
0
votes
1answer
147 views

Euler-Totient Multiplicative

http://www.oxfordmathcenter.com/drupal7/node/172 By and large, I understand this proof, however I'm struggling to understand how the Chinese remainder theorem implies that there exists some $x \in ...
0
votes
1answer
33 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 ...
3
votes
0answers
42 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
59 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
236 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 ...
1
vote
0answers
32 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 ...
1
vote
0answers
34 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
0answers
27 views

Over what subset of $\mathbb{N}$ is the deficiency $D(x) = 2x - \sigma(x)$ a weakly multiplicative function?

This is an offshoot of this MSE question which was posted earlier today. Let $\mathbb{N}$ be the set of natural numbers (i.e., positive integers). We call $\sigma(x)$ the sum of the divisors of $x$. ...
1
vote
0answers
61 views

sum of divisors function $\sum \tau(n) = \frac{1}{4}$

These notes on multiplicative number theory mention the convolution $ 1 \ast 1 = \tau$ (where $\tau$ is the divisor function not Ramanujan tau function. Therefore $$ \bigg(\sum \frac{1}{n^s} ...
1
vote
0answers
391 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 ...
0
votes
0answers
9 views

Lagarias and Robin theorems versus multiplicative property

If I use for example Robin's theorem, see here in the section Growth of arithmetic functions, or Lagarias equivalence, see (5) here has sense ask us what is the more sharp inequality for ...
0
votes
0answers
23 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 ...
0
votes
0answers
38 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
0answers
109 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 ...