Maths Olympiad Prep

Library / /122 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

Determine all pairs (a,b)(a, b) of positive integers for which

a+b=φ(a)+φ(b)+gcd(a,b). a+b=\varphi(a)+\varphi(b)+\operatorname{gcd}(a, b) .

Here, φ(n)\varphi(n) is the number of integers kk in {1,2,,n}\{1,2, \ldots, n\} such that gcd(n,k)=1\operatorname{gcd}(n, k)=1.

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

Solution

First, let a=1a=1. It holds that φ(1)=1\varphi(1)=1. For all positive integers bb, we have ggd(a,b)=1\operatorname{ggd}(a, b)=1, so the equation becomes 1+b=1+φ(b)+11+b=1+\varphi(b)+1, thus φ(b)=b1\varphi(b)=b-1. Therefore, there is exactly one number in {1,2,,b}\{1,2, \ldots, b\} that is not coprime with bb; this must be bb itself (since ggd(b,b)>1\operatorname{ggd}(b, b)>1 unless b=1b=1, but in that case φ(b)=b\varphi(b)=b). This implies that bb is a prime number. The equation holds for all prime numbers. We conclude that (1,p)(1, p) is a solution for all prime numbers pp. Similarly, b=1b=1 gives the solutions (p,1)(p, 1).

Now, we assume that a,b2a, b \geq 2. Since ggd(b,b)>1\operatorname{ggd}(b, b)>1, it follows that φ(b)b1\varphi(b) \leq b-1. Therefore,

ggd(a,b)=a+bφ(a)φ(b)aφ(a)+1 \operatorname{ggd}(a, b)=a+b-\varphi(a)-\varphi(b) \geq a-\varphi(a)+1

Let pp be the smallest prime divisor of aa (which exists, since a2a \geq 2). Since for all multiples of pp, tpat p \leq a, we have ggd(tp,a)>1\operatorname{ggd}(t p, a)>1, it follows that aφ(a)1paa-\varphi(a) \geq \frac{1}{p} \cdot a. Therefore,

ggd(a,b)aφ(a)+1ap+1 \operatorname{ggd}(a, b) \geq a-\varphi(a)+1 \geq \frac{a}{p}+1

The largest two divisors of aa are aa and ap\frac{a}{p}. Since ggd(a,b)\operatorname{ggd}(a, b) is a divisor of aa that is at least ap+1\frac{a}{p}+1, it must be equal to aa. Thus, ggd(a,b)=a\operatorname{ggd}(a, b)=a. By a completely analogous argument, we can prove that ggd(a,b)=b\operatorname{ggd}(a, b)=b. Therefore, a=ba=b.

Now the equation becomes 2a=2φ(a)+a2 a=2 \varphi(a)+a, or a=2φ(a)a=2 \varphi(a). We see that 2a2 \mid a. Therefore, write a=2kma=2^{k} \cdot m with k1k \geq 1 and mm odd. Then, by a known property of the φ\varphi-function, we have φ(a)=φ(2k)φ(m)=2k1φ(m)\varphi(a)=\varphi\left(2^{k}\right) \varphi(m)=2^{k-1} \cdot \varphi(m), so the equation becomes 2km=22k1φ(m)2^{k} \cdot m=2 \cdot 2^{k-1} \cdot \varphi(m), or m=φ(m)m=\varphi(m). This implies m=1m=1. Therefore, a=b=2ka=b=2^{k}, and the equation indeed holds.

We conclude that the solutions are: (1,p)(1, p) and (p,1)(p, 1) for all prime numbers pp, and (2k,2k)\left(2^{k}, 2^{k}\right) for all positive integers kk.

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.