#10 Arithmetic Functions

\(540=2^2\cdot 3^3\cdot 5\). Therefore \(\tau(540)=3\cdot 4\cdot 2=24\). Also \(\sigma(540)=(1+2+4)(1+3+9+27)(1+5)=7\cdot 40\cdot 6=1680\). Finally, \(\varphi(540)=540\cdot\frac12\cdot\frac23\cdot\frac45=144\).

Since \(\tau(n)=(a+1)(b+1)\), the pairs are \((a+1,b+1)=(1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\). Because \(a,b\ge 0\) are allowed in \(2^a3^b\), all pairs give solutions: \(3^{17}\), \(2\cdot 3^8\), \(2^2\cdot 3^5\), \(2^5\cdot 3^2\), \(2^8\cdot 3\), \(2^{17}\).

Since \(a\) and \(b\) are coprime, every divisor \(d\mid ab\) is uniquely \(d=d_1d_2\), where \(d_1\mid a\), \(d_2\mid b\). Hence \(\sigma(ab)=\sum_{d_1\mid a}\sum_{d_2\mid b}d_1d_2=\left(\sum_{d_1\mid a}d_1\right)\left(\sum_{d_2\mid b}d_2\right)=\sigma(a)\sigma(b)\).

If \(\gcd(a,n)=1\), then \(\gcd(n-a,n)=1\). These two residues are distinct: \(a=n-a\) would give \(2a=n\), so \(a\) is not coprime to \(n\) for \(n>2\). Thus the coprime residues split into pairs, and their number \(\varphi(n)\) is even.

Consider the numbers \(1,2,\ldots,n\). After reducing \(\frac{k}{n}\), its denominator becomes a divisor \(d\) of \(n\). For a fixed denominator \(d\), the numerator can be any number from \(1\) to \(d\) coprime to \(d\), giving \(\varphi(d)\) fractions. All \(n\) values of \(k\) are counted exactly once, so \(\sum_{d\mid n}\varphi(d)=n\).

The condition gives \(\frac{n}{\varphi(n)}=2\). If \(n\) has an odd prime divisor \(p\), then the product contains \(\frac{p}{p-1}\), and even with the possible factor \(2\) from the prime \(2\), the product cannot be exactly \(2\). Thus the only prime divisor of \(n\) is \(2\). Hence \(n=2^a\), \(a\ge 1\). All such numbers work since \(\varphi(2^a)=2^{a-1}\).

We have \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}=3\). To get the integer value \(3\), the primes \(2\) and \(3\) must occur: \(\frac{2}{1}\cdot\frac{3}{2}=3\). Any other prime \(p\ge 5\) adds a factor \(\frac{p}{p-1}>1\) and changes the value. Hence \(n=2^a3^b\), where \(a,b\ge 1\). All such \(n\) work.

We need \(\prod_{p\mid n}\frac{p}{p-1}=\frac52\). The factors from \(2\) and \(5\) give \(2\cdot\frac54=\frac52\). Adding any other prime changes the product. Without \(2\) or without \(5\), the value is also impossible. Therefore \(n=2^a5^b\), where \(a,b\ge 1\). Check: \(\varphi(2^a5^b)=2^{a-1}\cdot 4\cdot 5^{b-1}=\frac{2}{5}2^a5^b\).

Let \(n=2^a\prod p_i^{\alpha_i}\), where \(p_i\) are odd. For odd \(p\), the sum \(1+p+\cdots+p^\alpha\) consists of \(\alpha+1\) odd terms, so it is odd if and only if \(\alpha\) is even. For \(2^a\), the sum \(1+2+\cdots+2^a\) is always odd. Therefore \(\sigma(n)\) is odd exactly when all exponents of odd primes are even. This means the odd part of \(n\) is a square; the exponent of \(2\) is arbitrary. If \(a\) is even, \(n\) is a square; if \(a\) is odd, \(n\) is twice a square.

If \(n\) has at least two coprime prime-power factors \(p^a\) and \(q^b\), then \(\sigma(n)\) factors as a product of two integers greater than \(1\), so it is not prime. Hence \(n=p^a\). Then \(\sigma(n)=1+p+\cdots+p^a\). If \(a+1\) is composite, say \(a+1=uv\) with \(u,v>1\), then \(1+p+\cdots+p^a=\frac{p^{uv}-1}{p-1}\) factors as \(\frac{p^u-1}{p-1}(1+p^u+\cdots+p^{u(v-1)})\), composite. Thus \(a+1\) is prime, and \(\tau(n)=a+1\).

