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

2
votes
1answer
27 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
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
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}$ ...
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
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
57 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 ...
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
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} ...
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 !
0
votes
0answers
27 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 ...
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?
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 ...
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? ...
1
vote
1answer
62 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
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
250 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 ...
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 ...
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
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
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).$
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 ...
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 ...
2
votes
4answers
70 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}}$ ...
1
vote
0answers
77 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
1answer
58 views

How to show that $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$ [closed]

If f is an arithmetic function such that $f (1) = 1$ and $p$ is a prime number. Prove that: $\forall k \in \mathbb{N}$ $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$
4
votes
1answer
102 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
1answer
176 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
1
vote
0answers
34 views

All all hypo-multiplicative functions linear combinations of quasi-multiplicative functions?

A function $f(n)$ is multiplicative if, for all coprime $m$ and $n$, $f(m)f(n)=f(mn).$ It is called quasi-multiplicative by many authors if $f(m)f(n)=f(1)f(mn)$, and the two coincide when $f(1)=1.$ ...
1
vote
0answers
86 views

Multiple Dirichlet convolutions

I have been playing around with Dirichlet convolutions. As a reminder, take two arithmetic functions $f,g$, then their Dirichlet convolution is defined as the arithmetic function with: $(f\star g)(n) ...
3
votes
0answers
76 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 ...
1
vote
1answer
60 views

Sums involving square of Moebius function

I try to estimate the following sum: $$ \sum_{n \leq x}\mu(n)^2 f(n) $$ where $\mu(n)$ is a Moebius function and $f(n)$ is some multiplicative arithmetic function. If I understand it correctly it is ...
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 ...
0
votes
0answers
30 views

Number of excellent pairs is equal to $\sigma(n)$

Let $\nu$ be an irrational positive number, and let $m$ be a positive integer. A pair of $(a,b)$ of positive integers is called good if $$a \left \lceil b\nu \right \rceil - b \left \lfloor a \nu ...
4
votes
2answers
156 views

Which natural number predicates can be defined in Robinson arithmetic?

I'm especially wondering about the order relation, subtraction, division and exponentiation here: $x \leq y \quad \Leftrightarrow \quad \exists u\ y=x+u$ $z= x-y \quad \Leftrightarrow \quad ...
0
votes
1answer
49 views

Find the term of the G.P.

Find the term of the G.P. $1, 1.2, 1.44, 1.728,... $ which is just greater than $100$. Please somebody explain me the question? All i know is $a=1$ and $r=1.2$ Help :( should it be $T_{n} > ...
4
votes
2answers
114 views

prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
1
vote
1answer
73 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)$?