Maths Olympiad Prep

Library / /93 of 97

Number theory Difficulty 8.8 Shortlist Find the answer

Given a fixed positive integer a9a\geq 9. Prove: There exist finitely many positive integers nn, satisfying:
(1)τ(n)=a\tau (n)=a
(2)nϕ(n)+σ(n)n|\phi (n)+\sigma (n)
Note: For positive integer nn, τ(n)\tau (n) is the number of positive divisors of nn, ϕ(n)\phi (n) is the number of positive integers n\leq n and relatively prime with nn, σ(n)\sigma (n) is the sum of positive divisors of nn.

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

Solution

Given a fixed positive integer a9 a \geq 9 , we need to prove that there exist finitely many positive integers n n satisfying the following conditions:
1. τ(n)=a \tau(n) = a
2. nϕ(n)+σ(n) n \mid \phi(n) + \sigma(n)

Here, τ(n) \tau(n) is the number of positive divisors of n n , ϕ(n) \phi(n) is the Euler's totient function, and σ(n) \sigma(n) is the sum of the positive divisors of n n .

Assume, for contradiction, that there are infinitely many such n n . Let n n be expressed in its prime factorized form as n=p1a1p2a2pmam n = p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m} . Given τ(n)=(a1+1)(a2+1)(am+1)=a \tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_m + 1) = a , which is fixed, we can use the Pigeonhole Principle to assume that m m , a1 a_1 , a2 a_2 , ..., am a_m are also fixed.

Now, consider the divisibility condition:
nϕ(n)+σ(n). n \mid \phi(n) + \sigma(n).

Substituting the expressions for ϕ(n) \phi(n) and σ(n) \sigma(n) , we get:
np1a11(p11)p2a21(p21)pmam1(pm1)+p1a1+11p11p2a2+11p21pmam+11pm1. n \mid p_1^{a_1 - 1} (p_1 - 1) p_2^{a_2 - 1} (p_2 - 1) \cdots p_m^{a_m - 1} (p_m - 1) + \frac{p_1^{a_1 + 1} - 1}{p_1 - 1} \frac{p_2^{a_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_m^{a_m + 1} - 1}{p_m - 1}.

We need to show that this condition cannot hold for infinitely many n n . By induction on m m , we start with m=1 m = 1 :
pcC1pc1(p1)+C2pc+11p1. p^c \mid C_1 p^{c-1}(p-1) + C_2 \frac{p^{c+1} - 1}{p-1}.

This clearly cannot hold for sufficiently large p p . Assuming the induction hypothesis for m1 m-1 , we need to show it for m m . If pi p_i are fixed, we reduce the problem to m1 m-1 and are done. Therefore, pi p_i must get larger and larger.

Considering the limit as pi p_i \to \infty , we have:
Tn=C1ϕ(n)+C2σ(n). T n = C_1 \phi(n) + C_2 \sigma(n).

Dividing and taking the limit to infinity, we get T=C1+C2 T = C_1 + C_2 . Thus,
C1(nϕ(n))=C2(σ(n)n). C_1(n - \phi(n)) = C_2(\sigma(n) - n).

Dividing by n n , we obtain:
C1(11p1)(11pm)+C2(1+1p1+1p12++1p1a1)(1+1pm++1pmam)=C1+C2. C_1 \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_m}\right) + C_2 \left(1 + \frac{1}{p_1} + \frac{1}{p_1^2} + \cdots + \frac{1}{p_1^{a_1}}\right) \cdots \left(1 + \frac{1}{p_m} + \cdots + \frac{1}{p_m^{a_m}}\right) = C_1 + C_2.

Letting pi p_i \to \infty , if C1C2 C_1 \neq C_2 , there will be a contradiction. Therefore, C1=C2 C_1 = C_2 , and we get:
(11p1)(11pm)+(1+1p1++1p1a1)(1+1pm++1pmam)=2. \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_m}\right) + \left(1 + \frac{1}{p_1} + \cdots + \frac{1}{p_1^{a_1}}\right) \cdots \left(1 + \frac{1}{p_m} + \cdots + \frac{1}{p_m^{a_m}}\right) = 2.

This leads to a contradiction since terms with 1pq \frac{1}{pq} cannot be dealt with. Hence, there cannot be infinitely many solutions.

Thus, the answer is: There\boxed{\text{There}} exist finitely many positive integers } 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.