Finn alla x så att 16x % 26 (mod 42)

Uppgiften är "Finn alla x så att $16 x \equiv 26 (m o d 42)$ ", och jag hittar GCD, LCM samt linjärkombinationen av dessa. Men jag förstår tyvärr ej hur de kommer fram till att $x = 20 + 21 n$ , $n \in ℤ$ . svaren är tydligen x = 21 och x = 41.

Jag får fram att GCD(42,16) = 2, och
LCM(42,16) = (21*16 eller 42*8) = 404.

$16 x - 42 y = 26$

linjärkombinationen är:
$26 = (13 * 8) * 16 - (13 * 3) * 42 + k (21 * 16 - 8 * 42)$
$26 = 16 * (13 * 8 + 21 k) - 42 (13 * 3 - 8 k)$

Skulle någon vilja vara snäll, och förklara steg för steg på väldigt enkel nivå skulle detta uppskattas. mvh emhamm

$16 x - 42 y = 26$

GCD är mycket riktigt 2. Euklides baklänges ger:

$2 = 6 - 4 \cdot 1 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2 (16 - 10) - 10 = 2 \cdot 16 - 3 \cdot 10 =$

$= 2 \cdot 16 - 3 (42 - 16 \cdot 2) = 8 \cdot 16 - 3 \cdot 42$

Alltså att $16 (8 \cdot 13) - 42 (3 \cdot 13) = 26$ , mycket riktigt.

Därefter adderar och subtraherar vi MGM (k är något heltal):

$16 (8 \cdot 13) - 42 (3 \cdot 13) + 8 \cdot 42 k - 16 \cdot 21 k = 26$

Förenkling ger:

$16 (8 \cdot 13 - 21 k) - 42 (3 \cdot 13 + 8 k) = 26$

Lösningarna till ekvationen är alltså på formen:

$\{\begin{cases} x = 8 \cdot 13 - 21 k = 104 - 21 k \\ y = 3 \cdot 13 + 8 k = 39 + 8 k \end{cases}$

Lösningen för x måste ligga inom intervallet (som ges av mod 42, och alltså är 0 till 41). Vi ska då försöka hitta några k som gör att x hamnar inom intervallet 0 ≤ x ≤ 41. Då provar vi oss fram: om k = 4 blir k-termen lika med 84, det skulle vi nog kunna använda. $x_{1} = 104 - 4 \cdot 21 = 104 - 84 = 20$ (tror du råkat skriva fel när du skrev x = 21).

Dessutom gäller det att om det finns en lösning till en moduloekvation, finns det alltid lika många som GCD, med andra ord ska det finnas en till. Vad händer om vi adderar en multipel av 21 till $x_{1}$ ? Jo, då får vi $x_{2}=41$ . Inga fler lösningar finns i intervallet, och vi är klara.

Smutstvätt skrev:
$16 x - 42 y = 26$
GCD är mycket riktigt 2. Euklides baklänges ger:
$2 = 6 - 4 \cdot 1 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2 (16 - 10) - 10 = 2 \cdot 16 - 3 \cdot 10 =$
$= 2 \cdot 16 - 3 (42 - 16 \cdot 2) = 8 \cdot 16 - 3 \cdot 42$
Alltså att $16 (8 \cdot 13) - 42 (3 \cdot 13) = 26$ , mycket riktigt.
Därefter adderar och subtraherar vi MGM (k är något heltal):
$16 (8 \cdot 13) - 42 (3 \cdot 13) + 8 \cdot 42 k - 16 \cdot 21 k = 26$
Förenkling ger:
$16 (8 \cdot 13 - 21 k) - 42 (3 \cdot 13 + 8 k) = 26$
Lösningarna till ekvationen är alltså på formen:
$\{\begin{cases} x = 8 \cdot 13 - 21 k = 104 - 21 k \\ y = 3 \cdot 13 + 8 k = 39 + 8 k \end{cases}$
Lösningen för x måste ligga inom intervallet (som ges av mod 42, och alltså är 0 till 41). Vi ska då försöka hitta några k som gör att x hamnar inom intervallet 0 ≤ x ≤ 41. Då provar vi oss fram: om k = 4 blir k-termen lika med 84, det skulle vi nog kunna använda. $x_{1} = 104 - 4 \cdot 21 = 104 - 84 = 20$ (tror du råkat skriva fel när du skrev x = 21).

Dessutom gäller det att om det finns en lösning till en moduloekvation, finns det alltid lika många som GCD, med andra ord ska det finnas en till. Vad händer om vi adderar en multipel av 21 till $x_{1}$ ? Jo, då får vi $x_{2}=41$ . Inga fler lösningar finns i intervallet, och vi är klara.

Supertack! Nu tror jag faktiskt att jag förstår ordentligt denna gång. Tack för att du tar dig tid och svarar, det uppskattas enormt! :)

Varsågod! Kul att det kunde hjälpa lite!

Svara

Visa senaste svar