2020 OIM Problems/Problem 2
Problem
For each positive integer , define
as the smallest positive integer such that
is a multiple of
. For example,
since
,
and
are not multiples of
, but
is a multiple of
. Find all positive integers
such that
.
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
Note the elementary property that will be used without proof: for all positive integers ,
We claim that the only possible are numbers of the form
, where
is a nonnegative integer. First, we show that these numbers do in fact satisfy the condition. By formula, we have
; thus
. Only one of
or
is even.
If is even, then we must have
, which is clearly only possible if
. If
is even, then we must have
; thus
. For all nonnegative
, it is easily shown that
; thus,
so these
satisfy the condition regardless of the parity of
.
Next, we show that these are the only possible . First, assume that
such that
is an odd prime and
is a positive integer. Clearly if
, then the property is satisfied (although this may not be minimal) since we must have
; thus these cases are eliminated. Then consider
as any other odd number. Let
for relatively prime odd integers
; this is possible since we already considered odd
with only one prime factor. Consider all nonnegative integers
such that
By the Chinese Remainder Theorem, there exists some such that the above holds. Clearly
does not work, so there exists some unique
; let this be
. Notice that
would then be divisible by
, so
would satisfy the property (although it may not be minimized); thus we must have
, eliminating this case.
Finally, we consider even . Let
for positive integers
such that
is odd (because we already showed that
works). Then
and
are clearly relatively prime.
Let be nonnegative integers in the interval
such that
Again, since or
clearly do not satisfy the above, then by the Chinese Remainder Theorem, there will always exist some unique integers
in the interval
, so we are able to define them as such above. Next, adding the first/third congruences and the second/fourth congruences:
Notice that
satisfies this system of congruences; by the Chinese Remainder Theorem, this solution is unique. Thus,
However, since
, this implies that
. From the above congruence, the only multiple of
in this interval is
itself; thus,
Assume for the sake of contradiction that both
. Then
, clearly a contradiction. Thus at least one of
, implying that at least one of
. Assume that
; then
is divisible by
from our congruences above, so setting
would suffice; thus
; the same goes for
if
. As a result, this case is also eliminated, so we are done.