Matematik

Hvad er den inverse

02. januar 2019 af Warrio - Niveau: Universitet/Videregående

Hej

jeg sidder med en opgave og kan ikke se hvad det er jeg gøre forkert :(

Hvad er den inverse til 23 modulo 44?

Jeg starter:

44 = 1*23 + 21

23 = 1*21+2

21= 10 * 2 +1

2 = 2*1 + 0

Derefter omskrives de:

1 = 21 - 10 * 2 (1)

2 = 23 - 1 * 21 (2)

21 = 44 - 1 * 23 (3)

Derefter indsætter jeg (2) i (1):

1 = 21 - 10 * (23 - 1 * 21) = 21 - 10 * 23 - 1 * 21 = 21 - 10 *23

Derefter indsættes (3):

44 - 1 *23 -10 * 23 = 44 - 11 *23

Det er vel ensbetydende med at den inverse er lig med -11 her, ikke ? og det er forkert iforhold til faciten :( hvad gøre jeg forkert?

På forhånd tak.

Brugbart svar (0)

Svar #1
02. januar 2019 af swpply (Slettet)

$\begin{align*} \text{step }0: && 44 &= 1\cdot23 + 21 &&\longrightarrow\ \ \ p_0 := 0\\ \text{step }1: && 23 &= 1\cdot21 + 2 &&\longrightarrow\ \ \ p_1 := 1\\ \text{step }2: && 21 &= 10\cdot2 + 1 &&\longrightarrow\ \ \ p_2 = 43 \equiv0-1\cdot1 \mod 44\\ \text{step }3: && 2 &= 2\cdot 1 + 0 &&\longrightarrow\ \ \ p_3 = 2 \equiv1-1\cdot43 \mod 44 \\ \text{step }4: &&\ &\ &&\longrightarrow\ \ \ p_4 = 23 \equiv43-2\cdot10 \mod 44 \end{align*}$

altså har du at 23 er sin egen inverse modulo 44.

Svar #2
02. januar 2019 af Warrio

Jo, men det er bare, om man kunne se hvad fejlen var i min fremgangsmåde. For det skal nemlig opstilles på denne måde, når det skal vises.

Brugbart svar (0)

Svar #3
02. januar 2019 af swpply (Slettet)

At finde det inverse element til 23 (mod 44) svare til at løse følgende kongruense

(1) $23\cdot x\equiv1\mod44$ ,

hvilket i sig selv svar til at finde hele tal x og y således at

(2) $23\cdot x + 44\cdot y = \gcd(23,44) = 1$ .

Eksistensen af løsninger (x og y) er givet ved at gcd(23,44) = 1 og dermed er en divisor i 1.

Bestem x ved Euklids algoritme
Euklids algoritme giver os at

$\begin{align*} \text{step }0: &&44 &= 1\cdot23 + 21 &&\Leftrightarrow\quad 21 = 44-1\cdot23\\ \text{step }1: &&23 &= 1\cdot21 + 2 &&\Leftrightarrow\quad 2 = 23 - 1\cdot 21\\ \text{step }2: &&21 &= 10\cdot2 + 1 &&\Leftrightarrow\quad 1 = 21-10\cdot2\\ \text{step }3: &&2 &= 2\cdot1 + 0 \end{align*}$

Dermed har vi at

$\begin{align*} 1 &= 21-10\cdot2 \\ &= 21 - 10\cdot(23-1\cdot21) \\ &= -10\cdot23 + 11\cdot21 \\ &= -10\cdot23+11\cdot(44-1\cdot23) \\ &= 23\cdot(-21) + 44\cdot11 \end{align*}$

Ved sammenligning med (2) ovenfor, finder vi altså at (x, y) = (-21, 11) er en løsning. Bruger vi nu at

$-21\equiv 23\mod44$

har vi hermed vist at 23 er sin egen inverse (mod 44).

Brugbart svar (0)

Svar #4
02. januar 2019 af swpply (Slettet)

#0 [...] Derefter indsætter jeg (2) i (1):
1 = 21 - 10 * (23 - 1 * 21) = 21 - 10 * 23 - 1 * 21 = 21 - 10 *23

[...]

Du har altså lavet en fejl i ovenstående. Du bør istedet havde skrevet

$\begin{align*} 1 &= 21 - 10\cdot(23-1\cdot21) \\ &= 21 - 10\cdot23 + 10\cdot1\cdot21 \\ &= (1+10\cdot1)\cdot21 - 10\cdot 23 \\ &= 11\cdot21 - 10\cdot23 \end{align*}$

Skriv et svar til: Hvad er den inverse

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.