Maths Olympiad Prep

Library / /11 of 12

Number theory Difficulty 6.5 National olympiad Prove it Bulgaria

Let aa be a positive integer. Denote by τ(a)\tau(a) and φ(a)\varphi(a) respectively the number of all positive integers that divide aa and the number of all positive integers not greater than aa and relatively prime to aa. Find all positive integers nn having only two prime divisors and such that φ(τ(n))=τ(φ(n))\varphi(\tau(n)) = \tau(\varphi(n)).

Solution

Let n=pkqln = p^k q^l, where p<qp < q are prime numbers, k,lNk, l \in \mathbb{N} and let u=φ(τ(n)),v=τ(φ(n))u = \varphi(\tau(n)), v = \tau(\varphi(n)). We have that u=φ((k+1)(l+1))u = \varphi((k+1)(l+1)) and v=τ(pk1ql1(p1)(q1))v = \tau(p^{k-1} q^{l-1} (p-1)(q-1)). Obviously u<kl+k+lu < kl + k + l and
vτ(pk1ql1(p1))+1=klτ(p1)+1. v \geq \tau(p^{k-1} q^{l-1} (p-1)) + 1 = kl \tau(p-1) + 1.
If p>2p > 2, then τ(p1)2\tau(p-1) \geq 2 and v2kl+1kl+k+lv \geq 2kl + 1 \geq kl + k + l (    (k1)(l1)0\iff (k-1)(l-1) \geq 0), hence v>uv > u. Therefore p=2p = 2 and thus v=τ(2k1ql1(q1))v = \tau(2^{k-1} q^{l-1} (q-1)).
If m>2m > 2 is a prime and mq1m | q-1, then 2mq12m | q-1. So,
vτ(2kql1m)=2(k+1)l>2kl+1 v \geq \tau(2^k q^{l-1} m) = 2(k+1)l > 2kl + 1
and again v>uv > u. Therefore q=2s+1,sNq = 2^s + 1, s \in \mathbb{N}. It follows now that v=τ(2k+s1ql1)=(k+s)lv = \tau(2^{k+s-1} q^{l-1}) = (k+s)l and the equality u=vu = v implies
φ((k+1)(l+1))=(k+s)l. \varphi((k+1)(l+1)) = (k+s)l.
It follows from the formula for φ\varphi that if a>1a > 1 and b>1b > 1, then φ(ab)abφ(b)b\frac{\varphi(ab)}{ab} \le \frac{\varphi(b)}{b}.
i.e. φ(ab)aφ(b)\varphi(ab) \le a \varphi(b) and equality holds only if all prime factors of aa divide bb. When a=k+1a = k + 1 and b=l+1b = l + 1 we have
φ((k+1)(l+1))(k+1)φ(l+1)(k+s)l. \varphi((k+1)(l+1)) \le (k+1) \varphi(l+1) \le (k+s)l.
Moreover the equality holds if and only if s=1s = 1, i.e. q=3q = 3. φ(l+1)=l\varphi(l + 1) = l. Hence l+1l + 1 is a prime number and all prime factors of k+1k + 1 divide l+1=rl + 1 = r, i.e. k+1=rt,tNk + 1 = r^t, t \in \mathbb{N}.
Therefore the desired numbers are all integers of the form n=2rt13r1n = 2^{r^t-1} 3^{r-1}, where rr is a prime number and tNt \in \mathbb{N}.

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 and solution reproduced as published; topic and difficulty added by this site.