Lösa mod system när talen inte är parvis relativt prima
Jag ska lösa systemet ovanför.
Använder mig av följande lösningsalgoritm:
Min fråga är om det finns en lösning på systemet om talen ej är relativt prima?
Med parvis relativt prima menar man att:
gcd(4,7) = 1
gcd(4,10) ska vara 1 men är i detta fall 2.
gcd(7,10) = 1
Om de inte är parvis relativt prima uppkommer ibland motsägelser, exvis om den sista kongruensen hade varit x= 2 mod 10.
Finns ingen motsägelse finns lösningar och då kan man eliminiera redundant information tills man får ett ekvivalent system med relativt prima tal.
I ditt fall kan man rätt enkelt se lösningen x=93 så ingen motsägelse. Då kan du skriva om sista kongruensen till x=3 mod 5 och sedan använda vanlig metod.
Varför kan vi skriva om sista så. Jo om x=3 mod 5 så x=3 mod 10 eller x=8 mod 10. Den andra går inte för då är inte x=1 mod 4. Så givet att x=1 mod 4 så är x=3 mod 5 ekvivalent med x=3 mod 10.
Hur ser du att x = 93 så enkelt?
Filipjohanssonn skrev:Hur ser du att x = 93 så enkelt?
Tredje kongruensen ger att x slutar på 3, så jag testar 3, 13, 23. 23 uppfyller kongruens 2 och 3 men inte kongruens 1 så jag adderar 70=7×10 och får lösningen.
Smutsmunnen skrev:Filipjohanssonn skrev:Hur ser du att x = 93 så enkelt?
Tredje kongruensen ger att x slutar på 3, så jag testar 3, 13, 23. 23 uppfyller kongruens 2 och 3 men inte kongruens 1 så jag adderar 70=7×10 och får lösningen.
Tack så mycket!
Du kan skriva om x kongruent med 3 mod 10. Eftersom 10=2*5 är det enligt kinesiska restsatsen samma sak som att x kongruent med 1 (mod 2) samt x kongruent med 3 (mod 5).