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

3
votes
1answer
84 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 ...
3
votes
1answer
58 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 ...
3
votes
1answer
85 views

Properties of Arithmetic Functions

I was recently working on arithmetic functions and using Perron's formula to obtain asymptotic estimates. One observation I made was that the Dirichlet series often can be written in terms of the ...
3
votes
1answer
486 views

Chebyshev's first $\vartheta(x)$ function question

This was an exercise using the first Chebyshev function, $\vartheta(x)= \sum_{p \leq x} \log p.$ The question is simply how to prove (2) below, the rest is my two thoughts on how to proceed. [Edit: ...
3
votes
1answer
98 views

does the surd $\sqrt[p-1]{p}$ for prime $p$ occur in any context?

for any prime $p \in \mathbb{N}$ use the corresponding symbol $q$ to denote the quantity $$q=p^{\frac1{p-1}}$$ and for $n \in \mathbb{N}$ define: $$ Q_n= \prod_{p \le n} q $$ empty products evaluate ...
3
votes
1answer
112 views

Minimal $x$ for which $\phi(k) > n$ for all $k > x$

It's well-known that $$ \liminf_n\frac{\varphi(n)\log\log n}{n}=e^{-\gamma} $$ and there exists an effective version $$ \varphi(n)>\frac {n}{e^\gamma\log\log n+\frac{3}{\log\log n}} $$ valid for ...
3
votes
0answers
131 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
0answers
79 views

On the indivisibility of odd perfect numbers by small numbers

A good day to everyone! This question is an offshoot of the following MSE posts: Odd perfect number divisors Can an odd perfect number be divisible by $101$? My question is as follows: Is ...
3
votes
1answer
26 views

Two sets with the same geometric and arithmetic means

There are two sets A and B with equal geometric mean and arithmetic mean. Each element of both sets is odd integer greater than 1. A = B ? Order of elements isn't important.
3
votes
0answers
110 views

Does the Fourier matrix $F_n$ represent a (tensor) multiplicative function?

At "Complex Hadamard Matrices", I found that, two Kronecker (tensor) products of Fourier matrices $k_1$ and $k_2$ are equivalent, if and only if $k_2$ can be obtained from $k_1$ by a combination of an ...
3
votes
0answers
76 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
4answers
119 views

Finding the GCD of $50!$ and $2^{50}$

I've been trying to figure out how $n!$ and $x^n$ are related (where x is an integer) for most of the morning - I know it must be the key to unlocking this problem. Up to this point I've only used ...
2
votes
2answers
141 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 ...
2
votes
2answers
63 views

how to compute the “Hamming total” of a symmetric group?

The Hamming distance between two binary numbers has an obvious analogue for numbers encoded using a base $\gt 2$. A different analogue is the following. Let $\sigma \in S_n$ be a permutation which ...
2
votes
1answer
112 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
3answers
67 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
77 views

A closed form for $\sum_{i\cdot j^k=n}(-1)^i$?

$$\alpha_k(n) \stackrel{\text{def.}}{=} \sum_{i\cdot j^k=n}(-1)^i.$$ Does a closed form exist for $\alpha_k(n)$? For low values of $k$: $$\alpha_0(n)=(-1)^n$$ $$\alpha_1(n)=\begin{cases} ...
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 ...
2
votes
2answers
497 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 ...
2
votes
1answer
163 views

Next asymptotic term of the average order of sigma

$$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+O(n\log n). $$ Is the next asymptotic term known? That is, is there a monotonic increasing function $f(x)$ such that $$ ...
2
votes
1answer
44 views

Closed-Form Modular Arithmetic

Is there a way to define modulo division (or functions of modular arithmetic in general) as superposition of (elementary?) functions? For example, the multiplication is first introduced as ...
2
votes
1answer
40 views

for which values of the pair of integers $(n,k)$ is $p(n,k) =1+\frac{2^{k}-1}n$ is prime?

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)$ is prime ? Any help is very welcom .Thank you
2
votes
4answers
75 views

How to show that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ [duplicate]

set $ n, n \in \mathbb{N}$ and prove that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ ¨I have tried this¨ If $n > 1$ then $n = p_{1}^{\alpha_{1}}\cdot p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ ...
2
votes
1answer
47 views

Finding $m∈\mathbb N$ such that $d^n(m)$ is not a perfect square for any $n\geq1$

Let , for $k ∈\mathbb N$ , $d(k)$ denote the number of positive divisors of $k$ ; define $d^n (k)$ recursively as $d^1(k)=d(k)$ , for $n\geq1$ , $d^{n+1}(k)=d(d^n(k))$ , how do we find those ...
2
votes
1answer
89 views

how to prove $f$ is an arithmetic function with this property $\sum_{d\mid n} f(d)=n^2$

