For questions on arithmetic functions, a real or complex valued function $f(n)$ defined on the set of natural numbers.

learn more… | top users | synonyms

0
votes
0answers
6 views

for which values of the pair of integers $(n,k)$ : $p(n.k)=p(n).p(k)$?

let $p(n,k)= 1+\frac{2^{k}-1}{n}$ for a positive integer $n,k$ -for which values of the pair of integers $(n,k)$ : $p(n.k)=p(n).p(k)$ ? note :$p(n)$ and $p(k)$ should be primes for a possible ...
3
votes
0answers
22 views

Summation of a function 2

Let $n$ is a positive integer. $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the complete prime factorization of $n$. Let me define a function $f(n)$ $f(n) = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ where ...
3
votes
0answers
75 views

Approximate how the Numbers $n$ such that Mertens' function is zero grow.

Is it possible to approximate how the "Numbers $n$ such that Mertens' function is zero" grow?
4
votes
0answers
321 views

Numbers $n$ such that Mertens' function is zero.

OEIS (A028442) lists the Numbers n such that Mertens' function $$ M(n)=\sum_{k=1}^n\mu(k) $$ is zero: 2, 39, 40, 58, 65, 93, 101, 145, 149, 150, 159, 160, 163, 164, 166, 214, 231, 232, 235, 236, ...
3
votes
1answer
38 views

Number of Divisors of most numbers

In the book A Comprehensive Course in Number Theory by Alan Baker. The author mentions that even though the average order of $\tau(n)$ is $\log n$, almost all numbers have about $(\log n)^{\log 2}$ ...
3
votes
1answer
38 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
1answer
18 views

Multiplicative Function Property

Suppose $f$ is an arithmetic function. Does the property $f(1) = 1$ if $f$ is multiplicative? Or is it only when $f$ is completely multiplicative?
5
votes
1answer
73 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
3
votes
5answers
123 views

How can I show that $\phi(m) \mid \phi(n)$? [duplicate]

I want to prove that: $$\text{ if } m,n \geq 1 \text{ and } m \mid n,\text{ then } \phi(m) \mid \phi(n).$$ How can I show this? I thought the following: $$m \mid n \Rightarrow \exists k \in ...
2
votes
2answers
131 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
3
votes
0answers
102 views

To prove $\phi(mn)\phi(d)=\phi(m)\phi(n)d$ without explicitly computing the phi function values

If $m,n$ are positive integers with g.c.d.$(m,n)=d$ , then we can show by explicitly computing respective totients that $\phi(mn)\phi(d)=\phi(m)\phi(n)d$, I want to know, is there any more elegant way ...
3
votes
1answer
56 views

find all positive integers n such that $\phi(n)+\sigma(n)=2n$.

I'm asked to find all integers n such that $\phi(n)+\sigma(n)=2n.$ I know that when n is a prime, $\phi(n)+\sigma(n)=(n-1)+(n+1)=2n.$ My guess is that n can only be primes, and I want to derive a ...
0
votes
1answer
19 views

On the sets $\{\dfrac {\phi(n+1)}{\phi(n)} : n\in \mathbb Z^+\}$ and $\{\dfrac {\phi(n)}{n} : n\in \mathbb Z^+\}$

How to show that the set $\{\dfrac {\phi(n+1)}{\phi(n)} : n\in \mathbb Z^+\}$ is dense in $\mathbb R^+$ ? Also that the set $\{\dfrac {\phi(n)}{n} : n\in \mathbb Z^+\}$ is dense in $(0,1)$ ?
2
votes
0answers
51 views

how to show $\lim \sup_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= \infty$ and $\lim \inf_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= 0$?

Let $\phi (n)$ be the Euler's totient function . Thenhow to prove that the set $\{\dfrac{\phi(n+1)}{\phi(n)}: n \in \mathbb Z^+\}$ is unbounded above that is how to show $\lim \sup_{n \to \infty} ...
1
vote
3answers
57 views

The probability that a random integer is prime to a given integer $m$ is $\frac{\phi(m)}m$?

Let $N_m(x)$ denote the number of positive integers not exceeding $x$ that are relatively prime to $m$ , then how to prove that $\lim_{x \to \infty} \dfrac{N_m(x)}x=\dfrac{\phi (m)}m$ , where ...
4
votes
1answer
99 views

