Tag Archives: arithmetic function

A bound on the multiplicative order

Let $n=p_1^{a_1}\cdots p_k^{a_k}$ factored uniquely into primes, and let $a$ be an integer coprime to $n$. If we denote by $\hbox{ord}_na$ the multiplicative order of $a$ modulo $n$ then Euler’s theorem tells us that $\hbox{ord}_na\mid\phi(n)$, so that $\hbox{ord}_na\le\phi(n)$. Can we do better?

Note that $a^{p_i^{a_i-1}(p_i-1)}\equiv 1\pmod{p_i^{a_i}}$ for each $i$ by Euler’s theorem. Hence

(*)\qquad\qquad\begin{aligned}\hbox{ord}_na&\le [p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1)]\\ &=\frac{\phi(n)}{(p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1))^{k-1}}\end{aligned}

using a result from this post. Now if $2\parallel n$, then the GCD on the right-hand side is equal to $1$. Otherwise $2$ divides the GCD, so that

$(**)\qquad\qquad\qquad\qquad\displaystyle\hbox{ord}_na\le\frac{\phi(n)}{2^{k-1}}=\frac{\phi(n)}{2^{\omega(n)-1}}$.

By the Chinese Remainder Theorem we can choose $a$ to be a primitive root modulo $p_i^{a_i}$ for $i=1,\dots,k$ simultaneously. Hence equality can be achieved in $(*)$ for any $n$. Further, if one of the $p_i$ is $2$ and one is congruent to $3\pmod 4$ then the GCD in $(*)$ is exactly $2$, so that equality is achieved in $(**)$. So $(**)$ is the best uniform bound if $n\not\equiv 2\pmod 4$, while if $n\equiv 2\pmod 4$ then $\hbox{ord}_na\le \phi(n)$ is uniformly the best possible.

Filed under Number theory

Another inequality involving sigma and tau

Let $n$ be a positive integer. By the weighted AM-GM inequality, one has

$\displaystyle\frac{\sum d\cdot n/d}{\sum n/d}\ge\left(\prod d^{n/d}\right)^\frac{1}{\sum n/d}$,

where all sums and products are taken over the positive divisors $d$ of $n$. This means

$\displaystyle\boxed{\frac{n\tau(n)}{\sigma(n)}\ge\left(\prod_{d\mid n}d^{1/d}\right)^{n/\sigma(n)}}$.

Considering the analytic behaviour of the function $f(x)=x^{1/x}$ one deduces

$\displaystyle\prod_{d\mid n}d^{1/d}\ge\prod_{1\neq d\mid n}n^{1/n}=n^{(\tau(n)-1)/n}$

for any $n$, with equality iff $n$ is prime or $1$ or $4$. (By convention we take an empty product to be $1$.) Combining this with the first inequality in this post we obtain

$\displaystyle n^{1/2}\ge\frac{n\tau(n)}{\sigma(n)}\ge n^\frac{\tau(n)-1}{\sigma(n)}$,

i.e.,

$\boxed{\displaystyle n^{1/2}\le\frac{\sigma(n)}{\tau(n)}\le n^{1-\frac{\tau(n)-1}{\sigma(n)}}}$.

This strengthens the first boxed inequality from this post.

Filed under Number theory

Proof of a well-known identity involving Euler’s phi function

Let $\phi(n)$ be Euler’s function, i.e., the number of positive integers not exceeding $n$ that are coprime to $n$. A famous identity goes as follows:

$\displaystyle\sum_{d\mid n}\phi(d)=n$

where the sum is taken over all positive divisors of $n$. Here is a counting argument for a proof.

Let $S=\{1,\dots,n\}$. For each divisor $d$ of $n$, let us count the number of elements $m\in S$ with $\gcd(m,n)=d$. When $d=1$, this is just $\phi(n)$. What about when $d=2$? If $n$ is odd then clearly there is no such $m$. Otherwise, $\gcd(m,n)=2$ implies that $m$ and $n$ must both be even. Moreover, this happens iff $\gcd(m/2,n/2)=1$. Hence, as before, the number of such $m$ is $\phi(n/2)$.

