Maths Olympiad Prep

Library / /34 of 37

Number theory Difficulty 6.9 National Olympiad Prove it Italy

Problem:

We say that a pair (a,b)(a, b) of positive integers is nice if aa divides bb and a+1a+1 divides b+1b+1.

a. Prove that, for a fixed positive integer aa, there exist infinitely many positive integers bb such that the pair (a,b)(a, b) is nice.

b. Fixed a positive integer aa, determine the minimum integer b>ab>a such that (a,b)(a, b) is nice.

c. Taking now a=18a=18, determine the minimum positive integer b>ab>a such that (a,b)(a, b) is nice and moreover a+2a+2 divides b+2b+2.

Solution

Solution:

By definition, a pair of positive integers (a,b)(a, b) is nice if there exist positive integers k,hk, h such that b=kab=k a and b+1=h(a+1)b+1=h(a+1). In particular, we have ka+1=h(a+1)k a+1=h(a+1) and therefore
h=ka+1a+1. h=\frac{k a+1}{a+1} .
Since hh is an integer, we have that ka+1=k(a+1)(k1)k a+1=k(a+1)-(k-1) is divisible by a+1a+1, from which k1k-1 is divisible by a+1a+1 and therefore there exists a nonnegative integer nn such that k1=n(a+1)k-1=n(a+1). Putting everything together, we obtain that if the pair (a,b)(a, b) is nice then there exists an integer nn such that b=ka=a(na+n+1)b=k a=a(n a+n+1).
On the other hand, if b=a(na+n+1)b=a(n a+n+1) for some nonnegative integer nn, then, clearly, aa divides bb and b+1=(na+n+1)a+1=n(a+1)a+(a+1)b+1=(n a+n+1) a+1=n(a+1) a+(a+1) is divisible by a+1a+1.
Summing up, the pair (a,b)(a, b) is nice if and only if b=a(na+n+1)b=a(n a+n+1) for some positive integer nn.

a. Given aa, there exist infinitely many positive integers bb for which the pair (a,b)(a, b) is nice: indeed, it follows from what was said above that for every positive integer nn the pair (a,a(na+n+1))(a, a(n a+n+1)) is nice.

Second solution: for every odd positive integer dd, the pair of the type (a,ad)(a, a^{d}) is nice: clearly aa divides ada^{d}; moreover ad+1=(a+1)(1a+a2a3++ad1)a^{d}+1=(a+1)(1-a+a^{2}-a^{3}+\ldots+a^{d-1}) is divisible by a+1a+1. We have thus obtained another infinite family of nice pairs (a,b)(a, b) with aa given.

b. Note that, if m>nm>n, then a(ma+m+1)>a(na+n+1)a(m a+m+1)>a(n a+n+1). Since the nice pairs are all and only those of the type (a,a(na+n+1))(a, a(n a+n+1)) (for nn a nonnegative integer) and since for n=0n=0 we have a(na+n+1)=aa(n a+n+1)=a, the minimum integer b>ab>a for which (a,b)(a, b) is nice is obtained for n=1n=1, that is b=a2+2a>ab=a^{2}+2 a>a.

Second solution: Given aa, the minimum bb (such that b>ab>a and (a,b)(a, b) is a nice pair) is a multiple of aa of the type mam a (m>1m>1 integer). I observe that if ma+1m a+1 gives remainder rr upon division by a+1a+1, then (m+1)a+1=(ma+1)+(a+1)1(m+1) a+1=(m a+1)+(a+1)-1 gives remainder r1r-1. Since for m=1m=1 the remainder of the division of ma+1m a+1 by a+1a+1 is zero, the next multiple of aa to have this property will be given when m=a+2m=a+2, that is b=(a+2)ab=(a+2) a.

c. From what was said above, we know that the pair (18,b)(18, b) is nice if and only if b=18(18n+n+1)=18(19n+1)b=18(18 n+n+1)=18(19 n+1). The condition
20=a+2b+2=342n+20, 20=a+2 \mid b+2=342 n+20,
is satisfied if and only if 20 divides 342n342 n or, equivalently, if 10 divides nn. We thus deduce that the minimum b=18(19n+1)b=18(19 n+1) greater than 18 for which the pair (18,b)(18, b) is nice and b+2b+2 divides a+2=20a+2=20 is obtained for n=10n=10, that is b=19118=3438b=191 \cdot 18=3438.

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.