Verilen $n$bul $2$ pozitif tam sayılar $a,b$ öyle ki $a+b=n$ ve $LCM(a,b)$ olabildiğince minimum

Question

Bu, önceki bir matematik / kodlama yarışmasında bir sorundur.

Bunu parçaladım $2$ vakalar: $n$ eşit mi $n$garip. Ne zaman$n$ eşit mi, bu demek oluyor ki $a=b=n/2$çünkü sezgisel olarak, eğer alırsak $a < n/2$ (WLOG), sonra $b > n/2$, ve bu yüzden $LCM(a,b) \ge b > n/2$.

Ne zaman $n$tuhaf, nasıl yapılacağını bulamadım. Ortaya çıkardığım tek yol, tüm değerleri kaba kuvvet uygulamaktı.$a$ (tekrar, WLOG) $1$ kadar kadar $n/2$ama bu çok yavaş $n$ büyük.

Herhangi bir yardım çok takdir edilecektir.

Answer 1

Cevap $a=k, b=n-k$ garip için $n>1$ ve en büyük uygun (yani, $<n$) bölen $k$ nın-nin $n$ ve $a=b=n/2$ hatta $n$.

Kanıt. Varsayalım$n$ garip, $k+(n-k)$ ayrışması $n$ en küçüğü ile $LCM(k, n-k)$. Durum 1. Eğer$k$ böler $n$ sonra bölünür $n-k$ ve $LCM$ dır-dir $n-k$yani bu durumda almak daha iyidir $k$ en büyük uygun bölen olmak $n$. Durum 2. Eğer$k$ bölünmez $n$o zaman bölünmez $n-k$, Böylece $LCM$ dır-dir $k(n-k)/gcd(n,k)$. İzin Vermek$k/gcd(n,k)=m$. İzin Vermek$gcd(n,k)=d$. Sonra$k=md$. Sonra ayrışma$md+(n-2d)$ ve $LCM$ dır-dir $m(n-2d)=mn-2md$. Minimal olması için sahip olmalıyız$mn-2md<n-d$, yani $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Ama o zamandan beri$n$ garip ve bölünebilir $d$ ima ediyor $n\ge 3d$, yani $3(m-1)/(2m-1)<1$, $m<3$ yani $m=2$kolayca bir çelişkiye yol açar. Dolayısıyla, asgari LCM, Durum 1'de$k$ en büyük özellik ($\ne n$) bölen $n$. $\Box$

Answer 2

Kendi kanıtımı yazdım:

Eğer $n$ eşit, cevap belli ki $a = b = n/2$çünkü eğer alırsak $a < n/2$ (WLOG), bunun anlamı $b > n/2$, ve bu yüzden $LCM(a,b) \ge b > n/2$.

Eğer $n$ tuhaf, cevap $a = k$, $b = n-k$, nerede $k$ en büyük bölen $n$. Bunu not et$k$ eşit olamaz$n$o zamandan beri bizde $a = n$, $b = 0$ama soru soruyor $2$ pozitif tamsayılar.

Ayrıca şunu unutmayın $k$ en fazla olabilir $n/2$ en büyük bölen ($n$). Bu şu anlama gelir$n-k \ge n/2$.

Şimdi neden $k$bölen olmak Şey, çok basit:

Eğer $k|n$, sonra $k|n-k$, ve bu yüzden $LCM(k,n-k) = n-k < n$. Ama eğer$k \nmid n$, sonra $k \nmid n-k$, ve bu yüzden $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Bitti.