Maths Olympiad Prep

Library / /334 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

Let nN+n \in \mathbf{N}_{+}, and let d(n)d(n) denote the number of all positive divisors of nn, and φ(n)\varphi(n) denote the number of integers in {1,2,,n}\{1, 2, \cdots, n\} that are coprime to nn. Find all non-negative integers cc such that there exists a positive integer nn satisfying
d(n)+φ(n)=n+c, d(n) + \varphi(n) = n + c,

and for each such cc, find all positive integers nn that satisfy the above equation.
(Feng Zhigang, problem contributor)

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

Solution

Let the set of all positive divisors of nn be AA, and let the set of numbers in 1,2,,n1,2, \cdots, n that are coprime with nn be BB. Since there is exactly one number 1AB1 \in A \cap B in 1,2,,n1,2, \cdots, n, we have
d(n)+φ(n)n+1d(n)+\varphi(n) \leqslant n+1.
Thus, c=0c=0 or 1.
(1) When c=0c=0, from d(n)+φ(n)=nd(n)+\varphi(n)=n, we know that there is exactly one number in 1,2,,n1,2, \cdots, n that does not belong to ABA \cup B. If nn is even and n>8n > 8, then n2,n4n-2, n-4 do not belong to ABA \cup B, so nn does not satisfy the equation. If nn is odd, when nn is a prime or 1, d(n)+φ(n)=n+1d(n)+\varphi(n)=n+1 (which falls under case (2)); when nn is a composite number, let n=pq,1<pq,p,qn=pq, 1<p \leqslant q, p, q are both odd numbers. If q5q \geqslant 5, then 2p,4p2p, 4p do not belong to ABA \cup B, so nn does not satisfy the equation.

In summary, only when n8,nn \leqslant 8, n is even, or n9,nn \leqslant 9, n is an odd composite number, does
d(n)+φ(n)=n. d(n)+\varphi(n)=n.

Direct verification shows that nn can only be 6,8,96, 8, 9.
(2) When c=1c=1, from d(n)+φ(n)=n+1d(n)+\varphi(n)=n+1, we know that every number in 1,2,,n1,2, \cdots, n belongs to ABA \cup B. It is easy to see that, in this case, n=1n=1 or a prime number meets the requirement. For the case when nn is even, as discussed above, if nn is even, then n4n \leqslant 4 (consider the number n2n-2); if nn is an odd composite number, let n=pq,3pq,p,qn=pq, 3 \leqslant p \leqslant q, p, q are both odd numbers, in this case, 2p2p does not belong to ABA \cup B, which is a contradiction.
Direct verification shows that n=4n=4 meets the requirement.
Therefore, the nn that satisfies d(n)+φ(n)=n+1d(n)+\varphi(n)=n+1 is 1, 4, or a prime number.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.