Maths Olympiad Prep

Library / /234 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

3. We will call a natural number nn amusing if for any of its natural divisors dd, the number d+2d+2 is prime.

( a ) What is the maximum number of divisors an amusing number can have?

(b) Find all amusing numbers with the maximum number of divisors.

Answer: a maximum of 8 divisors, only one amusing number 3353^{3} \cdot 5.

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

Solution

Solution. Among the divisors of a funny number, there cannot be a two or a prime dd with a remainder of 1 when divided by 3 (otherwise, the prime d+2d+2 would be divisible by 3, implying d=1d=1). Therefore, the divisors can only be threes (and their powers) and at most one prime divisor p2(mod3)p \equiv 2(\bmod 3) (if there is another such divisor qq, then d=pq1(mod3)d=p q \equiv 1(\bmod 3) and d+2d+2, divisible by 3,3, is not prime). Moreover, the power of three cannot be greater than 4, since otherwise there would be a divisor d=35d=3^{5}, for which d+2=245d+2=245 is not prime.

Can a funny number have the form 3kp3^{k} \cdot p for k<5k<5?

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.