The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [multiplicative-function]

This tag is for questions relating to multiplicative functions which are arise most commonly in the field of number theory.

Filter by
Sorted by
Tagged with
0
votes
0answers
55 views

How do I use something related to mobius inversion to solve this problem?

The problem is given below: For two sequences of complex numbers $\{a_0, a_1, \cdots, a_n, \cdots\}$ and $\{b_0, b_1, \cdots, b_n, \cdots\}$ show that the following relations are equivalent: $$a_n = \...
6
votes
1answer
133 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

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 $mn$ is a perfect cube. Prove ...
0
votes
1answer
90 views

Proof of inequality involving multiplicative function?

The identity below seems true for the examples I've considered. I thought I had proven it using induction but found a mistake and removed my attempted proof since it is not helpful. Given: $P(z)$ is ...
1
vote
0answers
47 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 ...
3
votes
1answer
70 views

Hints to compute if exists $\lim_{n\to\infty}\sum_{k=1}^n\sigma(k^2)/\sum_{k=1}^n\sigma(k)$, which $\sigma(n)=\sum_{d\mid n}d$, and other question

I would like receive hints at least for one of the following problems, these are going from experiments. Can you provide to me hints for at least one of the following problems? I will try put the ...
-1
votes
1answer
54 views

Counting divisors of a number

Let m be any positive integer and consider $\Sigma_{d|m} \frac{1}{d} $. I wish to ask whether there is a closed form expression for the above sum.
5
votes
1answer
137 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, $$\mathrm{rad}(...
0
votes
7answers
155 views

How to compute $8x \equiv 33 \pmod{35}$?

How to compute $8x \equiv 33 \pmod{35}$? I followed this video to solve this problem. Is there a better way? My solution steps: Divide both sides by 8: $$x \equiv \frac{33}{8}^{-1} \pmod{35}$$ $$...
14
votes
3answers
332 views

Series of the totient function

Good morning, I wonder if : $$\sum_{n} \frac{(-1)^n}{\varphi (n)}$$ converges or not. where $\varphi (n)$ is the Euler function. Do you have any idea ?
0
votes
1answer
66 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 ...
1
vote
1answer
77 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
1answer
238 views

Determine if $f(n) = n+k$ is completely multiplicative, multiplicative or neither.

Question Determine if $f(n) = n+k$ (k is a fixed real number) are completely multiplicative, multiplicative or neither. Attempted solution The only background I have at this point are (1) the ...
4
votes
1answer
67 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 ...
1
vote
1answer
98 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 ...
6
votes
1answer
299 views

Average order of $\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, $$\mathrm{rad}(n)=\prod_{\scriptstyle p\mid n\atop p\text{ ...
2
votes
1answer
124 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} \sigma(mn)=\sigma(m)\...
0
votes
4answers
2k 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
1k views

Number theory proof for why $\tau$, the number of divisors of $n$ is multiplicative [closed]

Could someone please help me with a proof as to why $\tau$ is multiplicative?
1
vote
1answer
28 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.
7
votes
1answer
250 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
152 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 ...
3
votes
2answers
255 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
85 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
78 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
173 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 ...
6
votes
1answer
574 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: (1)$\...
0
votes
2answers
90 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 ...
22
votes
2answers
859 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
115 views

If a function $f$ is multiplicative, how do I show that $\sum_{d\mid n} \mu(n/d) f(d)$ is also multiplicative?

I am studying A Classical Introduction to Modern Number Theory by Ireland and Rosen, and this is exercise 9 from chapter 2. The authors define a function $f$ to be multiplicative if for all $a, b$ ...
0
votes
1answer
75 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
2answers
344 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 ...
2
votes
2answers
1k 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
140 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, \...
0
votes
2answers
156 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
2k 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: ...
9
votes
1answer
407 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 m}\left(p-...
0
votes
3answers
86 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. ...
2
votes
0answers
345 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} \bigg)^...
1
vote
1answer
245 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
1answer
554 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_1) + f(d_2) +...+f(d_r)$, where $d_1, d_2,...,d_r$ are divisors of $n$. Prove that $g(n)$ is a ...
18
votes
5answers
6k 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 ...
0
votes
1answer
44 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
30 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 + \large\...
0
votes
1answer
649 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 S_1$...
0
votes
1answer
28 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
204 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 it ...
4
votes
1answer
154 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
6
votes
2answers
883 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 ...
8
votes
3answers
910 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) + \sigma(p^2) +...
3
votes
2answers
1k 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 ...