Euklids udvidede algoritme

Du bør kigge på algoritmen en gang til. Jeg kan ikke se hvorfra du har dine tal men det er helt forkert.

Første trin: Find resten ved division af 723 med 123. Denne rest er mindre end 123, så de 589 du angiver kommer slet ikke i spil

Lav det iøvrigt i et regneark. Det er meget nemmere

Da 712 = 5*123 + 97 har vi sfd(712,123) = sfd(123,97) de næste linier er ikke i orden, men

Da 123 = 1*97 +26 har vi sfd(123,97) = sfd(97,26)       svarer til din 34. linie

Jeps, så er jeg med. Men jeg har stadig problemer med at finde s og t i:

712s + 123t = 1.

Fra:

Da 712 = 5*123 + 97 har vi sfd(712,123) = sfd(123,97)

Da 97 = 3*26 + 19 har vi sfd(97,26) = sfd(26,19)

Da 26 = 1*19 + 7 har vi sfd(26,19) = sfd(19,7)

Da 19 = 2*7 + 5 har vi sfd(19,7) = sfd(7,5)

Da 7 = 1*5 + 2 har vi sfd(7,5) = sfd(5,2)

Da 5 = 2*2 + 1 har vi sfd(5,2) = sfd(2,1)

Da 2 = 1*1 + 1 har vi sfd(2,1) = sfd(1,1)

Da 1 = 1*1 + 0 har vi sfd(1,1) = sfd(1,0)

Derfor har vi = 1

Hvis du sammenligner de forskellige linjer får du sfd(712, 123) = sfd(123, 97= sfd(26,19) = .... = 1

Den sidste ligning er meningsløs = 1 siger ingenting, når der ikke omtales hvad der er = 1

For at finde s og t skal du se på det sidste skema. Her skal du succesivt beregne qi, si og ti.

Først beregnes qi det findes som qi = heltal(r_i-1/r_i-2)  første gang altså som q₁ =heltal(r₀/r_-1) Heltal står for rundet ned til nærmeste hele tal. I eksemplet i filen får du q₁ = heltal(1644/956) = heltal(1,719665) = 1. I din opgave er det q1 = heltal(712/123) = heltal(5,78886) = 5

ri og si findes som r_i = r_i-2-q_i*r_i-1, s_i = s_i-2-q_is_i-1

I filen giver det r₁= 1-1*0 = 1  s₁ = 0-1*1 = -1

q_i har jeg fundet for dem alle. Det er: -, -, 5, 1, 3, 1, 2, 1, 1, 1

Men jeg forstår stadig ikke hvordan s og t kan findes for dem alle.

Det jeg har problemer med at forstå, er:

Vi har jo ikke s_i-2 og s_i-1 Og det samme gælder for t_i-2 og t_i-1. Det er jo dem, jeg skal finde.

r_i og s_i findes som r_i = r_i-2-q_i*r_i-1, s_i = s_i-2-q_is_i-1

der gælder for første beregning r_-1=1 r₀ = 0   s_-1= 0, s₀ = 1

med q₁ = 5 giver det

r₁ = r_-1-5*r₀ = 1-5*0 = 1,  s₁ = s_-1-5*s₀ = 0-5*1 = -5

Næste gang bliver det

r₂=r₀-q₂*r₁      s2 = s₀-q₂*s₁

Du skal succesivt finde q₁, s₁, t₁ derefter q₂, s₂, t₂, dernæst q₃, s₃, t₃ o.s.v.

Jeg ser lige at jeg har benyttet forkerte betegnelser i den første del r skal erstattes med s og s med t

Giver det så:

r2 = r-1-1*r0 = 1-1*0 = 1,  s2 = s-1-1*s0 = 0-1*1 = -1

r3 = r-1-3*r0 = 1-3*0 = 1,  s3 = s-1-1*s0 = 0-3*1 = -3

Er det korrekt?

nej Se tredje sidste line i #7. Du skal hver gang tælle indekset i en op

Hvis det skrives op på samme måde som i din fil

 i         r_i        q_i         s_i          t_i  

-1                 .-           1          0

 0                  -           0          1

 1                 5           1         -5

2                  1

Du skal så i hver beregning bruge de tal, der ligger i de 2 foregående rækker

Så passede den :) Tusind tak for din fantastiske hjælp!