Maths Olympiad Prep

Library / /62 of 101

Number theory Difficulty 6.3 National olympiad Prove it Estonia

Mari writes 8 prime numbers (not necessarily different) to her notebook, all smaller than 200. She then adds 1 to the first number, 2 to the second number and so on until adding 8 to the eighth number. She then finds the product of the eight sums. Find the largest power of two which can divide the product found.

Solution

To have the product divisible by as great power of 2 as possible, each of the factors has to be divisible by the greatest power of 2 possible. By adding an even number to a prime number, the sum is divisible by 2 only if the original prime is even. As the only even prime number is 2, it has to be chosen to all even positions. Their respective sums are 4, 6, 8, and 10, and the respective maximal powers of 2 which they are divisible with are 222^2, 212^1, 232^3, and 212^1. Let's investigate the odd positions one by one.
As 127 is a prime and 127+1127+1 is the maximal power of 2 less than 200+1200+1, the first position is 127. As 125=53125 = 5^3, the maximal power of 2 dividing the third sum cannot be 272^7. However, 61 is a prime and 61+3=2661 + 3 = 2^6, hence 61 is suitable for the third position. As 123=341123 = 3 \cdot 41, the maximal power of 2 dividing the fifth sum cannot be 272^7. However, 5959 is a prime and 59+5=2659 + 5 = 2^6, hence 5959 is suitable for the fifth position. As 121=112121 = 11^2, the maximal power of 2 dividing the seventh sum cannot be 272^7. The natural numbers smaller than 200 which are divisible by 262^6 are 64 and 192. The respective numbers which would result in these numbers are 57=31957 = 3 \cdot 19 and 185=537185 = 5 \cdot 37, neither of which is a prime. However, 89 is a prime and 89+7=32589 + 7 = 3 \cdot 2^5, hence 89 is suitable for the seventh position. In summary, the maximal power of 2 which divides the product of the eight numbers is 27+2+6+1+6+3+5+1=2312^{7+2+6+1+6+3+5+1} = 2^{31}.

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.