Prove $\sum_{k = 1}^n \mu(k)\left[ \frac nk \right] = 1$ [duplicate]

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius ...
6
votes
2answers
770 views

Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1 $

I am trying to show $$\sum_{d \leq x} \mu(d)\left\lfloor \frac{x}{d} \right\rfloor = 1 \;\;\;\; \forall \; x \in \mathbb{R}, \; x \geq 1 $$ I know that the sum over the divisors $d$ of $n$ is zero if ...
1
vote
1answer
60 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
31 views

Proof involving the Euler phi-function

I'm having trouble approaching the following exercise: Let $n$ and $k$ be positive integers. Prove that $\phi(n^k) = n^{k-1}\phi(n)$. I've tried examining the prime factorization $n^k = (p_1^{a_1} ...
7
votes
1answer
109 views

Intuitive basis of Mobius inversion?

If we're given $f(n)= \sum_{d|n}g\left(\frac{n}{d}\right),n \in \mathbb{N},$ then Mobius inversion gives $$g(n)=\sum_{d|n}\mu \left( d\right) f \left( \frac{n}{d}\right).$$ Also, the generalised ...
1
vote
0answers
53 views

Relation between Dirichlet convolution and Bell series and convolution of functions and the Fourier transform?

We define the Dirichlet convolution of two arithmetic functions $a,b:\mathbb{N}\to\mathbb{C}$ to be $$ (a*b)(n)=\sum_{d\mid n}a(d)b\left(\frac{n}{d}\right). $$ Given a prime $p$, we define the Bell ...
2
votes
2answers
462 views

Show that $\sigma(n) = \sum_{d|n} \phi(n) d(\frac{n}{d})$

This is a homework question and I am to show that $$\sigma(n) = \sum_{d|n} \phi(n) d\left(\frac{n}{d}\right)$$ where $\sigma(n) = \sum_{d|n}d$, $d(n) = \sum_{d|n} 1 $ and $\phi$ is the Euler Phi ...
3
votes
1answer
65 views

Formula for $\sum_{d|n} \frac {\mu(d)}d$

I feel like I've seen a formula somewhere for $\displaystyle \sum_{d|n} \frac {\mu(d)}d$, but I can't remember what it is and can't find it. Does anybody know of a formula?
8
votes
3answers
917 views

Is there a “nice” formula for $\sum_{d|n}\mu(d)\phi(d)$?

I'm trying to work through Ireland and Rosen's A Classical Introduction to Modern Number Theory as I've heard good things about it. This is Exercise 12 from Chapter 2. Here $\mu$ is the Moebius ...
1
vote
2answers
110 views

A proof of $\sum{\mu(n)/n}=0$

I am looking for a proof (or references) of the following statement $$\sum_{n=1}^{\infty}{\frac{\mu(n)}{n}}=0$$ where $\mu$ is the Möbius function. Many thanks !
1
vote
1answer
271 views

Question - Möbius inversion formula

I need your help in the next question: Prove directly from the definition the Möbius inversion formula. (Möbius function defined as follows: μ(n) = 1 if n is a square-free positive integer with ...
9
votes
5answers
513 views

Identity with nested sum taken over divisors of $\gcd$'s

For computational reasons, I want to show that the following holds true: Let $n_1,n_2,N\in \mathbb{N}$. One has $$\Large \sum_{a\mid \gcd(n_1,N)}\sum_{b\mid \gcd(n_2,\frac{n_1N}{a^2})} ab ...
0
votes
0answers
26 views

Order of operations for log transformation

I am working with a large dataset of positive values with a positive skew. I will be using a Ln transformation in SPSS to normalize my dataset. However, I am not sure of the order of operations. For ...
1
vote
1answer
45 views

Demonstration in arithmetic function

I need help to know (in detail) how to prove that the product of two multiplicative arithmetic functions is a multiplicative arithmetic function. $$$$$f(n)$ and $g(n)$ are functions multiplicative, ...
-1
votes
5answers
159 views

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$ I found (by trial) $m=\{13,21,26,28,36\}$, but do not know if misinterpreted the problem, but actually I suppose I have to find an equation ...
1
vote
0answers
57 views

Summing the reciprocal of $\phi(n)^2$

I am currently reading Vaughan's book 'The Hardy-Littlewood method' and am working on exercise 3.3 (page 37). I have tried working through a special case but that didn't help either. More concretely, ...
6
votes
1answer
82 views

Lower bound of Euler phi function times sum of divisors

After some work, I got this nice inequality: $$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$ where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm ...
4
votes
2answers
65 views

Proving an identity of the Möbius function and Euler’s totient function product

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
0
votes
2answers
14 views

Offset a range of numbers

I want to find an equation to offset a range of numbers by a given amount. I'm not sure if I am using the term offset correctly. Lets say the range is from 0 - 1 and I want it to be offset by .25 : 0 ...
2
votes
0answers
23 views

To calculate what is $\sum_{1 \le m<n ;(m,n)=1} m^2$ or what is the remainder when $\sum_{1 \le m<n ;(m,n)=1} m^2$ is divided by $n$? [duplicate]

For an integer $n >1$ , what is the sum of the squares of all the positive integers that are less than $n$ and relatively prime to $n$ that is I am trying to calculate $f(n):=\sum_{1 \le m<n ...
4
votes
3answers
247 views

Prove there are k consecutive non-squarefree integers

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero. I've started the proof, but I need a bit of help midway ...
7
votes
2answers
85 views

$\varphi(N)>\pi(N)$?

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function? The only exceptions less than ...
1
vote
0answers
30 views

Number of triples $(a, b, c)$ with $1 \leq a,b,c \leq n$ which are coprime ($gcd(a,b,c)=1$)

Number of ordered triples $(a, b, c)$ with $gcd(a, b, c) = 1$ and $1 \leq a, b, c \leq n$ can be computed using the following formula: $$ C(n) = \sum_{k=1}^n\mu(k) \left \lfloor \frac{n}{k} \right ...
5
votes
1answer
113 views

How many numbers are products of $p^p$?

Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are ...
2
votes
3answers
59 views

Where did the sum-of-divisors function come from?

Doing a research project on a few number-theoretic functions, and I was curious, where does the sum-of-divisors function come from? Surely someone thought it up and made it a possibility. I'm talking ...
2
votes
1answer
72 views

Prime Factorization and Number Theory

Prime factorization of $n$ is $$n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$$ Let $f(n) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ where $e_k=a_k$ if $p_k|a_k$, else $e_k=a_k-1$ I want to ...
0
votes
0answers
48 views

What is the inverse of $f(x)=x^{x^x}$?

I'm curious to find the inverse of $ f(x)=x^{x^x} $ As an added extra, I'm already familiar with the Lambert Product Log function.
1
vote
2answers
686 views
1
vote
0answers
26 views

gcd of product of exponents of prime factors and product of prime factors

Let $n = \prod\limits_i p_i^{k_i}$. I want to express $$ \gcd(\prod\limits_i k_i, \prod\limits_i p_i) $$ as an arithmetic function (i.e get rid of gcd). Is that possible? Thanks!
1
vote
2answers
79 views

About the 'sigma' function.

Is it true that if $n$ divides $m$ , $\sigma(\frac mn) \leq \frac{\sigma(m)}n$. If so this has a bearing on counterexamples to Robin's inequality.
1
vote
0answers
66 views

A challenge question in elementary number theory!

Find an expression for the following sum: $$\sum_{i:(i,n)=1}(i-1,n)$$ I guess that this sum equals to $\phi(n)d(n).$
0
votes
2answers
67 views

Are there particular techniques to find the general formula for an arithmetic function, neither multiplicative nor additive?

I was reading about the Euler phi function and the sigma function when I began to wonder how on earth one gets to the general formula for an arithmetic function. I'm not considering trivial formulae ...
2
votes
2answers
79 views

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? [closed]

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? I'm trying to use the Cauchy condensation test to show that $\sum_{n\ge{2}}\frac{d(n)}{n\log^2n}$ is ...
0
votes
1answer
50 views

Product of all divisors [duplicate]

Prove that $\prod_{d \mid n}d=n^{v(n)/2}$ where $v(n)$ is the sum of divisors function. We have if $n=p_{1}^{a_{1}}p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ then $v(n)=(a_{1} +1)(a_{2}+1) \dots (a_{k} ...
7
votes
4answers
401 views

How to prove $ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$

how to prove: $$ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$$ $\prod_{d|n} d$ is product of all of distinct positive divisor of $n$, $\tau (n)$ is number (count)of all of positive divisor of $n$