If \(n=\prod p_i^{a_i}\), then \(\tau(n)=\prod(a_i+1)=14\). Since \(14=14\) or \(14=7\cdot 2\), there are two types. First, \(n=p^{13}\). Second, \(n=p^6q\), where \(p\ne q\) are primes. There are no other types.

We have \(\sigma(p^a)=1+p+\cdots+p^a=\frac{p^{a+1}-1}{p-1}\). By the standard fact \(p^u-1\mid p^v-1\) if and only if \(u\mid v\), we get that \(\sigma(p^a)\mid\sigma(p^b)\) if and only if \(p^{a+1}-1\mid p^{b+1}-1\), that is \(a+1\mid b+1\). Dividing by the common factor \(p-1\) is valid because both expressions are the corresponding geometric quotients.

Let \(m=\prod p^{a_p}\), \(n=\prod p^{b_p}\), where \(0\le a_p\le b_p\). For a prime \(p\), the contribution to \(\varphi(p^a)\) is \(p^{a-1}(p-1)\) for \(a\ge 1\). If \(a_p=0\), there is no contribution. If \(a_p\ge 1\), the corresponding contribution in \(\varphi(n)\) contains \(p^{b_p-1}(p-1)\), divisible by \(p^{a_p-1}(p-1)\). Multiplying over all primes gives \(\varphi(m)\mid\varphi(n)\).

For \(\frac{n}{\varphi(n)}\) to be an integer, the product \(\prod_{p\mid n}\frac{p}{p-1}\) must be integral. Every odd prime \(p\) contributes an even factor \(p-1\) in the denominator. In the numerator there can be only one factor \(2\), if \(2\mid n\). Hence there is at most one odd prime divisor. If such a prime \(p\) occurs, we need \(p-1\mid 2\), so \(p=3\), and \(2\mid n\) is necessary. Therefore the solutions are \(n=1\), \(n=2^a\) for \(a\ge 1\), and \(n=2^a3^b\) for \(a,b\ge 1\). All are easily checked.

If \(\gcd(a,n)=1\), then \(\gcd(n-a,n)=1\). The pair \(a,n-a\) has sum \(n\). There is no self-pair: \(a=n-a\) gives \(2a=n\), and then \(a\) is not coprime to \(n\) for \(n>2\); for \(n=2\), the sum is \(1=\frac{2\cdot 1}{2}\). Thus the \(\varphi(n)\) numbers split into \(\frac{\varphi(n)}{2}\) pairs, each with sum \(n\). The total is \(\frac{n\varphi(n)}{2}\).

Every divisor \(d\) corresponds to \(\frac{n}{d}\), and the product of the pair is \(n\). If \(n\) is not a square, all divisors split into \(\frac{\tau(n)}{2}\) pairs, giving \(n^{\tau(n)/2}\). If \(n\) is a square, one divisor \(\sqrt{n}\) pairs with itself; the other pairs give \(n^{(\tau(n)-1)/2}\), and the remaining factor \(\sqrt{n}\) gives \(n^{1/2}\). The total is \(n^{\tau(n)/2}\).

For each pair of distinct divisors \(d\) and \(\frac{n}{d}\), we have \(d^2+\left(\frac{n}{d}\right)^2\ge 2n\). The pair contains two divisors, so its contribution is at least \(n\) per divisor. If \(n\) is a square, the central divisor \(\sqrt{n}\) contributes \(n\), exactly \(n\) for one divisor. Summing over all divisors gives \(\sigma_2(n)\ge n\tau(n)\).

Let \(d\) be the smallest divisor of \(n\) greater than \(1\). Then \(d\le \sqrt{n}\), otherwise \(n\) would have no divisor between \(1\) and \(\sqrt{n}\). The number \(\frac{n}{d}\) is also a divisor and \(\frac{n}{d}\ge \sqrt{n}\). The divisors \(1,d,\frac{n}{d},n\) contribute at least \(1+d+\frac{n}{d}+n>n+\sqrt{n}\). Hence \(\sigma(n)>n+\sqrt{n}\).

Let \(n=\prod_{i=1}^{r}p_i^{a_i}\), where \(r=\omega(n)\). Then \(\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1)\). If none of the \(p_i\) is \(2\), then all \(p_i\) are odd, and each factor \(p_i-1\) is even; hence \(2^r\mid\varphi(n)\), so certainly \(2^{r-1}\mid\varphi(n)\). If \(2\mid n\), then among the remaining primes there are \(r-1\) odd ones, and their factors \(p_i-1\) give divisibility by \(2^{r-1}\). The claim follows.

If \(n=p\) is prime, then all numbers \(1,2,\ldots,p-1\) are coprime to \(p\), so \(\varphi(p)=p-1\). Conversely, if \(n\) is composite, let \(d\) be a divisor of \(n\) with \(1