Данный $n$, найти $2$ положительные целые числа $a,b$ такой, что $a+b=n$ и $LCM(a,b)$ как минимум

Aug 16 2020

Это проблема в предыдущем конкурсе по математике / кодированию.

Я разбил это на $2$ случаи: $n$ даже или $n$странно. Когда$n$ четное, это означает, что $a=b=n/2$, потому что интуитивно, если взять $a < n/2$ (WLOG), затем $b > n/2$, и так $LCM(a,b) \ge b > n/2$.

Когда $n$странно, я не мог понять, как это сделать. Единственный способ, который я придумал, - это перебрать все значения$a$ (снова WLOG) из $1$ до $n/2$, но это слишком медленно, когда $n$ большой.

Любая помощь приветствуется.

Ответы

1 JCAA Aug 16 2020 at 02:01

Ответ $a=k, b=n-k$ для нечетных $n>1$ и наибольшее собственное (т. е. $<n$) делитель $k$ из $n$ и $a=b=n/2$ даже для $n$.

Доказательство. Предположим$n$ странно, $k+(n-k)$ является разложением $n$ с самым маленьким $LCM(k, n-k)$. Случай 1. Если$k$ разделяет $n$ затем он делит $n-k$ и $LCM$ является $n-k$, поэтому в этом случае лучше взять $k$ быть наибольшим собственным делителем $n$. Случай 2. Если$k$ не разделяет $n$, то он не делит $n-k$, так что $LCM$ является $k(n-k)/gcd(n,k)$. Позволять$k/gcd(n,k)=m$. Позволять$gcd(n,k)=d$. потом$k=md$. Тогда разложение будет$md+(n-2d)$ и $LCM$ является $m(n-2d)=mn-2md$. Чтобы быть минимальным, мы должны иметь$mn-2md<n-d$, так $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Но с тех пор$n$ нечетно и делится на $d$ это подразумевает $n\ge 3d$, так $3(m-1)/(2m-1)<1$, $m<3$ так $m=2$, что легко приводит к противоречию. Следовательно, минимум НОК достигается в случае 1, когда$k$ является наибольшим собственным ($\ne n$) делитель $n$. $\Box$

skar90 Aug 16 2020 at 16:00

Я написал собственное доказательство:

Если $n$ четный, ответ очевиден $a = b = n/2$, поскольку если взять $a < n/2$ (WLOG), это означает, что $b > n/2$, и так $LCM(a,b) \ge b > n/2$.

Если $n$ странно, ответ $a = k$, $b = n-k$, где $k$ является наибольшим делителем $n$. Обратите внимание, что$k$ не может быть равным$n$, с тех пор у нас было бы $a = n$, $b = 0$, но вопрос требует $2$ положительные целые числа.

Также обратите внимание, что $k$ может быть самое большее $n/2$ после выделения наибольшего делителя ($n$). Это означает, что$n-k \ge n/2$.

Теперь, почему $k$быть делителем? Ну все просто:

Если $k|n$, тогда $k|n-k$, и так $LCM(k,n-k) = n-k < n$. Но если$k \nmid n$, тогда $k \nmid n-k$, и так $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Готово.