Maths Olympiad Prep

Library / /103 of 128

Number theory Difficulty 6.3 National Olympiad Prove it Philippines

Problem:

For a positive integer nn, denote by φ(n)\varphi(n) the number of positive integers knk \leq n relatively prime to nn. How many positive integers nn less than or equal to 100100 are divisible by φ(n)\varphi(n)?

Solution

Solution:

We claim that any such integer nn must be either equal to 11 or of the form 2a3b2^{a} 3^{b}, where a1a \geq 1 and b0b \geq 0.

First, we note that if n>1n > 1, it must be even. This is because if nn admits a prime factorization n=i=1kpirin = \prod_{i=1}^{k} p_{i}^{r_{i}} over distinct primes pip_{i}, then φ(n)=i=1k(pi1)piri1\varphi(n) = \prod_{i=1}^{k} (p_{i} - 1) p_{i}^{r_{i} - 1}. In particular, if an odd prime pip_{i} divides nn then pi1p_{i} - 1 divides φ(n)\varphi(n), and consequently φ(n)\varphi(n) is even.

Then, we note that at most one odd prime divides nn. Suppose otherwise, i.e., 2ap1r1p2r22^{a} p_{1}^{r_{1}} p_{2}^{r_{2}} is a part of the prime factorization of nn for odd primes p1,p2p_{1}, p_{2}. Then by the multiplicativity of φ\varphi, we know that
φ(2ap1r1p2r2)=2a1(p11)p1r11(p21)p2r21 \varphi\left(2^{a} p_{1}^{r_{1}} p_{2}^{r_{2}}\right) = 2^{a-1} (p_{1} - 1) p_{1}^{r_{1} - 1} (p_{2} - 1) p_{2}^{r_{2} - 1}
must divide φ(n)\varphi(n). Note that the largest power of 22 dividing nn is 2a2^{a}, but since p11p_{1} - 1 and p21p_{2} - 1 are both even, 2(a1)22=2a+12^{(a-1)} 2^{2} = 2^{a+1} divides φ(n)\varphi(n). This is a contradiction.

Finally, we show that the said odd prime pp dividing nn must in fact be equal to 33. Indeed, if n=2aprn = 2^{a} p^{r} where aa and rr are positive integers, we have
nφ(n)=2pp1=2+2p1. \frac{n}{\varphi(n)} = \frac{2p}{p-1} = 2 + \frac{2}{p-1}.
For this to be an integer, p=3p = 3.

Hence, we count all such integers of the form n=2a3rn = 2^{a} 3^{r} by summing over all possible values of rr (because there are fewer):

If r=0r = 0, then 0a60 \leq a \leq 6. (This is the only case in which a=0a = 0 is allowed.)

If r=1r = 1, then 1a51 \leq a \leq 5.

If r=2r = 2, then 1a31 \leq a \leq 3.

If r=3r = 3, then a=1a = 1.

This gives us a total of 7+5+3+1=167 + 5 + 3 + 1 = 16 values of nn.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.