Maths Olympiad Prep

Library / /64 of 144

Number theory Difficulty 8.2 Shortlist Find the answer

For a positive integer nn, let d(n)d(n) be the number of positive divisors of nn, and let φ(n)\varphi(n) be the number of positive integers not exceeding nn which are coprime to nn. Does there exist a constant CC such that

φ(d(n))d(φ(n))C \frac {\varphi ( d(n))}{d(\varphi(n))}\le C
for all n1n\ge 1

Cyprus

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To determine whether there exists a constant C C such that
φ(d(n))d(φ(n))C \frac{\varphi(d(n))}{d(\varphi(n))} \leq C
for all positive integers n1 n \geq 1 , we need to analyze the behavior of the arithmetic functions involved, particularly for different classes of numbers.

### Understanding the Functions

1. **Euler's Totient Function, φ(n)\varphi(n):** This function counts the number of positive integers up to n n that are coprime to n n .

2. **Divisor Function, d(n)d(n):** This function counts the total number of positive divisors of n n .

### Analyzing the Expression

We want to explore:

φ(d(n))d(φ(n)) \frac{\varphi(d(n))}{d(\varphi(n))}

For large values of n n , we choose n n to be a power of 2 to analyze the behavior.

### Example Exploration with Powers of 2

Let n=2k n = 2^k .

- Euler's Totient Function: φ(2k)=2k2k1=2k1\varphi(2^k) = 2^k - 2^{k-1} = 2^{k-1}.

- Divisor Function:
- d(2k)=k+1 d(2^k) = k + 1 , since 2k 2^k has k+1 k+1 divisors {1,2,4,,2k}\{1, 2, 4, \ldots, 2^k\}.
- d(φ(2k))=d(2k1)=k d(\varphi(2^k)) = d(2^{k-1}) = k, because the divisors of 2k1 2^{k-1} are {1,\{1, 2, 4, ,2k1}.\ldots, 2^{k-1}\}.

- Expression: Evaluating
φ(d(2k))d(φ(2k))=φ(k+1)k. \frac{\varphi(d(2^k))}{d(\varphi(2^k))} = \frac{\varphi(k+1)}{k}.

### Special Case Evaluation

- k+1 k + 1 can be an arbitrary integer. If k+1 k+1 is specifically chosen as a prime, φ(k+1)=k\varphi(k+1) = k.

This makes:
φ(k+1)k=kk=1. \frac{\varphi(k+1)}{k} = \frac{k}{k} = 1.

However, the challenge is maintaining a constant C C without dependence on n n . Evaluating cases where k k cannot be covered by simple conditions:

- Testing other numbers particularly those with more complex divisors or reduced φ(n)\varphi(n):
- Choosing n=pq n = p \cdot q (where p p and q q are distinct primes) where d(n) d(n) and φ(n) \varphi(n) have rapidly increasing counts of divisors complicates uniform bounding.

Thus, constructing examples for arbitrarily chosen numbers shows that no such uniform C C satisfies the inequality across all constructions of n n .

### Conclusion

Through various constructions and lacking the ability to uniformly cap the behavior of the divisor interactions with large n n :

No \boxed{\text{No}}

It concludes that no constant C C can exist to satisfy the condition for all n1 n \geq 1 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.