Maths Olympiad Prep

Library / /3 of 32

, 2010

Number theory Difficulty 4.7 AIME Prove it Estonia

Call a positive integer nn prime-prone if there exist at least three prime numbers from which we can get nn by removing the last digit. Prove that every two prime-prone positive integers differ from each other by at least 33. (Juniors.)

Solution

As the prime numbers under consideration have at least two digits, the last digit can be only 11, 33, 77, or 99. Thus nn is prime-prone if and only if, among numbers 10n+110n + 1, 10n+310n + 3, 10n+710n + 7, and 10n+910n + 9, at least three are primes.

If n=3kn = 3k, then 10n+3=30k+310n + 3 = 30k + 3 and 10n+9=30k+910n + 9 = 30k + 9 are divisible by 33 and hence composite. If n=3k+2n = 3k + 2, then 10n+1=30k+2110n + 1 = 30k + 21 and 10n+7=30k+2710n + 7 = 30k + 27 are divisible by 33 and hence composite again. Consequently, all prime-prone integers are congruent to 11, and hence to each other, modulo 33. Thus they differ by a multiple of 33, i.e., by at least 33.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.