Question

Hej, słuchajcie.. Robie zadanie z matmy i mam pytanie do kogoś mądrego :)

"Korzystając z algorytmu Euklidesa znaleźć NWD podanych par liczb, a następnie przedstawić go w postaci kombinacji liniowej [tzn. NWD(a,b)=ax+by] .

a=20

b=14

Obliczyłam już:

20=14*1+6

14=6*2+2

6=2*3+0

NWD(20,14)=2

I dalej mam pytanie jak to przedstawić w postaci kombinacji liniowej?

Te liczby x i y mam zgadywać tak, żeby pasowało czy je się jakoś oblicza?

Będę bardzo wdzięczna za pomoc :)

Answer 1

Przy obliczaniu kombinacji liniowej najważniejsze są poprzednie obliczenia:

20=14*1+6

14=6*2+2

 

Teraz przepisujemy te równania tak, aby wyliczyć ostatnie elementy:

(1)...   6 = 20 - 14 * 1

(2)...   2 = 14 - 6 * 2

 

Kombinacje wyliczamy podstawiając powyższe zależności od końca, czyli:

 

2 == korzystamy z (2) ==  14 - 6 * 2 == korzystamy z (1) == 14 - (20-14*1)*2 = 14 - 20*2 + 14*2 = 14*3 - 20*2

 

czyli 2 = 3 * 14 - 2 * 20

 

 

 

 

Weźmy inny przykład:

NWD(60,73)

 

73 = 1*60 + 13

60 = 4*13 + 8

13 = 1*8 + 5

8 =1*5 + 3

5 = 1*3 + 2

3 = 1*2 + 1

2 = 2*1 + 0

 

Czyli NWD(60,73) = 1

 

Teraz przepisujemy powyższe równania:

13 = 73 - 1*60

8 = 60 - 4*13

5 = 13 - 1*8

3 = 8 - 1*5

2 = 5 - 1*3

1 = 3 - 1*2

 

i podstawiamy kolejno (najważniejsze żeby nie wyliczać pogrubionych elementów, tylko grupować po nich):

1 = 3 - 1*2 =

= 3 - 1*(5 - 1*3) = 3 - 5 + 3 = 2*3 - 5 =

= 2*(8 - 1*5) - 5 = 2*8 - 2*5 - 5 = 2*8 - 3*5 =

= 2*8 - 3*(13-1*8) = 2*8 - 3*13 + 3*8 = 5*8 - 3*13 =

= 5*(60-4*13) - 3*13 = 5*60 - 20*13 - 3*13 = 5*60 - 23*13 =

= 5*60 - 23*(73 - 1*60) = 5*60 - 23*73 + 23*60 =

= 28*60 - 23*73