Questions tagged [multiplicative-function]
This tag is for questions relating to multiplicative functions which are arise most commonly in the field of number theory.
249
questions
0
votes
0
answers
56
views
Full derivation inside of twin prime statement in terms of multiplicative arithmetic functions. How can the last formula be rearranged?
Let $(\cdot\mid\cdot) : \Bbb{N}\times\Bbb{N} \to \Bbb{Z}_2$ be the divisibility function which takes on the value $(x|y) = 1$ whenever $x$ divides $y$ and the value $(x|y) = 0$ whenever it does not ...
- 19.5k
0
votes
1
answer
44
views
Continuous Factorial
I am working on a theory of quantum information and am unsure on some of the mathematical formalism I need.
I have learned that integration can be thought of as summing up infinitely thin slices.
My ...
- 227
1
vote
0
answers
37
views
Summatory function of Euler-phi
Let $F(n) = \sum_{d^2|n} \phi(d)$. We must show that if $F(1) = 1$, and if $n>1$ factors as $n=p^{a_1}_1p^{a_2}_2...p^{a_m}_m$, then
$$
F(n)=\prod_{i=1}^{m} p^{[a_i/2]}_i.
$$
If I understood ...
- 11
2
votes
0
answers
78
views
Why did we stop creating functions at exponents?
It seems that every new function is just a function that asks something of the one before it, for example: First we have addition. That is the starting point. Now, multiplication, which asks "How ...
- 29
2
votes
1
answer
30
views
A question about the property of completely multiplicative functions
I am self-studying number theory. In Apostol's number theory textbook, Theorem 2.17 states:
Let $f$ be multiplicative. Then $f$ is completely multiplicative if
and only if $$f^{-1}(n)=\mu(n) f(n) \...
- 790
1
vote
1
answer
37
views
Necessary and sufficient condition to be completely multiplicative
I want to prove that $f*f=f \tau$ iff $f$ is completely multiplicative. The "if" part was relatively easy, using $f(g*h)=(fg)*(fh)$ and plug $g=h=1$ for all $n$.
Juxtaposition is ordinary, ...
- 140
0
votes
2
answers
75
views
Let $f:\Bbb{N}\to\Bbb{C}$ denotes the indicator function of squares. Express it in terms of Mobious function $\mu$.
Here $f(n)=\begin{cases}
1\ \text{if } n=m^2\text{ for some }m\in\Bbb{N}\\
0\ \text{if otherwise}
\end{cases}$
This is a multiplicative function. At first I define $g:\Bbb{N}\to\Bbb{C}$ be $g(n)$ to ...
- 2,397
0
votes
0
answers
62
views
Fast consecutive prime multiplication
Are there any fast algorithms for multiplying consecutive prime numbers? I found this question about a pattern when multiplying consecutive primes. I was wondering if there is a multiplication ...
- 147
3
votes
3
answers
141
views
Why is it important that the $p$-adic absolute value satisfy multiplicativity?
I suppose my question is really "why do we require norms in general to satisfy multiplicativity?". I ask this because for the usual absolute value on $\mathbb R$, I never feel like ...
- 5,824
-2
votes
1
answer
74
views
$f$ is multiplicative $\implies f^{-1}$ is multiplicative. [closed]
Let $f$ be a multiplicative function i.e. $f(mn)=f(m)f(n)$ for all $m,n$ satisfying $\gcd(m,n)=1$ and $f\not\equiv 0$. Define $f^{-1}$ to be the function $g$ such that $f*g=I$ where $I(n)=1$ if $n=1$ ...
- 2,011
2
votes
1
answer
76
views
Find the values of $f(2)$ for which $f$ cannot be a strictly increasing and completely multiplicative function
I was solving some problems on functional equations especially on multiplicative functions today. I noticed that a strictly increasing completely multiplicative function $f:\mathbb N \to\mathbb N$ ...
- 3,823
8
votes
2
answers
226
views
Prove that $f(n)=n^2$ where $f$ is a strictly increasing multiplicative function with $f(2)=4$.
Let $f:\mathbb N\to\mathbb N$ be a strictly increasing function with $f(2)=4$ which is completely multiplicative i.e $f(ab)=f(a)f(b)$ for all $a,b\in\mathbb N$. Prove that $f(n)=n^2$ for all $n\in\...
- 3,823
2
votes
1
answer
76
views
How to prove that a function on a quotient set $\mathbb{Z}/n\mathbb{Z}$ is well defined?
I am asked to prove that a function under a quotient set is well-defined. I know that for a function to be well-defined, two mappings or images found in the co-domain/range can't be mapped from the ...
2
votes
1
answer
56
views
Factorials and Place Value
I recently came across this question from a non-calculator exercise. The units and tens place value digits I can see as $0$ and $0$ since in $12!$ we have $10*5*2=100$ but is there a way to find $a$ ...
- 91
2
votes
1
answer
138
views
How would one motivate/know to introduce the Dirichlet character in the formula for the number of lattice points on a circle of radius $\sqrt N$
Grant's masterful video https://www.youtube.com/watch?v=NaL_Cb42WyY&ab_channel=3Blue1Brown ("Pi hiding in prime regularities") describes a way of computing $\pi$ that ultimately leads us ...
- 5,824
0
votes
0
answers
23
views
Discontinuous multiplicative Linear Functional on a non complete normed Algebra
I have come across the following proposition in the book "Complete Normed Algebras" by F. F. Bonsall and J. Duncan in section 16 on page.
Definition: A multiplicative linear functional on ...
- 1
0
votes
1
answer
92
views
Do these multiplicative functions exist?
I read about the multiplicative function $\mu$ defined by Möbius. Which is for any given $n\in \mathbb{N}$ such as $n=p_1^{\alpha_1}\cdot ....\cdot p_r^{\alpha_r}$ is defined as
$$\mu(n)= \left\{ \...
0
votes
0
answers
24
views
totally multiplicative function
Let $f$ be a totally multiplicative function, $f(n+N)=f(n)$ for every $n \in \mathbb{N}$. Prove that $|f(n)|=1$ for every $n \in \mathbb{N}$, where $gcd(n,N)=1$
My approach is to prime factorise $n+N=\...
- 434
0
votes
1
answer
22
views
Equivalence between convex combination and multiplicative form
I am interested in understanding the relationship between convex combination and a multiplicative form.
Let $x,y > 0$. Let the convex combination be $f(\gamma) = \gamma x + (1-\gamma) y$ where $\...
- 31
2
votes
1
answer
39
views
When multiplying two or more terms in an integral, can I calculate the terms seperately and then multiply?
For example, say I have an equation that is $\int_0^\infty x g(x)f(x)dx$
Can I calculate each term seperately, say for example my maximum $x$ value is 500.
Is it something like $500\int_0^{500} g(x)\...
- 219
3
votes
1
answer
73
views
Sums of divisors of a Jacobi symbol
$$f(n)= \genfrac(){}{0}{-15}{n}$$ if $n \neq 1$ is odd.
What is $\sum_{d \mid n}f(d)$ ?
Here is what I tried : Let $n=p_1^{a_1} \cdot \cdot \cdot p_r^{a_r}$, for $p_1,...,p_r$ odd primes. If $p_1,...,...
- 434
-1
votes
2
answers
62
views
Euclidean algorithm and Multiplicative inverse in RSA Cryptosystem
I understand RSA Cryptosystem, the Euclidean algorithm, and mod, however, I can't seem to understand how to solve the following problem.
-Use Euclidean algorithm to compute the multiplicative inverse $...
- 1
-1
votes
1
answer
43
views
Prove that $G(n) = \sum_{d|n} \frac{n}{d}\tau(d)$ is multiplicative.
I don't know how to prove this because it seems to me that $f(d)=\frac{n}{d}\tau(d)$ is not multiplicative.
- 389
0
votes
1
answer
78
views
Sum of an arithmetic function over the divisors of an integer is multiplicative
I am trying to prove the following claim:
Let $f$ be an arithmetic function and, for $n \in \mathbb{Z}$ with $n > 0$, let
$$
F(n) = \sum_{d\ \vert\ n,\ d > 0}f(d)
$$
If $F$ is multiplicative, ...
- 103
0
votes
1
answer
40
views
Group operator vs. complex number multiplication operator in the multiplicative property of a character of a group [closed]
A character $f$ of a group $G$ is defined as a complex-valued function defined on $G$ that has the multiplicative property $f(ab) = f(a)f(b)$ for all $a, b$ in $G$, and if $f(c) \ne 0$ for some $c$ in ...
- 1,132
0
votes
3
answers
244
views
Let $f$, $g$ be multiplicative functions, not identically $0$ such that $f(p^k)=g(p^k)$ for each prime $p$ and $k \ge 1$. Prove that $f = g$.
Let $f$ and $g$ be multiplicative functions that are not identically $0$ and such that $f(p^k)=g(p^k)$ for each prime $p$ and $k\ge1$. Prove that $f=g$.
Source: Elementary Number Theory by David M. ...
- 665
2
votes
2
answers
75
views
The Question about Euler's Totient Function : How phi(i*p) = p*phi(i)? Here, p is prime and p divides i, phi-> Euler totient function
I have a question about the Euler totient function. I am new to the number theory and i don't know where to start to prove this. If $p$ is prime and $p$ divides $i$,
$$ Φ (i\cdot p) = p \cdot Φ (i),$$...
- 23
0
votes
1
answer
46
views
derivate is based on addition, is there a muliplication analogon?
like
$$
\operatorname{f^o}(x) = \lim_{h\to 1} \frac{f(x*h)}{f(x)}
$$
$$
\operatorname{f}(x)=e^x
$$
$$
\operatorname{f^o}(x) = \lim_{h \to 1} e^{x*h}/e^{x} = \lim_{h\to 1} e^{x*h-x}=e^0=1
$$
does it ...
1
vote
0
answers
53
views
Dirichlet convolution of a multiplicative function with itself
Let $f$ be a multiplicative function, i.e. for all coprime $a,b\in\mathbb{N}\quad f(ab)=f(a)f(b)$.
Consider:
$$(f*f)(n)=\sum_{d\vert n}f(d)f\left(\frac{n}{d}\right),\quad\text{where * is Dirichlet ...
- 439
2
votes
5
answers
255
views
Find the highest natural number which is divisible by $30$ and has exactly $30$ different positive divisors.
Find the highest natural number which is divisible by $30$ and have exactly $30$ different positive divisors.
What I Tried: I am not sure about any specific approach to this problem. Of course as the ...
- 4,061
2
votes
1
answer
144
views
Check if an arithmetic function is (completely) multiplicative
In Paul J. McCarthy's book about arithmetic functions, he constructs a completely multiplicative function $g$ by setting $g(p)$ equal to a root of the equation
$$X^2+f^{-1}(p)X+f^{-1}(p^2)=0, $$
where ...
- 654
-1
votes
2
answers
72
views
RSA: what is $k$ in the formula to calculate $d$? [closed]
In RSA, to calculate $d$, when given $\phi(n)$ and $e$, I stumbled upon this formula:
$$d = \dfrac{k \phi(n) + 1}{e}$$
But what does $k$ stand for? How to obtain the value for $k$?
Thank you,
Chris
- 29
0
votes
0
answers
59
views
Sum of inverse of a multiplicative function
I stumbled upon the following problem, while trying to come up with a recreational math question.
Let $n$ be a positive integer with factorization $n=2^a\prod_{i=1}^{k}p_i^{e_i}$
Define the arithmetic ...
user125368
0
votes
1
answer
62
views
Multiplicative Functions Proof
I don't know if this question was asked before, but I could not find it on this forum: a function $f(n)$ is multiplicative if $f(mn)=f(m)f(n)$, where m and n are coprime and positive. If $d(n)$ is the ...
- 21
1
vote
0
answers
73
views
Proving a relation between sum of reciprocal of divisors and $\sigma(n)$
Prove that $\sum_{d\mid n}\dfrac{1}{d}=\dfrac{\sigma(n)}{n}\ \forall\ n\geq 1, n\in \mathbb
Z$
My question and my approach is a lot similar to this question and a bit different from this question ...
- 1,725
1
vote
0
answers
42
views
Any results about auto-correlation function of Mertens function
One can define $f(x) = M(e^x)/\sqrt{e^x}$, where $M$ is Mertens function. It looks like some sort of stationary random process (yes, I know it's not random process, see plot below), namely it lives ...
0
votes
1
answer
63
views
2.20 Question Introduction to analytic number theory
The following question is on page 48 apostol Introduction to analytic number theory( 20)
Let $P(n)$ be the product of the positive integers which are less than equal to $n$ and relatively prime to $n$...
- 1,545
0
votes
1
answer
33
views
A question in solution of a problem involving multiplicative functions
This question is question 2.3 of Apostol Introduction to analytic number theory.
It's solution image:
My question: how did in RHS on last line of solution author got $n / \phi(n) $ as $n = p_{1}^{a_1}...
- 1,545
5
votes
0
answers
252
views
Efficient summation of multiplicative functions on intervals
Suppose that $f: \mathbb{N} \to \mathbb{C}$ is a multiplicative function; i.e., $f(mn) = f(m)f(n)$ if $m, n$ are coprime. I'm interested in efficiently calculating sums of the form $\sum_{k=1}^N f(k)$...
- 1,085
1
vote
1
answer
73
views
Is $\frac{\sigma(n)}{{2n}}$ submultiplicative or supermultiplicative?
This question is an offshoot of this earlier post.
It is known that the abundancy index
$$I(n) = \frac{\sigma(n)}{n}$$
is a multiplicative function. (Note that the divisor sum $\sigma$ is also ...
- 10.2k
2
votes
1
answer
85
views
Is this function multiplicative and if so what is its value at prime powers?
For odd numbers $n$ let:
$$a(n) = \sum_{d^2|n} d \frac{\sigma^*(n/d^2)}{2^{\omega(n/d^2)}}$$
where $\sigma^*(k) = $ sum of unitary ($\gcd(d,k/d)=1$) divisors of $k$ and $\omega$ counts the prime ...
user276611
3
votes
2
answers
62
views
Prove of $\prod_{d|n} (\mu(d)(\mu(d) + 3) + 4) = 4^{d(n)}$
Found an interesting relation:
$$\prod_{d|n} (\mu(d)(\mu(d) + 3) + 4) = 4^{d(n)}$$
where $\mu(n)$ is a Möbius function and $d(n)$ is a divisors count.
I think this should be something known. The prove ...
- 1,560
2
votes
3
answers
129
views
find all $n$ such that $\varphi(\sigma(2^n)) = 2^n$
Problem: Find all positive integers $n$ such that $\varphi(\sigma(2^n)) = 2^n$, where $\varphi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of all divisors of $n$.
I know that $\sigma(2^...
- 35
1
vote
2
answers
210
views
Sum of divisors function inequality
Prove that if $n<m$ and $n$ divides $m$, then $\frac{\sigma(n)}{n} < \frac{\sigma (m)}{m}$, where $\sigma(x)$ denotes the sum of all the divisors of $x$.
I know that $\sigma (x)$ is ...
- 35
0
votes
1
answer
33
views
Show $\sum_{c|n} \mu(c)f(c) = \{1-f(p_1)\}\{1-f(p_2)\} \dots \{1-f(p_r)\}$ [closed]
$n=p^{k_1}_1p^{k_2}_3...p^{k_r}_r$ and f is multiplicative function.I have tried convolution but it seems not solving.
0
votes
0
answers
89
views
Why does the divisor-counting function appear in bounds for Kloosterman sums?
Given integers $m,n$ and $c \geq 2$, the Kloosterman sum is defined as $S(m,n;c) = \sum_{k \in (\mathbb{Z}/c\mathbb{Z})^{\times}}{e^{\frac{2i\pi}{c}(mk+nk^{-1})}}$, where $k^{-1}$ is the reciprocal of ...
- 27.3k
0
votes
1
answer
161
views
If an arithmetic function $f$ satisfies $f(mn) \leq f(m)f(n)$ (whenever $\gcd(m,n)=1$), is $f$ weakly multiplicative or submultiplicative?
From the preprint On sums of the small divisors of a natural number (Lemma 1, page 2) by Douglas E. Iannucci:
We observe here that the function $a(n)$ is not multiplicative. It is, however, ...
- 10.2k
3
votes
1
answer
80
views
A problem regarding the product of all the elements of $U_n$ for some selected $n$
$\mathbf {The \ Problem \ is}:$ Find the product of all elements of the multiplicative group $U_n$ where $n=p^2q$ and $p^2$ for distinct primes $p$ and $q ?$
$\mathbf {My \ approach} :$ Actually, ...
- 1,843
4
votes
1
answer
184
views
Estimate for $\sum_{n\leq x}2^{\Omega(n)}$
I need some help to find a mistake in my proof.
I have to prove that $\sum_{n\leq x}2^{\Omega(n)}\sim cx\log^2x$ for $x\rightarrow+\infty$, where $\Omega(p_1^{k_1}\cdot\ldots\cdot p_j^{k_j})=k_1+\...
- 187
1
vote
1
answer
42
views
Reference request: Axiomatic treatment of multiplicative functions?
I'm currently reading Apostol's analytic number theory, Chapter 2 on multiplicative functions. While the current exposition is nice, I can't help but feel that there has to been some algebraic ...
- 7,778