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

13
votes
10answers
6k views

What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
13
votes
2answers
346 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 ...
10
votes
3answers
504 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 ...
10
votes
1answer
389 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 ...
8
votes
1answer
294 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 ...
6
votes
6answers
743 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 ...
6
votes
2answers
188 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.
6
votes
1answer
84 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
121 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 ...
5
votes
4answers
490 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) ...
5
votes
1answer
67 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 ...
5
votes
3answers
809 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)}$$
4
votes
4answers
2k 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 ...
4
votes
1answer
102 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
4
votes
2answers
377 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.
4
votes
2answers
79 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 ...
3
votes
2answers
64 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$
3
votes
1answer
180 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 ...
3
votes
2answers
74 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$?
3
votes
1answer
745 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$ is also multiplicative. This is what I have: So, $f(n)$ is multiplicative means that if $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ ...
3
votes
3answers
136 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 ...
3
votes
1answer
39 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 ...
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 ...
3
votes
0answers
47 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
3answers
336 views

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

how to find $$\sum_{d|n}(-1)^{\frac nd}\phi(d)=?$$
2
votes
1answer
71 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 ...
2
votes
2answers
99 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 ...
2
votes
2answers
69 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 ...
2
votes
1answer
37 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, ...
2
votes
0answers
62 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: ...
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 + ...
2
votes
1answer
126 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 ...
2
votes
0answers
207 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
1answer
56 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
26 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
24 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 ...
1
vote
1answer
45 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 ...
1
vote
4answers
51 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 ...
1
vote
1answer
70 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, ...
1
vote
1answer
65 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
343 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
3answers
56 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
2answers
93 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++ ...
0
votes
1answer
137 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: ...
0
votes
2answers
82 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)$.
0
votes
2answers
90 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 ...
0
votes
2answers
62 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 ...
0
votes
1answer
23 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 ...
0
votes
1answer
28 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 ...