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
0answers
19 views

Composition of polynomial and multiplicative is multiplicative .

I made the following problem a while ago but I can't solve it (also I don't think it's extremely hard ) : Let $f$ be a non-constant completely multiplicative function over $\mathbb{Z}$ . Assume ...
1
vote
1answer
43 views

If $\varphi(mn)=\lambda \varphi(m)\varphi(n)$ what should be written for $\lambda$

Respected All. I am studying number theory where I came to know that $\varphi(n), \sigma(n)$ both are multiplicative function ; In other words, if $(m,n)=1$ then \begin{align} ...
-1
votes
4answers
160 views

How can I find The Multiplicative Inverse of $1+\sqrt{2}$? [closed]

I am doing contemporary abstract algebra and am working in an integral domain. I have found it necessary to compute the multiplicative inverse of $1+\sqrt{2}$; I know such the definition of a ...
0
votes
2answers
62 views
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.
5
votes
0answers
177 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$ ...
4
votes
1answer
126 views

Writing product $\prod_{i=1}^m (p_i^{n_i}-1)$ as a sum

Suppose I have an integer $N$ with prime decomposition $N=\prod_{i=1}^m p_i^{n_i}$. How can I write $$\prod_{i=1}^m (p_i^{n_i}-1)$$ as a sum that only depends on $N$, and not it's prime ...
2
votes
2answers
83 views

Proof to a property of Euler's totient function

The property is $$\sum_{d|n}\phi(d) = n$$ And the proof provided is If $d$ divides $n$, let $C_d$ be the unique subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d$, and let $\Phi_d$ be the set of ...
1
vote
1answer
59 views

Proving that $f$ is differentiable at $0$

Let's consider the following function: $$f(x,y)=\begin{cases} (x^2+y^2)\sin\left(\dfrac{1}{x^2+y^2}\right) & \text{if }x^2+y^2\not=0 \\{}\\ 0 & \text{if }x=y=0 \end{cases}$$ I know that ...
1
vote
1answer
34 views

Number theoretic function related to totient

I'm doing an excercise in Alan Baker's book A Concise Introduction to the Theory of Numbers, and I'm confused about the method spelled out for one question. I'll quote it here: Let $a$ run through ...
1
vote
1answer
33 views

Prove that $f$ is a multiplicative function and calculate the Summatory Function

Define $f(n)$ as $1$ if $n$ is odd, and $3$ if $n$ is even. So i have $f(odd) = 1$ and $f(even) = 3$ If a function $f$ is multiplicative then if $gcd(m,n) = 1$ then $f(m * n) = f(m) * f(n)$ This ...
4
votes
1answer
135 views

Euler's totient and divisors count function relationship when $[(\frac{\varphi(n)}{2}+1)\cdot(\frac{\tau(n)}{2}+1)] = n$

I am studying the Euler's totient function $\varphi(n)$ and the divisors count function, $\tau(n)$, also named $d(n)$, and recently opened a question (link here) about the following condition: ...
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 ...
15
votes
2answers
454 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
0
votes
1answer
33 views

formula for the number of perfect squares mod $N$

In a numerical experiment I notice for sum moduli $N$ there are much less than $N/2$ perfect squares. I had chosen a large number, the simplest example is $N=8$. Using the Chinese Remainder Theorem ...
3
votes
1answer
58 views

Convolution identity involving the Möbius function $\sum_{d|n,d>0} |\mu(d)| = 2^{\omega(n)}$

I'm learning about the Möbius Inversion Formula but I'm stuck on an exercise which involves the Möbius function. Let $n\in\mathbb{Z}$ with $n>0$ and let $\omega(n)$ denote the number of distinct ...
0
votes
2answers
138 views

new addition and new multiplication x ⊕ y = x + y − 1, x ⊗ y = x + y − xy on set Z, prove the set Z equipped with these 2 new operation

here says a new operation addition and new operation multiplication x ⊕ y = x + y − 1, x ⊗ y = x + y − xy on set Z,where the operations on the right hand side are ordinary addition and multiplication ...
2
votes
1answer
42 views

Möbius function on a finite poset (X, $\leq$)

I'm having some difficulties with the following problem: Give an example of a finite poset $(X, \leq)$ and elements $a,b \in$ X such that $\mu(a,b)=-4$ where $\mu$ is the Möbius function of $(X, ...
-1
votes
2answers
76 views

Why is this expression returning NaN? [closed]

For smoother ship movement, I am going to gradually move it to it's actual location - So like this: (mz - sz) / (10 * (60 / TerrainDemo.FPS)) mz is the ship's ...
0
votes
1answer
203 views

Grade School Multiplication Algorithm for Binary Numbers explanation

I under stand the shifting but not why it will always give the right answer? For Example: ...
8
votes
1answer
302 views

Identity in Number Theory Paper

