równanie
nick: czy takie równanie ma rozwiązanie?
511x+2018y=2
20 wrz 15:11
Bleee:
Ma nawet nieskończenie wiele rozwiązań
20 wrz 15:15
the foxi:
| | 2−511x | |
równanie spełnia nieskończenie wiele par (x,y) postaci (x; |
| ) |
| | 2018 | |
20 wrz 15:26
nick: a jak znaleźć jedno z nich?
20 wrz 15:26
Blee:
podstaw x=0 i wyznacz y
20 wrz 15:40
nick: a jeśli x i y musza być całkowite?
20 wrz 15:56
Mariusz:
x = 466 ⋀ y = −118
20 wrz 20:10
Mariusz:
U Cormena i reszty masz przydatną funkcję
function gcdex(a,b:integer;var x,y:integer):integer;
var d,dp,xp,yp:integer;
begin
if b = 0 then
begin
gcdex:= a;
x:=1;
y:=0;
end
else
begin
dp := gcdex(b, a mod b,xp,yp);
d := dp;
x := yp;
y := xp − (a div b) * yp;
gcdex := d;
end;
end;
20 wrz 20:24
Mila:
511x+2018y=2
NWD(511,2018)=1 i 1|2⇔ równanie ma rozwiązanie
Istnieją liczby całkowite x i y spełniające równanie
511x+2018y=1
Korzystamy z rozszerzonego algorytmu Euklidesa:
2018=3*511+485
511=1*485+26
485=26*18+17
26=1*17+9
17=1*9+8
9=8*1+1
po odwróceniu algorytmu
1=233*511−59*2018 /*2
2=466*511−118*2018
x0=466
y0=−118
x=466+2018*t
y=−118−511*t
==========
20 wrz 21:42
Adamm:
warunek konieczny i wystarczający by równanie
ax+by=c miało rozwiązanie, to by NWD(a, b)|c
20 wrz 22:05
Adamm:
w liczbach całkowitych oczywiście
i wtedy też ma nieskończenie wiele rozwiązań
20 wrz 22:06
Adamm:
sposób na rozwiązanie
wyznaczamy NWD(a, b) za pomocą algorytmu Euklidesa
to sprawi że będziemy mieli ax
0+by
0 = NWD(a, b) dla pewnych x
0, y
0
| | c | |
wtedy wystarczy całość przemnożyć przez |
| by dostać rozwiązanie |
| | NWD(a, b) | |
Mila zastosowała w praktyce
20 wrz 22:08