Given $n$, find $2$ positive integers $a,b$ such that $a+b=n$ and $LCM(a,b)$ is as minimum as possible This is a problem in a previous math/coding contest.
I broke this down into $2$ cases: $n$ is even or $n$ is odd. When $n$ is even, that means that $a=b=n/2$, because, intuitively, if we take $a < n/2$ (WLOG), then $b > n/2$, and so $LCM(a,b) \ge b > n/2$.
When $n$ is odd, I couldn't figure out how to do it. The only way I came up with was to brute force all values of $a$ (again, WLOG) from $1$ up until $n/2$, but this is way too slow when $n$ is large.
Any help would be much appreciated.
 A: The answer is $a=k, b=n-k$ for odd $n>1$  and the largest proper (i.e., $<n$) divisor $k$ of $n$ and $a=b=n/2$ for even $n$.
Proof. Suppose $n$ is odd, $k+(n-k)$ is the decomposition of $n$ with the smallest  $LCM(k, n-k)$. Case 1. If $k$ divides $n$ then it divides $n-k$ and the $LCM$  is $n-k$, so in this case it is better to take $k$ to be the largest proper divisor of $n$.
Case 2. If $k$ does not divide $n$, then it does not divide $n-k$, so the $LCM$ is $k(n-k)/gcd(n,k)$. Let $k/gcd(n,k)=m$. Let $gcd(n,k)=d$. Then $k=md$. Then the decomposition is $md+(n-2d)$ and the $LCM$ is $m(n-2d)=mn-2md$. To be minimal we should have $mn-2md<n-d$, so $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. But since $n$ is odd and divisible by $d$ it implies $n\ge 3d$, so $3(m-1)/(2m-1)<1$, $m<3$ so $m=2$, which easily leads to a contradiction. Hence the minimum LCM is attained in Case 1 when $k$ is the largest proper ($\ne n$) divisor of $n$. $\Box$
A: I have written my own proof:
If $n$ is even, the answer is obviously $a = b = n/2$, since if we take $a < n/2$ (WLOG), that means that $b > n/2$, and so $LCM(a,b) \ge b > n/2$.
If $n$ is odd, the answer is $a = k$, $b = n-k$, where $k$ is the largest divisor of $n$.
Note that $k$ cannot be equal to $n$, since then we would have $a = n$, $b = 0$, but the question asks for $2$ positive integers.
Also note that $k$ can be at most $n/2$ after isolating the largest divisor($n$). This implies that $n-k \ge n/2$.
Now, why should $k$ be a divisor? Well,  it's  simple:
If $k|n$, then $k|n-k$, and so $LCM(k,n-k) = n-k < n$.
But, if $k \nmid n$, then $k \nmid n-k$, and so $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.
Done.
A: If $a+b = n$ then $\gcd(a,b)|n$.
For any $d|n$ let $M_d$ be the minimum possible value of $\operatorname{lcm}(a,b)$ where $a+b = n$ and $\gcd(a,b) =d$.
Then we need to find $\min M_d$ for all $d|n$.
Let $d|n$.
We can find $a+b =n$ so that $\gcd(a,b) =d$ by letting $a=kd; k < \frac nd$ and $b=(\frac nd -k)d$.  If $\gcd(j,k)\ne 1$ we can always add or subtract values from $j,k$ (turns out this isn't that important so we don't need to go into detail).
$\operatorname{lcm}(a,b) = \frac {ab}{\gcd(a,b)} = jkd$.  Now $jk$ have the condition that $j+k = \frac nd = c$ a constant.  We can minimize $jkd$ but minimizing $jk$ which we can do by setting $j$ and $k$ as far apart as possible (that's just AM.GM. in revers); i.e. by setting $j=1$ and $k = \frac nd -1$ (and as $\gcd(1, \frac nd -1) =1$ that is why I said we wouldn't need to go into details).
Of for any given $d|n$ (and if $d=\gcd(a,b)$ then $d|n$) we can find a minimum such $ab$ so that $\operatorname{lcm}(a,b)= 1*(\frac nd -1)*d = n-d$.
So $M_d = n-d$.
And the minimum value of $M_d$ is $n-d$ where $d$ is the largest proper factor of $n$.
(We can't have $d = n$ because then $a,b \ge n$ and $a+b \ne n$.  But we can have $d=1$ if $n$ is prime.)
So in your case if $n$ is even then the largest proper divisor is $\frac n2$ and we have if $a= \frac n2*1$ and $b= \frac n2*(2-1)$ we have minimized it.
But any other $n = \prod p_i^{k_i}$ where $p_i$ are prime and $p_1 < p_2 .....$ then
$a = p_1^{k_1-1}\prod_{i>1}p_i^{k_i}$ and $b =  p_1^{k_1-1}\prod_{i>1}p_i^{k_i}(p_1-1)$ then $\operatorname{lcm}(a,b) = n- p_1^{k_1-1}\prod_{i>1}p_i^{k_i}$
