Dato $n$, trova $2$ interi positivi $a,b$ tale che $a+b=n$ e $LCM(a,b)$ è il minimo possibile

Question

Questo è un problema in un precedente concorso di matematica / codifica.

L'ho scomposto $2$ casi: $n$ è pari o $n$è strano. quando$n$ è pari, questo significa che $a=b=n/2$, perché, intuitivamente, se prendiamo $a < n/2$ (WLOG), quindi $b > n/2$, e così $LCM(a,b) \ge b > n/2$.

quando $n$è strano, non riuscivo a capire come farlo. L'unico modo in cui sono uscito è stato quello di forzare tutti i valori$a$ (di nuovo, WLOG) da $1$ fino al $n/2$, ma è troppo lento quando $n$ è grande.

Qualsiasi aiuto sarebbe molto apprezzato.

Answer 1

La risposta è $a=k, b=n-k$ per dispari $n>1$ e il più grande vero e proprio (cioè $<n$) divisore $k$ di $n$ e $a=b=n/2$ anche $n$.

Prova. Supponiamo$n$ è strano, $k+(n-k)$ è la decomposizione di $n$ con il più piccolo $LCM(k, n-k)$. Caso 1. If$k$ divide $n$ poi si divide $n-k$ e il $LCM$ è $n-k$, quindi in questo caso è meglio prendere $k$ essere il più grande divisore proprio di $n$. Caso 2. If$k$ non divide $n$, quindi non divide $n-k$, così il $LCM$ è $k(n-k)/gcd(n,k)$. Permettere$k/gcd(n,k)=m$. Permettere$gcd(n,k)=d$. Poi$k=md$. Allora la decomposizione è$md+(n-2d)$ e il $LCM$ è $m(n-2d)=mn-2md$. Per essere minimi dovremmo avere$mn-2md<n-d$, così $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Ma da allora$n$ è dispari e divisibile per $d$ implica $n\ge 3d$, così $3(m-1)/(2m-1)<1$, $m<3$ così $m=2$, che porta facilmente a una contraddizione. Quindi il LCM minimo viene raggiunto nel caso 1 quando$k$ è il più grande ($\ne n$) divisore di $n$. $\Box$

Answer 2

Ho scritto la mia prova:

Se $n$ è pari, la risposta è ovviamente $a = b = n/2$, poiché se prendiamo $a < n/2$ (WLOG), questo significa che $b > n/2$, e così $LCM(a,b) \ge b > n/2$.

Se $n$ è strano, la risposta è $a = k$, $b = n-k$, dove $k$ è il più grande divisore di $n$. Notare che$k$ non può essere uguale a$n$, da allora avremmo $a = n$, $b = 0$, ma la domanda chiede $2$ numeri interi positivi .

Nota anche quello $k$ può essere al massimo $n/2$ dopo aver isolato il più grande divisore ($n$). Questo implica che$n-k \ge n/2$.

Ora, perché dovrebbe $k$essere un divisore? Bene, è semplice:

Se $k|n$, poi $k|n-k$, e così $LCM(k,n-k) = n-k < n$. Ma se$k \nmid n$, poi $k \nmid n-k$, e così $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Fatto.