how to prove $f$ is an arithmetic function with this property $$\sum_{d\mid n} f(d)=n^2$$ Arithmetic function
2
votes
1answer
100 views

Solving $ f(\log x)$

A generalization of the conjecture $$\pi(x+x^{\theta}) - \pi(x) \sim \frac{x^\theta}{\log x} $$ (Ingham, 1937 or earlier) might be $$\Delta \pi_k = \pi_k((x+1)^2) - \pi_k(x^2)\sim \frac{x}{\log ...
2
votes
0answers
20 views

Characters appearing naturally in arithmetic functions

Let $r_2(n)$ denote the number of representations of $n$ as a sum of 2 squares. It is well-known that $$r_2(n) = 4\sum_{d \mid n} \chi(d),$$ where $\chi$ is the non-principal character modulo $4$. ...
2
votes
0answers
53 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} ...
2
votes
0answers
24 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 ...
2
votes
1answer
77 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 ...
2
votes
1answer
55 views

Arithmetic function

An arithmetic function is defined as follows:$f(1)=1$, $f(2k)=k$ and $f(2k+1)=f(k)+f(k+1)$. When (for which $k$) is $f(k)$ even? While it is obvious that $f(4n-1)=f(4n)=2n$, therefore $f(k)$ is even ...
2
votes
0answers
84 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
5answers
283 views

For every positive integer n greater than $2$, $\phi(n)$ is an even integer.

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer. I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show ...
1
vote
3answers
183 views

Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$?

A good day to everyone! Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$ (where $\sigma = \sigma_1$ is the sum-of-divisors function)? Note that, if $n = ...
1
vote
1answer
40 views

For all $n\in\Bbb N$ does there exist $n_1$ and $n_2$ such that $d(n_1) +d(n_2)=n$

I am trying to show that for each positive integer, $n$, we can find integers $n_1,n_2$ that satisfy $$d(n_1) +d(n_2)=n$$ where $d(n)$ is the divisor function. I am frustrated because even with easy ...
1
vote
2answers
77 views

Is Wiki wrong on Dirichlet Chararcters Modulo $10$?

Wiki says: Modulus 10 There are $\phi(10)=4$ characters modulo $10$. Note that $χ$ is wholly determined by $\chi(3)$, since $3$ generates the group of units modulo $10$. I can ...
1
vote
2answers
734 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
1answer
56 views

Evaluate $\sum_{d\mid N}\Lambda(d)$

For a positive integer $n$, define $$\Lambda(n) = \left\{ \begin{array} {ll} \log p & \mbox{if $n = p^r$, $p$ a prime and $r \in \mathbb{N},$ }\\ 0 & \mbox{otherwise.} ...
1
vote
2answers
80 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
2answers
129 views

If $(m,n)=1$ then $m^{\phi(n)}+n^{\phi(m)}\equiv0\pmod {mn}$

Show that if $(m,n)=1$ then $m^{\phi(n)}+n^{\phi(m)}\equiv0\pmod {mn}$ I tried, $(m,n)=1$ then, Euler theorem we have $m^{\phi (n)}\equiv1\pmod n$ and $n^{\phi (m)}\equiv1\pmod m$. But I could ...
1
vote
1answer
216 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 ...
1
vote
2answers
44 views

Finding root for the segment - found the formula but it doesn't work for some values - wrong formula?

I have the segment, defined as $(x_1, y_1)$, $(x_2, y_2)$. I know that $y_1\ge 0$ and $y_2 < 0$. I want to compute the root point for that segment. I decided to do it that way: ...
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
vote
1answer
413 views

Function that counts the number of divisors of a natural number?

Let Function $f(n)$ be formally defined for natural numbers such that it gives number of distinct divisors of the number n (n and 1 included) For example, $f (12)=6$, then what is a quick way to ...
1
vote
3answers
63 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 ...
1
vote
1answer
74 views

Finding formulas for sums

I know that $\sum_{d \mid n} \mu(d) = 0$ whenever $n >1$, and I know that $\sum_{d \mid n} \phi(d) = n$. How can I use this in order to give a formula for $\sum_{d \mid n} \mu(d)\phi(d)$?
1
vote
2answers
28 views

Mean of given Arithmetic function

Find the mean of $a, a+d, a+2d, a+3d,\dots,a+nd$ I have no idea what to do in this question but i have tried the following: $$mean\ \bar{x}= \frac{(a)+(a+d)+(a+2d)+(a+3d)+\cdots+(a+nd)}{n+1} $$ ...
1
vote
1answer
73 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$ ...
1
vote
1answer
80 views

What proportion of the natural numbers satisfy the following inequalities?

Let $\sigma_1(n)$ be the sum of the divisors of $n \in \mathbb{N}$, and let $$I(n) = \frac{\sigma_1(n)}{n}$$ be the abundancy index of $n$. What proportion of the natural numbers satisfy the ...
1
vote
1answer
152 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) ...