Questions tagged [multiplicative-function]
This tag is for questions relating to multiplicative functions which are arise most commonly in the field of number theory.
276 questions
0
votes
1
answer
66
views
Show that $\sum_{n \leq x} \left( \frac{\phi(n)}{n} \right)^\kappa = c(\kappa)x + O(x^\epsilon)$.
Let $\kappa$ be a fixed real number. Show that
$$\sum_{n \leq x} \left( \frac{\phi(n)}{n} \right)^\kappa = c(\kappa)x + O(x^\epsilon),$$
where
$$c(\kappa) = \prod_p \left( 1 - \frac{1}{p} \left( 1 - (...
- 707
0
votes
2
answers
148
views
Why is "the number of a rings of order $n$" a multiplicative function?
The OEIS sequence A037234 (also A027623) counts the number of (not necessarily unital) rings of order $n$. On the OEIS page (as pointed out by @Smiley1000) it says that the sequence is multiplicative. ...
- 1,415
0
votes
0
answers
28
views
The inverse of a non-multiplicative function in a set of arithmetic functions under Dirichlet product
I know how to find a Dirichlet inverse of multiplicative function and $g(n)$=-$\frac{1}{f(1)}$$\sum_{\substack{d \mid n \\ d < n}}$$f(\frac{n}{d})g(d)$. But how about other arithmetic functions? ...
- 11
1
vote
1
answer
150
views
Dirichlet series as Euler product
I am trying to show the following proposition:
Let $f$ be a multiplicative function and $P$ be the set of prime numbers. Then the Dirichlet series $\sum_{n=1}^\infty f(n)/n^s$ converges to the value $\...
- 135
5
votes
1
answer
132
views
How to correctly count "true" solutions to $x^n = 1 \bmod m$?
I got sidetracked (again) during the investigation of one of my other questions and started wondering how the cycles in the following picture came to be:
What you see here is the graph generated by ...
- 1,459
1
vote
0
answers
76
views
Finding all completely multiplicative arithmetic function such that $m+n\mid f(m)+f(n)$
My attempt:
Since $f$ is completely multiplicative we have $f(1)=1$.
$2n\mid 2f(n)$ for every n, so $f(n)=kn$ for some n.
$n+1\mid f(n)+1$ for every n,so for p prime, $p+1\mid kp+1\rightarrow p+1\mid ...
- 29
3
votes
1
answer
83
views
The "Euler Product formula" for general multiplicative functions
For the totient function $\phi$, we have the well known "Euler's product formula" (as named on Wikipedia) $$\phi(n) = n \prod_{p | n} \left( 1 - \frac{1}{p} \right)$$
This is easy to show ...
1
vote
1
answer
105
views
Applying convex multiplicative functions to Brocard's Problem
Brocard's problem asks if there are integer solutions to $n! = (x-1)(x+1)$ other than the cases of $n =$ $4$, $5$, $7$. Knowing the only shared divisor of the factors on the right is 2, would it be ...
- 43
0
votes
1
answer
101
views
Show that the function $f(n) = \sigma(n)\varphi(n)$ is a multiplicative function and calculate $f(p^k)$. [closed]
Let $f(n) = \sigma(n)\varphi(n)$ where $\sigma(n)=\sigma_1(n)= \sum_{d|n}d$ and $\varphi(n)$ is Euler function. Show that $f(n)$ is a multiplicative function and calculate $f(p^k)$, where $p$ is a ...
- 39
4
votes
1
answer
204
views
Does this function in $3$b$1$b has a name?
I was watching this video from $3$Blue$1$Brown channel, at minute 21:00 he introduced the following function:
$$
\chi(n)=
\begin{cases}
0 & \text{if } n=2k \\
1 & \text{if } n=4k+1\\
-1 & \...
- 6,267
14
votes
2
answers
547
views
Counting ones in binary representation: When is the product multiplicative?
Question:
For $n \in \mathbb{Z}^+$, define $Z(n)$ to be the number of ones in the binary expression of $n$. For fixed positive integer $a$, how does one describe the set of $b$ such that $Z(ab) = Z(a)...
- 15.9k
1
vote
2
answers
66
views
What is the reason for the ratios of square units not being the same as the ratios of units [closed]
When you have a square with side length 1 yard you get an area of 1 yd$^2$. When you convert the units of this square to feet you get a square with side length 3 and therefore an area of 9 square feet....
- 23
4
votes
0
answers
156
views
Probability that one random number among many has a unique prime factor
If I sample $N+1$ integers $x, x_1, \ldots, x_N$ uniformly and independently from $\{1, \ldots, M=2^k\}$, what is the probability that $x$ contains a prime divisor that does not divide any of the $\{...
- 679
2
votes
1
answer
92
views
Let $F: \mathbb R^n \to \mathbb R^m$ be smooth and such that for all $a \in \mathbb R$, $x \in \mathbb R^n$, $F(ax) = aF(x)$. Prove $F$ is linear
Let $F: \mathbb R^n \to \mathbb R^m$ be smooth and such that for all $a \in \mathbb R$, $x \in \mathbb R^n$, $F(ax) = aF(x)$. Prove $F$ is linear.
I am sorry to say this, but I am really stuck on ...
- 3,830
1
vote
1
answer
73
views
Summation notation over divisors confusion
What does the following summation notation represent?
$\sum\limits_{d_1 \mid a, \; d_2\mid b}f(d_1d_2)=\sum\limits_{d_1\mid a }\sum\limits_{d_2 \mid b}f(d_1)f(d_1)=\sum\limits_{d_1\mid a}f(d_1)\sum\...
- 629
1
vote
1
answer
86
views
Prove that there are infinitely many natural number such that $σ(n)>100n$
The problem is as follows: Prove that there are infinitely many natural numbers such that $σ(n)>100n$. $σ(n)$ is the sum of all natural divisors of $n$ (e.g. $σ(6)=1+2+3+6=12$).
I have come to the ...
- 19
3
votes
1
answer
107
views
Euler's Totient Function - Multiplicativity via Group of Units
The ring $\mathbb{Z}_{n m}$ is isomorphic to the ring $\mathbb{Z}_n \times \mathbb{Z}_m$ if $\operatorname{gcd}(m, n)=1$ holds. Let us prove the property that the Totient Function $\varphi$ is ...
- 2,274
0
votes
1
answer
130
views
Sum of multiplicative functions
Let $f_1, f_2$ multiplicative functions such that $f_1 \ne 0$ and $f_2 \ne 0$.
I want to show that $f_1 + f_2$ is multiplicative if and only if $f_1 = -f_2$
I tried starting the "only if" ...
- 211
0
votes
2
answers
111
views
When is the norm of a ring $\Bbb Z[\sqrt{-p}]$ multiplicative?
I got inspired by quadratic rings and zeta functions. I know for instance that the norm $a^2 + 17 b^2$ for the ring $\Bbb Z[\sqrt{-17}]$ is multiplicative yet the ring $\Bbb Z[\sqrt{-17}]$ is not a ...
- 17.1k
1
vote
1
answer
150
views
On a conjecture involving multiplicative functions and the integers $1836$ and $137$
We denote the Euler's totient as $\varphi(x)$, the Dedekind psi function as $\psi(x)$ and the sum of divisors function as $\sigma(x)$. Are well-known arithmetic functions, see the corresponding ...
4
votes
1
answer
110
views
On a conjecture involving multiplicative functions and the integers $1836$ and $136$
We denote the Euler's totient as $\varphi(x)$, the Dedekind psi function as $\psi(x)$ and the sum of divisors function as $\sigma(x)$. Are well-known arithmetic functions, see Wikipedia. I would like ...
0
votes
0
answers
45
views
Multiplicative complex function has mean value
I came up with the following question, and I don't have proof of it.
Let $m>1$ be a positive integer. Let $f:\mathbb{N}\to \mathbb{C}$ a multiplicative function, whose image is a subset of the $m$-...
- 21
2
votes
0
answers
149
views
Examples of quasi-logarithmic functions on natural numbers.
I saw this question recently and was curious about the value of the smallest symmetric group $S_k$ that has an element of order $n$. Call $k$, which depends on $n$, $f(n)$.
I checked a few small ...
- 12.1k
3
votes
1
answer
125
views
The mean square of $d_k(n)$
Let $d_2(n)=d(n)$ be the divisor function, and let $$d_k(n)=\sum_{d_1\cdots d_k= n}1=\sum_{m\cdot l= n}d_{k-1}(m).$$ Can anyone point me to a reference to the size of the error term when approximating
...
- 1,694
3
votes
1
answer
278
views
Polynomial Approximation of Multiplicative Function
Motivation: I am a undergrad studying number theory and all the multiplicative functions I studied in the course note has a polynomial upper bound, leading me to inquire where this holds for all ...
- 57
0
votes
0
answers
19
views
Number of ways to write $2n-1$ as $4x+2y+4xy+1$ where $x$ and $y$ are nonnegative integers
I see a claim in OEIS/A1227 which state that
"Number of ways to write $2n-1$ as $4x+2y+4xy+1$ where $x$ and $y$ are nonnegative integers equals number of odd divisors of $n$."
I can't see ...
- 907
0
votes
1
answer
72
views
Name of conjecture about correlation of $\lambda(n)$ and $\lambda(n+1)$
I remember reading about a conjecture one night a while ago, but I can’t seem to find anything about it anymore. I have forgotten it’s name, but I believe the conjecture went as follows:
Suppose $\...
- 2,577
1
vote
1
answer
76
views
Determining all arithmetic multiplicative functions that are idempotent to the convolution product
Exercise. Determine all the arithmetic multiplicative functions that are idempontent to the convolution product, i.e., determine all the functions $f$ such that, for every $a \in \Bbb N$, we have:
$$
(...
- 1,217
1
vote
1
answer
63
views
If $b|a$ and $f$ is a completely multiplicative function, how can I show that $f(a/b) = f(a) / f(b)$?
I know that $f(ab) = f(a)f(b)$ , but I'm not quite sure how to use this information.
- 21
0
votes
0
answers
83
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 ...
- 21.6k
0
votes
1
answer
900
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 ...
- 957
1
vote
0
answers
49
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
94
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 ...
- 129
2
votes
1
answer
402
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) \...
- 1,146
1
vote
1
answer
72
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, ...
- 1,032
0
votes
2
answers
121
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 ...
- 3,164
0
votes
0
answers
102
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 ...
- 157
3
votes
3
answers
286
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 ...
- 9,195
-2
votes
1
answer
85
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$ ...
- 3,801
1
vote
1
answer
127
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$ ...
- 4,026
7
votes
2
answers
418
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\...
- 4,026
2
votes
1
answer
93
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
90
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
247
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 ...
- 9,195
0
votes
1
answer
113
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
35
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=\...
- 444
0
votes
1
answer
74
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 $\...
- 41
2
votes
1
answer
551
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)\...
- 249
3
votes
1
answer
136
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,...,...
- 444
-1
votes
2
answers
176
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