Maths Olympiad Prep

Library / /6 of 13

Number theory Difficulty 5.3 AIME, harder Prove it Italy

Problem:

Find all pairs (a,b)(a, b) of positive integers such that a+1a+1 is a divisor of b1b-1 and bb is a divisor of a2+a+2a^{2}+a+2.

Solutions — 2

Solution 1

Solution:

Let us consider bb; since a+1a+1 divides b1b-1 we can write b=k(a+1)+1b = k(a+1) + 1, with kk a natural number. Let us reformulate the second condition as (k(a+1)+1)h=a2+a+2(k(a+1)+1) h = a^{2} + a + 2, that is kh(a+1)+h=a(a+1)+2k h(a+1) + h = a(a+1) + 2 for some hNh \in \mathbb{N}.

Let us first suppose that kk is positive; if kh=ak h = a, then h=2h = 2; from this follow the solutions of the type (2k,k(2k+1)+1)(2k, k(2k+1)+1) where kk is a positive integer. If instead kh<ak h < a, then h>a+3h > a+3; on the other hand, if kk is positive, we must have hhkh \leq h k, which is absurd.

There remains the case where kk is 00, and hence b=1b = 1; all pairs (a,1)(a, 1), with aa a positive integer, are indeed solutions.

Solution 2

Solution:

As before, let us write b=k(a+1)+1b = k(a+1) + 1, with kNk \in \mathbb{N} and (k(a+1)+1)h=a2+a+2(k(a+1)+1) h = a^{2} + a + 2 for some hNh \in \mathbb{N}.

We observe that for b=1b = 1 we have k=0k = 0 and aa can be any natural number n>0n > 0, that is, all pairs (n,1)(n, 1) are solutions.

Let us consider the second condition modulo (a+1)(a+1): we have that h2mod(a+1)h \equiv 2 \bmod (a+1). Now, if we had h(a+1)+2h \geq (a+1)+2, excluding the case k=0k=0 already considered, we would get
(k(a+1)+1)h(a+2)h(a+2)(a+3)=a2+a+2+4(a+1)>a2+a+2 (k(a+1)+1) h \geq (a+2) h \geq (a+2)(a+3) = a^{2} + a + 2 + 4(a+1) > a^{2} + a + 2
in contrast with the second condition. Hence h=2h = 2 and 2k(a+1)+2=a(a+1)+22k(a+1) + 2 = a(a+1) + 2, from which a=2ka = 2k. Consequently, substituting into the first condition, we have b=k(2k+1)+1b = k(2k+1) + 1, from which we obtain the other solutions (2k,2k2+k+1)\left(2k, 2k^{2} + k + 1\right), for k>0k > 0 a natural 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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.