Kongruensräkning
Hej! Jag har fastnat på en uppgift:
Bestäm det minsta positiva heltalet x som uppfyller x≡7(mod11)och x≡11(mod17).
Jag antog först att x borde vara en gemensam rest för båda ekvationerna.
7=11K1+x och 11=17K2+x
Men när jag sätter dessa lika med varandra (x=x) har vi fortfarande två okända konstanter som vi inte kan räkna med.
Jag undrar om jag är helt ute och cyklar? Hur kommer jag vidare härifrån? Eller bör jag använda en annan metod för att lösa problemet?
Tack i förhand!
Om x är 7 mod 11 borde det innebära att
x= K1*11+7
Om x är 11 mod 17 borde det innebära att
x= K2*17+11
Vi har då två sätt att uttrycka x på
K1*11+7 = K2*17+11
som du mer eller mindre sade, fast jag är osäker på sättet som du beskrev det på.
Likt dig är jag osäker på om detta är det bästa sättet att jobba på, men låt oss likväl pröva: Om vi nu prövar oss fram med olika heltalsvärden på K1 tills att vi får ett värde sådant att vänsterledets rest då man dividerar med 17 är 11 så har vi ett K1-värde som uppfyller uppgiftens beskrivning.
| K1 | K1*11+7 (= x) | x mod 17 |
| 1 | 18 | 1 |
| 2 | 29 | 12 |
| 3 | 40 | 6 |
| 4 | 51 | 0 |
| 5 | 62 | 11 |
Så 62 borde funka. Sedan är frågan om det är det minsta. Vid uträknandet av en ny rad i högre kolumnen kan man bara lägga till 11 från föregående rad samt subtrahera med 17 om talet överstiger 17 för att få den nya resten, så mittenkolumnen kan egentligen skippas fram tills att man hittat rätt rest.
Bedinsis skrev:Om x är 7 mod 11 borde det innebära att
x= K1*11+7
Om x är 11 mod 17 borde det innebära att
x= K2*17+11
Vi har då två sätt att uttrycka x på
K1*11+7 = K2*17+11
som du mer eller mindre sade, fast jag är osäker på sättet som du beskrev det på.
Likt dig är jag osäker på om detta är det bästa sättet att jobba på, men låt oss likväl pröva: Om vi nu prövar oss fram med olika heltalsvärden på K1 tills att vi får ett värde sådant att vänsterledets rest då man dividerar med 17 är 11 så har vi ett K1-värde som uppfyller uppgiftens beskrivning.
K1 K1*11+7 (= x) x mod 17 1 18 1 2 29 12 3 40 6 4 51 0 5 62 11 Så 62 borde funka. Sedan är frågan om det är det minsta. Vid uträknandet av en ny rad i högre kolumnen kan man bara lägga till 11 från föregående rad samt subtrahera med 17 om talet överstiger 17 för att få den nya resten, så mittenkolumnen kan egentligen skippas fram tills att man hittat rätt rest.
Då tror jag att jag fattar! Tack!
Så i det här fallet är resterna 7 och 11 för x, istället för att x är resten vid division med 7 och 11 (som jag skrev från början). Då fattar jag din lösning.
Men det känns som en lång formulering – finns det en mer effektiv metod?
Facitsvar är 62, men hur hittar man minsta tal om det finns en sådan vid ett annat sammanhang? Hade du kunnat förklara det tydligare? "Vid uträknandet av en ny rad i högre kolumnen kan man bara lägga till 11 från föregående rad samt subtrahera med 17 om talet överstiger 17 för att få den nya resten, så mittenkolumnen kan egentligen skippas fram tills att man hittat rätt rest."
Vi prövar alla möjliga värden på vänsterledet genom att gradvis öka K1 i steg om 1. Med andra ord så lägger vi till 11 till föregående tal.
Om vi vet om att vi har ett tal (t.ex. 51) vars rest vid division med 17 blir ett visst värde (t.ex. 0), vad blir då resten om man lägger till 11 till talet?
Då man dividerar frågar man ju sig egentligen hur många hela exemplar av nämnaren som täljaren kan innehålla och säger bara att "och sedan har vi en rest som vi skulle velat dela med men det gick ju inte jämnt ut". Om vi nu lägger till 11 är det som att vi vill undersöka om den gamla resten plus det vi lade till är stort nog för att vi ska kunna ta bort ytterligare ett exemplar av nämnaren. Detta inträffar om [den gamla resten]+11 överstiger 17, då kan vi vid division med 17 ta bort ytterligare ett exemplar av 17, i annat fall så blir den nya resten den gamla plus 11.
Jag vet inte om det finns en mer effektiv metod.
Ekvationen i exemplet är ju en diofantisk ekvation. Det finns ju lösningsmetoder, men de går man inte igenom på gymnasiet (tror jag). För ekvationer av den här typen använder man en metod som bygger på Euklides algoritm:
Har använt Euklides utökade algoritm för att lösa diofantiska ekvationer i matte 5.
