Citat:
Ursprungligen postat av
AntiBus
Kan någon tipsa här?
Vilken punkt med heltalskoordinater ligger närmast origo?
4x+7y=9
ska jag skriva så jag har y=(9-4x)/7 ?
4x + 7y = 9, hitta gcd(4,7):
7=
4·1 + 3 =
3·2 + 1 =
1·7 + 0, gcd = 1.
Skriv 1 som linjärkombination av 4 och 7:
2·4 + -1·7 = 1.
Eftersom 9 ≠ gcd(4,7) = 1 måste VL och HL multipliceras med 9:
18·4 + -9·7 = 9.
x₀=18, y₀=-9 är en heltalslösning. Vad är dom andra? Jo, x = n·7/gcd(4,7) + x₀ = 7n + 18,
y = -n·4/gcd(4,7) + y₀ = -4n - 9. n ∈ ℤ.
Vi kan göra uttrycken lite finare med andra x₀ och y₀ som fås genom att välja något passande n, typ n = -2:
x₀ = 4, y₀ = -1 ⇒
x = 7n + 4,
y = -4n - 1.
Vilken är närmast origo? Vi måste minimera distansen från linjen till origo, √(x² + y²), fast den minimeras om x² + y² minimeras, eftersom x och y är reella. Så vi minimerar (7n + 4)² + (-4n - 1)² genom att sätta derivatan till 0. Då får vi n = -32/65. Eftersom (7n + 4)² + (-4n - 1)² är symmetrisk runt n = -32/65 får vi att närmaste
heltalet som minimerar (7n + 4)² + (-4n - 1)² är n = närmaste heltalet till -32/65 = avrunda(-32/65) = 0.