6 svar
73 visningar
Filipjohanssonn är nöjd med hjälpen!
Filipjohanssonn 35
Postad: 15 sep 2020

11x + 13 ≡ 4 (mod 37)

Hej!

Har svårt att lösa tal av denna typ. 

Jag gör såhär:

Uppgift: 11x + 13 ≡ 4 (mod 37)

11x + 13 = 4 + 37y

11x - 37y = -9

SGD(37,11) = 1

Euklides algoritm ger:

37 = 3 * 11 + 4
11 = 2 * 4 + 3
4 = 1 *3 + 1

1 | (-9) Lösning finns!

Euklides algoritm baklänges för att få ut linjärkombination av diofantiska ekvationen:

1 = 4 - 1*3
     = 4 - (11 - 2*4)
     = (37 - 3*11) - 11 + 2 (37 - 3*11)

Antal 11 = 4
x0 = 4* (-9) = -36
X = -36 + 37/1*n
X = -36 + 37n

Men svaret jag får är fel. X skall vara 16 vilket jag inte vet hur man får ut. Vad gör jag för fel?

Tacksam för lösning!!

 

Mvh Filip

Laguna Online 10346
Postad: 16 sep 2020

Jag är inte säker på det sista du gör. Du har fått 1 = 3*37 - 10*11. Multiplicerar vi med -9 får vi

-9 = -27*37 + 90*11

Vi kan addera nån multipel av 0 = 11*37 - 37*11 för att få mindre tal:
-9 = -16*37 + 53*11
-9 = -5*37 + 16*11
-9 = 6*37 - 21*11

Du behöver inte Euklides metod.  I läroboken bör finnas exempel. I origo hittade jag några.

Filipjohanssonn 35
Postad: 16 sep 2020
rapidos skrev:

Du behöver inte Euklides metod.  I läroboken bör finnas exempel. I origo hittade jag några.

I min lärobok "Diskret matematik" så använder man Euklides algoritm. Min lärare har använt sig av något som kallas "Kedjekvot" för att få fram x0 och y0 men har inte lyckats lösa det.

Enl Lagunas lösning har du x=90. Tar du mod(37) av x = 2*37+16 dvs x kongruent 16 mod(37).

Laguna Online 10346
Postad: 16 sep 2020
Filipjohanssonn skrev:
rapidos skrev:

Du behöver inte Euklides metod.  I läroboken bör finnas exempel. I origo hittade jag några.

I min lärobok "Diskret matematik" så använder man Euklides algoritm. Min lärare har använt sig av något som kallas "Kedjekvot" för att få fram x0 och y0 men har inte lyckats lösa det.

Just ja, kedjebråksmetoden hade jag glömt. Är det att man kapar nedersta biten och sedan gör det hela till ett vanligt bråk igen?

Filipjohanssonn 35
Postad: 16 sep 2020
Laguna skrev:
Filipjohanssonn skrev:
rapidos skrev:

Du behöver inte Euklides metod.  I läroboken bör finnas exempel. I origo hittade jag några.

I min lärobok "Diskret matematik" så använder man Euklides algoritm. Min lärare har använt sig av något som kallas "Kedjekvot" för att få fram x0 och y0 men har inte lyckats lösa det.

Just ja, kedjebråksmetoden hade jag glömt. Är det att man kapar nedersta biten och sedan gör det hela till ett vanligt bråk igen?

Ja exakt. Man tar de tal man har multiplicerat med under Euklides algoritm. 

Svara Avbryt
Close