ekvationssystem i moduloräkning

Hej!

Finn samtliga lösningar i $ℤ_{56}$ till systemet

$\begin{array}{r} 4 x + 7 y = 5 \\ 3 x + 2 y = 8 \end{array}\}$

Första gången jag löste uppgiften använde jag att ovanstående sytem är samma sak som

$\begin{array}{r} 4 x + 7 y = - 51 \\ 3 x + 2 y = - 48 \end{array}\}$ i $ℤ$ . Jag räknade ut y=3 (mod56) och x=38 (mod 56) vilket också stämmer med facit.

Nu tänkte jag att man lika gärna kan skriva systemet som

$\begin{array}{r} 4 x + 7 y = 61 \\ 3 x + 2 y = 64 \end{array}\}$ och naturligtvis få samma svar. Jag får även här att y=3 (mod56) men får x=10:

$\begin{array}{r} 3 (4 x + 7 y = 61) \\ 4 (3 x + 2 y = 64) \end{array}\} = \begin{array}{r} 12 x + 21 y = 183 \\ 12 x + 8 y = 256 \end{array}\}$ . Om vi subtraherar rad två från rad ett får vi

$13 y = - 73 \equiv 39 (m o d 56)$ och vi har som önskat att $y = 3 .$

Om vi nu sätter in $y = 3$ i ekvationen $12 x + 21 y = 183$ får vi $12 x + 21 \times 3 = 183 \Leftrightarrow x = 10$ .

Varför får jag inte att x=38 som förut?

Man kan inte dividera hur som helst modulo någonting.

För att få dividera ax = ab mod c och få x = b måste b och c vara relativt prima, dvs sgd(b,c) = 1

12x = 120 mod 56 betyder inte att x = 10.

Däremot funkar division med 13 för 13y = 3x13(mod 56) eftersom 3 och 56 inte har någon gemensam delare.

Därför måste man tänka till lite när man har ekvationssystem modulo någonting.

Ja, det låter ju rimligt. Första gången gjorde jag så här (mod56):

$\begin{array}{r} 4 x + 7 y = 5 \\ 3 x + 2 y = 8 \end{array}\} ~ \begin{array}{r} 4 x + 7 y = - 51 \\ 3 x + 2 y = - 48 \end{array}\} \Leftrightarrow \begin{array}{r} 3 (4 x + 7 y) = 3 (- 51) \\ 4 (3 x + 2 y) = 4 (- 48) \end{array}\} = \begin{array}{r} 12 x + 21 y = - 153 \\ 12 x + 8 y = - 192 \end{array}\}$ .

Om man nu subtraherar den andra ekvationen från den första får vi att $13 y = 39 \Leftrightarrow y = 3$ . (Vilket alltså var tillåtet eftersom $s g d (3, 56) = 1 .$ )

Vi substituerar nu $y$ med $3$ i ekvationen $12 x + 21 y = - 153$ och får $12 x + 21 \times 3 = - 153 \Leftrightarrow 12 x = - 216$ . Vi delar bägge led med $12$ och får att $x = - 17 \equiv 38 (m o d 56)$ .

Om jag förstått det rätt så får vi alltså dela med 12 eftersom resultatet, -17, är relativt prima med 56 (och alla andra tal med för den delen).

Jag hade uppenbarligen tur första gången jag löste uppgiften. I min okunnighet tänkte jag, när jag gjorde om den, att det gick lika bra att lägga till 56 till HL i bägge rader i ekvationssystemet som att dra ifrån 56 från HL.

Frågan jag ställer mig nu är: Hur ska man resonera för att välja rätt från början?

Jag tror inte det finns några generella metoder.

Om man har ett ekvationssystem modulo ett primtal känns det som att det borde vara lösbart men modulo ett sammansatt tal behöver det inte vara det.

Exempel:

$x + y = 1 (m o d 5) x - y = 2 (m o d 5) \Rightarrow 2 x = 3 (m o d 5) \Rightarrow x = 4 (m o d 5) \Rightarrow y = 2 (m o d 5)$

$x + y = 1 (m o d 6) x - y = 2 (m o d 6) \Rightarrow 2 x = 3 (m o d 6) \Rightarrow l ö s n i n g s a k n a s$

Tack! Jag har märkt att när jag tycker det är märkligt att en metod saknas för något som tillhör matematik på grundnivå, så finns det en anledning till det. Och den anledningen är att jag ställt fel fråga. Det SKA helt enkelt inte finnas någon sådan metod.

Jag fick svar från min lärare nu efter helgen och hen menar att det inte spelar någon roll vilken multipel av 56 man räknar med. (Skönt att få det bekräftat!) Lösningsmetoden bestod i att notera att 3 (från $3 x$ i den andra ekvationen) är relativt prima med 56. Vidare att $3^{- 1} = 19$ i $ℤ_{56}$ . Om man då multiplicerar bägge led i den andra ekvationen med 19 och stuvar om lite får man x uttryckt i y. Detta uttryck sätts sedan in i den första ekvationen och man kan då lösa ut y.

Detta värde för y sätter vi sedan in i uttrycket för x och får då direkt fram värdet för x utan att behöva utföra någon division. Denna division (eller multiplikation med invers) har vi ju redan utfört.

Svara

Visa senaste svar