A positive integer is written on the blackboard. In each step we replace the number by the sum of any two positive integers whose product is equal to the number on the board. Determine the smallest number that can be obtained after a finite number of steps in terms of the initial number .
Solution
First, let us show the following: if the number on the blackboard has decreased after the change, then the new number is greater than or equal to . We cannot obtain the number because the sum of two positive integers can never be equal to . The number can only be obtained from , the number can only be obtained from , and the number can only be obtained from or . So, if the number obtained is less than , then it has not decreased during the change. If the starting number was , then we cannot get a smaller number.
Now, let us show that if a number is greater than , then it can be reduced. Assume that the number is on the blackboard at a given time. If is even, i.e. of the form , where is a positive integer, then it can be replaced by . In this way we have obtained a number smaller than , since the condition is equivalent to the assumption . If is odd, then we can express it as , where is a positive integer. In this case, we can first replace it by and then with . Once again we have obtained a number smaller than , because the condition is equivalent to our assumption . Therefore, if the starting number is , we can reduce it to the number , using a finite number of steps, and according to the reasoning above this is the smallest number that can be obtained.
The smallest number we can obtain after a finite number of steps is equal to if and is equal to .