There is some natural number written on the board. An operation is defined as adding to the number its maximal proper divisor. Prove that after some iterations of this operation that we get a number that's divisible by 32020.
I got wrapped up in the (N mod 4) angle from the start but I think the proof can be stated more simply.
If N is even, its largest divisor is N/2. Therefore applying the operation is equivalent to multiplying by 3/2.
If N is odd, applying the operation once will make it even. Applying the operation a second time (multiplying by 3/2) will make it odd again, and more specifically will make it divisible by 3. Now its largest divisor is N/3, so applying the operation is equivalent to multiplying by 4/3.
So if we start with even N, just keep multiplying by 3/2 until it's odd (this will take as many turns as there are factors of 2 in N).
If we start with odd N that isn't divisible by 3, two operations will make it odd and divisible by 3.
Either way we quickly get to an odd number which is divisible by 3. From that point forward, three successive operations will multiply it by 4/3 * 3/2 * 3/2 = 3. So we keep tripling a number that was already a multiple of 3 and thus will eventually be divisible by any power of 3.
|
|
Posted by tomarken
on 2021-03-18 15:29:49 |
Maybe more straightforward
