Maths Olympiad Prep

Library / IMO Shortlist /91 of 365

IMO Shortlist

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 n≥1n\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 n≥1 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)=2k−2k−1=2k−1\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(2k−1)=k d(\varphi(2^k)) = d(2^{k-1}) = k, because the divisors of 2k−1 2^{k-1} are {1,\{1, 2, 4, …,2k−1}.\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=p⋅q 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 n≥1 n \geq 1 .

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

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.