Maths Olympiad Prep

Library / /42 of 68

Number theory Difficulty 5.6 AIME, harder Prove it Estonia

Let the odd part of a positive integer nn be the greatest odd integer that divides nn.
Does there exist a positive odd integer that cannot be represented as a product of the odd parts of two consecutive positive integers?

Solutions — 2

Solution 1

Let us show that number 1111 cannot be represented as a product of the odd parts of two consecutive positive integers. Assume the opposite: let 11=xy11 = x \cdot y, where xx and yy are the odd parts of two consecutive positive integers. As 1111 is a prime number, either x=1x = 1 and y=11y = 11 or x=11x = 11 and y=1y = 1. As of the two consecutive integers one is always odd and the odd part of an odd number is the number itself, either xx or yy is one of the two consecutive integers. If it is 11, then the other number can only be 22, but the odd part of 22 is not 1111. If it is 1111, then the other number can only be 1010 or 1212, but neither of those has odd part equal to 11. In all cases we got a contradiction which proves the statement.

Solution 2

Let us show 1111 cannot be represented in the required way. If this representation existed, then due to the primality of 1111 the factors would have to be 11 and 1111. Therefore one of the two consecutive integers has to be divisible by 1111. But this number cannot be 1111 itself, since neither 1010 nor 1212 has 11 as its odd part. It also cannot be an odd multiple of 1111, because then its odd part would be the number itself rather than 1111. Finally, it cannot be an even multiple of 1111, since in such case the neighbouring numbers would be odd numbers greater than 11, the odd parts of which are numbers themselves rather than 11.

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.