Maths Olympiad Prep

Library / /3 of 19

Number theory Difficulty 7.2 National olympiad, round 2 Find the answer

Find the number of positive integers nn satisfying ϕ(n)n\phi(n) | n such that
m=1([nm][n1m])=1992\sum_{m=1}^{\infty} \left( \left[ \frac nm \right] - \left[\frac{n-1}{m} \right] \right) = 1992
What is the largest number among them? As usual, ϕ(n)\phi(n) is the number of positive integers less than or equal to nn and relatively prime to n.n.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us analyze the problem and find the positive integers n n such that ϕ(n)n \phi(n) \mid n and:

m=1(nmn1m)=1992 \sum_{m=1}^{\infty} \left( \left\lfloor \frac{n}{m} \right\rfloor - \left\lfloor \frac{n-1}{m} \right\rfloor \right) = 1992

### Step 1: Simplify the Sum

The expression inside the sum, nmn1m\left\lfloor \frac{n}{m} \right\rfloor - \left\lfloor \frac{n-1}{m} \right\rfloor, evaluates to 1 if m m divides n n , and 0 otherwise. Thus, the sum counts the number of divisors of n n .

This implies:

d(n)=1992 d(n) = 1992

where d(n) d(n) is the number of divisors of n n .

### Step 2: Consider ϕ(n)n\phi(n) \mid n

The condition ϕ(n)n\phi(n) \mid n implies that n n must be a power of a prime, say n=pk n = p^k .

For prime powers, ϕ(n)=pkpk1=pk1(p1)\phi(n) = p^k - p^{k-1} = p^{k-1}(p-1), and divides n=pk n = p^k .

### Step 3: Prime Power Condition

Using the formula for the number of divisors of a prime power:

d(pk)=k+1=1992 d(p^k) = k + 1 = 1992

Hence, k=1991 k = 1991 .

### Step 4: Maximize n n

To find the largest n n , assume p p is the smallest prime, p=3 p = 3 (since 2 will not satisfy ϕ(n)n\phi(n) \mid n for powers greater than 1).

Thus, n=31991 n = 3^{1991} .

n=31991 n = 3^{1991}

Hence, the largest n n satisfying both ϕ(n)n\phi(n) \mid n and d(n)=1992 d(n) = 1992 is:

31991 \boxed{3^{1991}}

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.