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
26 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
23 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
75 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
93 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
28 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 ...
5
votes
0answers
173 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$ ...
3
votes
0answers
53 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$. ...
2
votes
0answers
215 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
358 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
39 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} ...
0
votes
0answers
37 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
87 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 ...