Enklare modulo-ekvationer

A.

Solve the simultaneous equations:

y = 5x - 1 (mod 7)
y = 3x + 2 (mod 7)

samt:

B.

Solve the equation:

5x = 12, in Z13

Hur löser man sådana här uppgifter? Mitt problem atm. är modulen, som jag har svårt för. Var gärna genomgående!

Tack!

Edit: trams.

EDIT: Ändrar till en enklare lösning.

De två likheterna ger 5x - 1 = y = 3x + 2 (mod 7), dvs 2x = 3 (mod 7).

Lösningarna till denna är x = 5 + 7n, där n är ett godtyckligt heltal.

Alltså får vi y = (5x - 1) + 7p = (5 (5 + 7n) - 1) + 7p = 24 + 35n + 7p = 24 + 7(n + 5p) = 24 + 7m,
där m är ett godtyckligt heltal.

Svar: x = 5 + 7n och y = 24 + 7m, där n och m är godtyckliga heltal.

Notera att 5*5 = 25 = 13+12, dvs du kan ta x = 5.

I en lösning jag hittat - till samma uppgift, finner jag detta:

"The invertible element to 2 in Z7 is 4 i.e. 2^(-1) = 4 in Z7"

Vad menas? Hur får de inversen för 2 till fyra?

Tacksam för ett snabbt svar!

Den multiplikativa inversen av 2 (mod 7) är 4. Det får man genom att bestämma SGD(2,7) med Euklides algoritm och gör aritmetikens fundamentalsats på den utvecklingen av SGD(2,7) man hade.

Tex

Euklides algoritm:

7 = 2*3+1

Vilket ger SGD(7,2) = 1

Aritmetikens fundamentalsats:

1 = 7-2*3

Men för att göra det mer applicerbart med modulär aritmetik så kan man lätt inse följande likhet.

1 = -7+4*2

Det är också godtagbartt att multiplicera med -1 om man skulle behöva det.

Nu till din uppgift:

y ≡ 5x - 1 (mod 7)
y ≡ 3x + 2 (mod 7)

Då vet vi att

5x - 1 = y = 3x + 2 (mod 7)
⇔
2x ≡ 3 (mod 7)

Den mutliplikativa inversen av 2 (mod 7) är 4. Alltså multiplicerar vi hela ledet med 4, detta kan man ofta inse ganska snabbt, men det blir svårare om du har tex 43683x eller liknande, då är en allmän lösningsmetod som jag visade ovan att föredra.

8x ≡ 12 (mod 7)
x ≡ 5 (mod 7)

Detta betyder då:
x är alltså ett tal som vid division med 7 skapar resten 5.

Lösa ekvationen betyder ju egentligen att koefficienten för x skall vara 1, alltså x skall stå ensamt i något utav leden. Så det skall vi göra.

5x ≡ 12 (mod 13)

Undersök SGD(5,13):

13 = 5*2+3
5 = 3*1+2
3 = 2*1+1

Aritmetikens fundamentalsats:

1 = 3-(5-3) = -5+2*3 = -5+2(13-5*2) = 2*13-5*5 = 1

2*13 = 26
-5*5 = 25

Differensen mellan dessa är 1, så det stämmer. Den multiplikativa inversen av 5 (mod 13) är alltså -5

Så nu applicerar vi detta:

5x ≡ 12 (mod 13)
-25x ≡ -60 (mod 13)
x ≡ 5 (mod 13)

Vilket då betyder att x är ett heltal som vid division med 13 alltid skapar resten 5.

Tex:

18/13 = 1+5/13

Resten fem.

Svar: x ≡ 5 (mod 13)

Det här steget förstår jag inte riktigt. Rejält hjärnsläpp idag... =(

Skulle du kunna förklara det här steget lite mer? =)

Vet du hur euklides algoritm fungerar?

Extremt svårt över internet. Svara först på min fråga.

Jodå, den kan jag!

Jag tror att mitt problem ligger i att jag har allmänt svårt att se sambanden mellan talen där du använder den fundamentala formeln. Har suttit ett tag nu och försökt applicera det jag kan kring det - men kommer ingenvart.

Man kan ju se det ganska enkelt i det här fallet:
Du skall hitta ett tal x sådant att 2x är 1 mer än en multipel av 7.
Med x = 4 får vi 2x = 8 = 1 + 7.


Den här kan vi lösa genom att utnyttja att inversen till 5^(-1) = 8 (mod 13), eftersom 5 * 8 = 40 = 3*13 + 1 = 1 (mod 13).

Lösningen till 5x = 12 ges av x = 5^(-1) * 12 = 8 * 12 = 96 = 5 (mod 13).

Vi kan även skriva 5x = 12 = -1 (mod 13), så x = 5^(-1) * (-1) = 8 * (-1) = -8 = 5 (mod 13).

Pröva med denna då.

SGD(17,11)

17 = 11*1+6
11 = 6*1+5
6 = 5*1+1

När du då skall hitta den multiplikativa inversen till dessa två tal så kan du utnyttja följande sats:

SGD(17,11)=1, så vi börjar med ett.

1 är lika med 6-5, eller hur? Det ser vi ju i början.

Enligt euklides algoritm så lyder det såhär:

a = bq+r

Då måste detta även gälla

r = a-bq

Som vi ser i exemplet då

6 = 5+1
1 = 6-5

Viktigt!. Alla steg skall hela hela hela hela tiden vara lika med ett, är de inte lika med ett så har du gjort fel någonstans. Det är ett bra "facit" att utgå ifrån. När du har kommit till sista steget skall du ha någointing i formen av a*17+b*11 = 1, där a och b är heltal.

Sedan ser vi steget över att 11-6 är ju lika med 5. Så vi byter ut 5 mot 11-6, så arbetar man sig uppåt så hela tiden. Det kräver rätt mycket träning, men det är en förutsättning om du skall tex lösa svåra diofantiska ekvationer eller svåra konrgruenta ekvationssystem.

Men som manne säger så var det ganska självklart i detta fallet, det är ju så låga heltal så man kan se det ganska snabbt.