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
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.
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).
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?
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.