This works in general: for any $d\mid n$, the number of elements $m\in S$ such that $\gcd(m,n)=d$ is $\phi(n/d)$. So summing $\phi(n/d)$ over all $d\mid n$, which is the same as summing $\phi(d)$ over all $d\mid n$, gives the total number of elements of $S$, which is $n$. This proves the desired result.

This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)

Filed under Combinatorics, Number theory

An inequality involving sigma and tau

Let $\tau(n)$ and $\sigma(n)$ respectively be the number and the sum of the positive divisors of the positive integer $n$. We will prove the following inequality:

$\sigma(n)\ge \sqrt n\tau(n)$.

First proof. By the Cauchy-Schwarz inequality,

$\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge (\sqrt n\tau(n))^2=n\tau(n)^2$.

Second proof. By Chebyshev’s inequality,

$\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge \tau(n)\cdot n\tau(n)$.

Third proof. By the AM-GM inequality,

$\displaystyle 2\sigma(n)=\sum_{d\mid n}\left(d+\frac nd\right)\ge 2\sqrt n\tau(n)$.

Fourth proof. Again by the AM-GM inequality,

$\displaystyle n^{\tau(n)}=\prod_{d\mid n}d\prod_{d\mid n}n/d=\left(\prod_{d\mid n}d\right)^2\Rightarrow n^{\tau(n)/2}=\prod_{d\mid n}d\le\left(\frac{\sigma(n)}{\tau(n)}\right)^{\tau(n)}$.

Fifth proof. If $n=p_1^{a_1}\cdots p_k^{a_k}$ factored into primes, then AM-GM gives

$\displaystyle\sigma(n)=\prod_{j=1}^k(p_j^{a_j}+\cdots+p_j+1)\ge\prod_{j=1}^k(a_j+1)p_j^{a_j/2}=\sqrt{n}\tau(n)$.

We also trivially have $\sigma(n)\le n\tau(n)$. Hence for all $n$,

$\displaystyle \boxed{\sqrt n\le\frac{\sigma(n)}{\tau(n)}\le n}$.

In general, if $f:\mathbb N\to\mathbb N$ is completely multiplicative, and

$F(n):=\displaystyle\sum_{d\mid n}f(d)$,

then the first four proofs can be generalised to deduce that

$(*)\qquad\qquad\qquad\qquad\quad\ F(n)\ge \tau(n)\sqrt{f(n)}$.

For example, if $\sigma_k(n)$ is the sum of the $k$-th powers of the positive divisors of $n$, then this shows that

$\displaystyle \boxed{n^{k/2}\le\frac{\sigma_k(n)}{\tau(n)}\le n^k}$

for each $k\ge 0$. This, combined with the result from the previous post, gives

$\displaystyle\lim_{n\to\infty}\frac{\sigma_k(n)}{n^{k+1}}=0$,

i.e., $\sigma_k(n)=o(n^{k+1})$ as $n\to\infty$, for each $k\ge 0$.

1 Comment

Filed under Number theory

An asymptotic property of the divisor counting function

Let $\tau(n)$ be the number of positive divisors of the positive integer $n$ and let $\phi(n)$ be Euler’s function. Then it is easily seen that

$\phi(n)+\tau(n)\le n+1$

for each $n$. So

$\displaystyle\frac{\phi(n)}{n}+\frac{\tau(n)}{n}\le 1+\frac 1n$

holds for all $n$.

$\displaystyle\limsup_{n\to\infty}\frac{\phi(n)}{n}=\lim_{n\to\infty}\frac{n-1}{n}=1$.

So it follows that

$\displaystyle\limsup_{n\to\infty}\frac{\tau(n)}{n}=0$.

Therefore, by the sandwich theorem,

$\displaystyle\lim_{n\to\infty}\frac{\tau(n)}{n}=0$,

i.e., $\tau(n)=o(n)$ as $n\to\infty$. In layman’s terms, this is saying that the number of divisors of $n$ is small compared to $n$ when $n$ is large. The following plot of $\tau(n)/n$ against $n$ for $1\le n\le 500$ captures this nicely.

So this means, for example, that there are only finitely many positive integers $n$ with more than $n/2015$ divisors, which I think is pretty neat!