Maths Olympiad Prep

Library / /25 of 42

Number theory Difficulty 6.3 National olympiad Prove it Romania

a) Prove that the numbers of the positive divisors of 137137, 138138 and 139139 are integer powers of 22.

b) What is the largest number of consecutive positive integers such that each of them has the number of its positive divisors a power of 22?

Solution

a) The numbers 137137 and 139139 are prime (137<139<132137 < 139 < 13^2 and they have no positive divisors less than 1313), so each of them have 212^1 divisors.
Since 138=2131231138 = 2^1 \cdot 3^1 \cdot 23^1, it results that 138138 has 222=232 \cdot 2 \cdot 2 = 2^3 positive divisors.

b) Extend the sequence 137137, 138138, 139139 with four new numbers to obtain the 77-element sequence 133133, 134134, 135135, 136136, 137137, 138138, 139139 such that each number has a number of positive divisors that is a power of 22. Indeed, the numbers 136=2317136 = 2^3 \cdot 17, 135=335135 = 3^3 \cdot 5, 134=267134 = 2 \cdot 67, 133=719133 = 7 \cdot 19 have, respectively, 88, 88, 44, 44 positive divisors.
We will prove that there are no 88 consecutive numbers with the requested property. To this end, remark that among 88 consecutive numbers there is one that leaves the remainder 44 when divided by 88, that is a number aa of the form a=8k+4=22(2k+1)a = 8k+4 = 2^2(2k+1). In the prime factors decomposition of aa, the prime 22 appears at the second power and 2k+12k+1 is not a multiple of 22. In consequence, the number of positive divisors of aa is divisible by 2+1=32+1=3, so it is not a power of 22.
Consequently, the largest sequence of consecutive positive integers with the numbers of their positive divisors powers of 22 has 77 elements.

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.