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

7
votes
2answers
965 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 ...
9
votes
4answers
1k 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$
4
votes
0answers
323 views

LCM of binomial coefficients and related functions

I know about the following identity: $$\displaystyle \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \frac{\text{lcm}(1, 2, ... n+1)}{n+1}$$ 1) Is there any method to find ...
1
vote
2answers
55 views

Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and ...
4
votes
0answers
356 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, ...
24
votes
1answer
827 views

Primes approximated by eigenvalues?

Consider the matrix starting: $$\displaystyle T = -\begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ ...
4
votes
1answer
149 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 ...
3
votes
1answer
187 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 ...
4
votes
3answers
486 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 ...
4
votes
2answers
100 views

Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$

Prove: $\sum_{k<n, (k,n)=1}k = \frac{1}{2}n \varphi (n)$ I have had strep throat and missed the lecture discussing properties of the Euler function. Any help in solving this is appreciated. ...
2
votes
2answers
179 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 ...
1
vote
2answers
1k views

Infinitely many positive integers $n$ such that $\phi(n) = \frac{n}{4}$?

Do there exist infinitely many positive integers $n$ such that $\phi(n) = \dfrac{n}{4}$?
1
vote
2answers
39 views

With $s(n)=\sum_{k=1}^n n \bmod k$, can be justified that $\forall\epsilon>0$ let us $\lim_{n\to\infty}\frac{s(n-1)}{\epsilon+s(n)}=1?$

Denoting as $$s(n)=\sum_{k=1}^n n \bmod k$$ the sum of remainders function (each remainder is defined as in the euclidean division of integers $n\geq 1$ and $k$). See [1] for example. For examples ...
10
votes
3answers
353 views

Arithmetical Functions Sum, $\sum_{d|n}\sigma(d)\phi(\frac{n}{d})$ and $\sum_{d|n}\tau(d)\phi(\frac{n}{d})$

$$\sum_{d|n}\sigma(d)\phi\left(\frac{n}{d}\right)=n\tau(n) ,\\ \sum_{d|n}\tau(d)\phi\left(\frac{n}{d}\right)=\sigma(n)$$ The problem (7.4.15) of Burton's Elementary Number Theory has been request to ...
9
votes
3answers
1k 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 ...
8
votes
1answer
144 views

Comparing average values of an arithmetic function

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior ...
5
votes
0answers
179 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 ...
4
votes
2answers
277 views

Elements of finite order in the group of arithmetic functions under Dirichlet convolution.

Let $(G, ∗)$ be the group of arithmetic functions $f : N \to C$ that satisfy $f (1)\neq 0$, with group operation given by the Dirichlet product $∗$. The identity function $I$ is the identity element ...
3
votes
2answers
104 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? ...
1
vote
0answers
254 views

Can an odd perfect number be divisible by 101?

Preamble - This question is an offshoot from the following earlier questions here at MSE: Can an odd perfect number be divisible by 825? Can an odd perfect number be divisible by 165? Odd perfect ...
4
votes
2answers
154 views

Limiting value of $\lim \frac{1}{k}\sum_{n=1}^k \frac{p(n+1)-p(n)}{\log p(n)}$

Empirically it seems $$\lim_{k\to \infty} \frac{1}{k}\sum_{n=1}^k \frac{g(n)}{\log p(n)} = 1\tag{1} $$ in which p(n) is the nth prime and g(n) is the prime gap $p(n+1)-p(n).$ Cramer conjectured ...
3
votes
5answers
151 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 ...
1
vote
1answer
82 views

Farey Sequence Vector Orthogonality Relation Question

Take the Farey sequence $\mathcal{F}_n$ for $n=39$ with values $a_m\in \mathcal{F}_n$ and put them into a vector $$ \vec v_k=\biggr(\exp(2\pi i k a_m)\biggr)_m $$ Since Merten's function for $n=39$ ...
7
votes
0answers
152 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
7
votes
1answer
203 views

Is there a complex variant of Möbius' function?

When you're dealing with arithmetic functions, you might have come across the classical Möbius' function $$ \mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\mbox{if }\; \omega(n) = ...
4
votes
1answer
207 views

Image of the Euler phi function

I was reading a text about arithmetic functions, which ofcourse mentioned the Euler phi function. I was wondering whether $\phi(n)$ takes on all positive integer values. The answer doesn't seem so ...
4
votes
1answer
562 views

On sums involving Euler's totient function

I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated: Let $\varphi(n)$ be Euler's totient function. Show that there is a constant ...
3
votes
0answers
83 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?
2
votes
1answer
113 views

Definition of “totient”

I had always taken the term "totient" to be defined by saying that the totient of a positive integer $n$ is the number of positive integers less than $n$ that are coprime to $n$. Thus, for example, ...
2
votes
0answers
85 views

Smallest prime p with N a quadratic residue mod p

Let $N$ be a square-free number equal to 2 or 3 $(\mod 4)$. Let $P(N)$ be the first odd prime, not a factor of $N$, for which $N$ is a quadratic residue. On average, $N$ would be a non-residue for ...
1
vote
1answer
182 views

Attempted exercise using Littlewood's theorem

This was an exercise to try to show we can use Littlewood's theorem$^1$ to prove that $$\lim_{N \to \infty}\frac{1}{N}\sum_{n=1}^{N} \frac{g(n)}{\log p_n} = 1 \hspace{30mm}(1)$$ If $\vartheta(p_k) ...
1
vote
1answer
228 views

How can the Möbius function be applied to a series?

Given a series $p_n(s)=\sum_{k=1}^n a_k $. I'd like to get $\hat{p}_n(s)=\sum_{k=1}^n \mu(k)a_k $. Think of $a_k=k^{-s}$ for example. If you let $n$ go to $\infty$, you'll see the well-known relation ...