与えられた $n$、検索 $2$ 正の整数 $a,b$ そのような $a+b=n$ そして $LCM(a,b)$ 可能な限り最小限です

Question

これは、以前の数学/コーディングコンテストの問題です。

私はこれをに分解しました $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$ は大きい。

どんな助けでも大歓迎です。

Answer 1

答えは $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$、これは簡単に矛盾につながります。したがって、最小LCMは、ケース1で次の場合に達成されます。$k$ 最大の適切な（$\ne n$）の約数 $n$。 $\Box$

Answer 2

私は自分の証拠を書きました：

場合 $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$。

完了。