In this paper by Jerry Hu, he defines the function $$f_{s,k,i}\left(u\right)=\prod_{p\mid u} \left(1-\frac{\sum_{m=i}^{k-1}{s \choose m}\left(p-1\right)^{k-1-m}}{\sum_{m=0}^{k-1}{s \choose ...
0
votes
3answers
62 views

Why is 15 + 15 different from 15 * 2?

(Apologies if the tag is incorrect. I can't find a "Multiplication" tag or similar) I'm going to be adding a set of 5 numbers up and dividing them to get the average for a java game I am making. ...
0
votes
0answers
42 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
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
29 views

Prove that $g(n)$ is a multiplicative function as well

Suppose that $f(n)$ is any multiplicative function , and define a new function as $g(n) = f(d_2) + f(d_2) -...+f(d_r)$, where $d_1, d_2,...,d_r$ are divisors of $n$. Prove that $g(n)$ is a ...
11
votes
3answers
666 views

Very elementary proof of that Euler's totient function is multiplicative

Well, I know two or three proofs of this fact $$\gcd(m,n)=1\implies \varphi(mn)=\varphi(m)\varphi(n)$$ where $\varphi$ is the totient function. My problem is this: I'd like to explain this to some ...
1
vote
1answer
49 views

Summation of multiplicative function $f$ where $f(p) = 1$ for $p$ prime

I have a multiplicative function $f$ with a special "base" case: For every prime $p$, $f(p) = 1$. E.g. splitting up $f(3^5 \times7^2 \times 13 \times 17)$ yields $f(3^5) f(7^2)$ which is left to be ...
0
votes
1answer
29 views

Simple act practice test problem

I am going through an act practice test and I came to a problem that said. Which of the following is equal to the product of x and the square of its reciprocal for all x < 0. My first step ...
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 + ...
0
votes
1answer
100 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
24 views

How to show that

If $f$ is a multiplicative function proof that: i) $f^{-1}(p^{2})= [f(p)]^{2}-f(p^{2})$ ii) $f$ is completely multiplicative $\Longleftrightarrow f^{-1}(p^{\alpha}) = 0; \forall p $ prime $\alpha ...
3
votes
0answers
96 views

Show that the phi function is multiplicative $\phi(mn) = \phi(m)\phi(n)$ [duplicate]

Show that the phi function is multiplicative $$\phi(mn) = \phi(m)\phi(n)$$ Any nice way to prove this without using induction ? The textbook proof looks bit awkward to me, so I am trying to see if ...
4
votes
1answer
113 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
5
votes
2answers
124 views

Prove that $\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)$

How can I prove: $$\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)?$$ Few observations : Left side is a sum function and the right side is a number of divisors function. Both the sides ...
7
votes
3answers
110 views

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ My try : Left hand side : $\begin{align} \sum_{d|p^k}\sigma (d) &= \sigma(p^0) + \sigma(p^1) + ...
3
votes
1answer
214 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
2
votes
1answer
140 views

suppose $\omega(n)$ denote the number of distinct prime factors of n

Suppose $\omega(n)$ denote the number of distinct prime factors of n. Prove that$$|\mu(n)|=\sum_{d|n}\mu(d)*2^{\omega(n/d)}$$ Can any one give me some hints about this problem? Is $\mu(n)$ a ...
5
votes
2answers
95 views

Prove $\sum_{k\mid n}{\mu(k)d(k)}=(-1)^{\omega{(n)}}$

I have the following exercise. I am supposed to show that for all natural numbers $n$, that the following equality holds $$\sum_{d|n}{\mu{(d)}d(d)}=(-1)^{\omega{(n)}}$$ Where $\mu$ is the Mobius ...
1
vote
0answers
23 views

An inequality involving Möbius function [duplicate]

For any positive integer $n$ show the inequality holds : $$\left|\sum_{i=1}^{n}\frac{\mu(i)}{i}\right|\le 1$$ I tried induction. when $\mu(n+1)=0$ it is trivial. But what if $\mu(n+1)\ne 0$? I am ...
2
votes
2answers
114 views

The multiplicative property of cofactor matrices

In this question, we just consider square matrices. The cofactor matrix $\mathrm{C}(\mathrm{A}) = (c_{ij})$ of a $n$-by-$n$ matrix $\mathrm{A} = (a_{ij})$ is a $n$-by-$n$ matrix ($n > 0$) with ...
6
votes
6answers
773 views

Why doesn't $255 \times 255 \times 255 = 16777215$

Ok, I obviously understand basic multiplication and understand why those don't equal. But in web colors, therr is FFFFFF hexadecimal different colors (or rather $16,777,215$ in base $10$). This amount ...
10
votes
1answer
415 views

A unsolved puzzle from Number Theory/ Functional inequalities

The function $g:[0,1]\to[0,1]$ is continuously differentiable and increasing. Also, $g(0)=0$ and $g(1)=1$. Continuity and differentiability of higher orders can be assumed if necessary. The ...
0
votes
1answer
39 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}\\ ...
3
votes
0answers
54 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$. ...
1
vote
4answers
53 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
60 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 ...
3
votes
2answers
78 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
51 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 ...
5
votes
1answer
73 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
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 ...