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.

Advertisements

Leave a comment

Filed under Number theory

Another inequality involving sigma and tau

cf. an 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.

Leave a comment

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!)

4 Comments

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.

Since there are infinitely many primes,

\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.

Screenshot 2015-06-26 03.46.54

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!

Leave a comment

Filed under Number theory