Lineær kongruens

Brug Euklids udvidet algoritme

Hvad hr det med lineær kongruens at gøre ?

Hvordan anvendes EUA til dette? Man skal altså løse ligningen:

Kan ikke rigtig sætte mig ind i metoden... 

Du skal finde x så 15403x+k*19800 = 1

Euklids algoritme leverer to tal u og v så 15403*u+v*19800 = 1

Ja, her er der stadig to ubekendte i spil. Jeg forstår, at man først skal bestemme SFD(a,b)=1:

Og så er det noget med, at man skal tage den sidste udregning, hvor resten er 1, og regne baglæns. Hvordan gøres dette, kan eksemplificere med et par beregninger. 

Venligst,

//

1= 25-12*2  =25-12(27-25) = ...

1= 25-12*2 = 25-12(27-25)

2=27-1*25=27-1(12*2+1)

25=2185-80*27=2185-80(1*25+2)

Er det her korrekt?

fortsat fra #5

= 13*25-12*27 = 13*(2185-80*27) = ...

Kan du ikke forklare processen med ord? Jeg forstår det simpelthen ikke. Hvad skete der fra svar 5 til 7?

jeg ganger ind i parentsen så jeg har en linearkombination af 25 og 27. på  højre side får du så en linearkombination af 2185 og 27. Næste trin er så at eliminere de 27 så du får en ny linearkombination

1 = 25-12*2  =25-12(27-25)

  = 13*25-12*27 = 13*(2185-80*27)

  = 13*25-12*(1*25+2) = 13*(2185-80*(1*25+2))

Jeg forstår det beklageligvis ikke. 

Beklager der er en fejl i 7. Der skal tilføjes -12*27

4397, 2212, 2185, 27, 25, 2, 1

Du  skal systematisk eliminere disse rester bagfra. du starter med  at eliminere 1 af

1= 25-12*2 så du nu har 1 som en linearkombination af 25 og 2

Dernæst eliminere du den mindste rest 2 ved at bruge næstsidste ligning så du har en linearkombination af resterne 27 og 25

Derefter eliminerer du igen den mindste rest 25 ved at bruge ligningen oven over så du får en linearkombination af 2185 og 27

De følgende vil så give linearkombinationerne af 2212 og 2185, dernæst linearkombinationerne 4397 og 2212 så du ender med at have en linearkombination af dine inputdata