Maths Olympiad Prep

Library / /26 of 42

Number theory Difficulty 6.4 National olympiad Prove it Romania

a) Prove that 12n+1312n+13 and 13n+1413n+14 are coprime, for every natural nn.

b) Find the number of the pairs (a,b)(a, b) of natural numbers for which there exists a natural number nn so that ab=12n+1313n+14\frac{a}{b} = \frac{12n+13}{13n+14} and 17a+19b<202417a + 19b < 2024.

Solution

a) If dd is a common divisor of the numbers 12n+1312n + 13 and 13n+1413n + 14, then dd divides the numbers 13(12n+13)13(12n + 13) and 12(13n+14)12(13n + 14). Then dd divides 13(12n+13)12(13n+14)13(12n + 13) - 12(13n + 14), that is d1d \mid 1. So d=1d = 1, hence the numbers 12n+1312n + 13 and 13n+1413n + 14 are coprime.

b) The relation ab=12n+1313n+14\frac{a}{b} = \frac{12n+13}{13n+14} leads to a(13n+14)=b(12n+13)a(13n+14) = b(12n+13), hence 13n+14b(12n+13)13n+14 \mid b(12n+13). Since 12n+1312n + 13 and 13n+1413n + 14 are coprime, 13n+1413n + 14 divides bb. Since

b0b \neq 0 (it is the denominator of a fraction), there exists kNk \in \mathbb{N}^* so that b=k(13n+14)b = k(13n+14) and therefore a=k(12n+13)a = k(12n+13).

Replace a=k(12n+13)a = k(12n + 13) and b=k(13n+14)b = k(13n + 14) in 17a+19b<202417a + 19b < 2024 to get
k(451n+487)<2024k(451n + 487) < 2024. Then 451n+487<2024451n + 487 < 2024, whence n3n \le 3.

For n=0n = 0 we get k4k \le 4, so (a,b){(13,14),(26,28),(39,42),(52,56)}(a, b) \in \{(13, 14), (26, 28), (39, 42), (52, 56)\}.
For n=1n = 1 we get k2k \le 2, so (a,b){(25,27),(50,54)}(a, b) \in \{(25, 27), (50, 54)\}.
For n{2,3}n \in \{2, 3\} we get k=1k = 1, so (a,b){(37,40),(49,53)}(a, b) \in \{(37, 40), (49, 53)\}.

In total, there are 8 pairs.

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 and solution reproduced as published; topic and difficulty added by this site.