Donné $n$, trouver $2$ entiers positifs $a,b$ tel que $a+b=n$ et $LCM(a,b)$ est aussi minimum que possible

Question

C'est un problème dans un précédent concours de mathématiques / codage.

Je l'ai décomposé en $2$ cas: $n$ est pair ou $n$est impair. Quand$n$ est pair, cela signifie que $a=b=n/2$, parce que, intuitivement, si nous prenons $a < n/2$ (WLOG), puis $b > n/2$, et donc $LCM(a,b) \ge b > n/2$.

Quand $n$est étrange, je ne savais pas comment faire. Le seul moyen que j'ai trouvé était de forcer brutalement toutes les valeurs de$a$ (encore une fois, WLOG) de $1$ jusqu'à $n/2$, mais c'est bien trop lent quand $n$ est large.

Toute aide serait très appréciée.

Answer 1

La réponse est $a=k, b=n-k$ pour bizarre $n>1$ et le plus grand proprement dit (c.-à-d. $<n$) diviseur $k$ de $n$ et $a=b=n/2$ même pour $n$.

Preuve. Supposer$n$ est impair, $k+(n-k)$ est la décomposition de $n$ avec le plus petit $LCM(k, n-k)$. Cas 1. Si$k$ se divise $n$ puis il se divise $n-k$ et le $LCM$ est $n-k$, donc dans ce cas, il vaut mieux prendre $k$ être le plus grand diviseur propre de $n$. Cas 2. Si$k$ ne divise pas $n$alors ça ne divise pas $n-k$, alors le $LCM$ est $k(n-k)/gcd(n,k)$. Laisser$k/gcd(n,k)=m$. Laisser$gcd(n,k)=d$. ensuite$k=md$. Alors la décomposition est$md+(n-2d)$ et le $LCM$ est $m(n-2d)=mn-2md$. Pour être minimal, nous devrions avoir$mn-2md<n-d$, donc $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Mais depuis$n$ est impair et divisible par $d$ ça implique $n\ge 3d$, donc $3(m-1)/(2m-1)<1$, $m<3$ donc $m=2$, ce qui conduit facilement à une contradiction. Par conséquent, le LCM minimum est atteint dans le cas 1 lorsque$k$ est le plus grand proprement dit ($\ne n$) diviseur de $n$. $\Box$

Answer 2

J'ai rédigé ma propre preuve:

Si $n$ est égal, la réponse est évidemment $a = b = n/2$, puisque si nous prenons $a < n/2$ (WLOG), cela signifie que $b > n/2$, et donc $LCM(a,b) \ge b > n/2$.

Si $n$ est étrange, la réponse est $a = k$, $b = n-k$, où $k$ est le plus grand diviseur de $n$. Notez que$k$ ne peut pas être égal à$n$, depuis lors nous aurions $a = n$, $b = 0$, mais la question demande $2$ entiers positifs .

Notez également que $k$ peut être au plus $n/2$ après avoir isolé le plus grand diviseur ($n$). Cela implique que$n-k \ge n/2$.

Maintenant, pourquoi devrait $k$être un diviseur? Eh bien, c'est simple:

Si $k|n$, puis $k|n-k$, et donc $LCM(k,n-k) = n-k < n$. Mais si$k \nmid n$, puis $k \nmid n-k$, et donc $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Terminé.