14 svar
232 visningar
K.Ivanovitj behöver inte mer hjälp
K.Ivanovitj 399 – Fd. Medlem
Postad: 12 jul 2017 23:59 Redigerad: 13 jul 2017 00:36

Kongruens

Hej

Jag skulle behöva lite hjälp med att lösa följande uppgifter:

a)13x4110 1x<41

b)8x42 38,  1x<42

 

Jag vet inte riktigt hur det är mening att man ska lösa uppgifterna.

I a uppgiften så är alltså 13x delat med 41 =10 eller hur ska man tänka?

Smaragdalena 80504 – Avstängd
Postad: 13 jul 2017 00:17

Skall det vara mellanslag efter 10 respektive 38, så att men undre gränsen för x = 1?

K.Ivanovitj 399 – Fd. Medlem
Postad: 13 jul 2017 00:37

ja, det blev för litet mellanslag där, jag redigerade nu

Stokastisk 3597 – Fd. Medlem
Postad: 13 jul 2017 08:25

Du ska hitta de multiplikativa inverserna till 13 mod 41 på a och multiplicera ekvationen med den. På b får du konstatera att du kan förkorta bort lite först. b kan skrivas om till

4x  19 (mod 21)

Sedan finner du den multiplikativa inversen till 4 mod 21 och multiplicerar ekvationen med den.

K.Ivanovitj 399 – Fd. Medlem
Postad: 13 jul 2017 10:37

okej,om jag har förstått det rätt så innebär de multiplikativa inverserna att jag ska hitta ett tal att multiplicera 13 med för att få 41 i uppgiften a, samt från 4 till 19 i uppgift b.

Stokastisk 3597 – Fd. Medlem
Postad: 13 jul 2017 12:35

Du ska hitta det stal a som gör att 13a  1 (mod 41). Detta innebär att 13a - 1 = 41b, för något heltal b, detta kan då skrivas om som 13a - 41b = 1. Jag antar att ni lärt er lösa denna typ av diofantiska ekvationer. Kör man euklides algoritm så får man

41 =3*13 + 2,13 =6*2 + 1

Nu kan man köra detta baklänges och få

1 =13 - 6*2 =13 - 6 *(41 - 3*13) =19*13 - 6*41

Så man ser att a = 19, b = 6 är lösningar. Eller framförallt att 19*13  1 (mod 41)

K.Ivanovitj 399 – Fd. Medlem
Postad: 13 jul 2017 16:49

okej jag tror jag är med på det mesta men var får vi ettan från i 13a1(mod41)

Stokastisk 3597 – Fd. Medlem
Postad: 13 jul 2017 17:05

Ja nu har du alltså den multiplikativa inversen till 13, vilket gör att man kan beräkna

19*13x  19*10 (mod 41) x  26 (mod 41)

Så nu vet vi att lösningarna är x = 41n + 26 och så x ska ligga i det angivna intervallet så är enda lösningen, x = 26.

K.Ivanovitj 399 – Fd. Medlem
Postad: 13 jul 2017 17:58

okej så vi sätter in a=19 i båda led i den ursprungliga uppgiften och får då 247x190(mod41)

Så långt är jag med, men jag är inte riktigt med på hur vi får att x26

Stokastisk 3597 – Fd. Medlem
Postad: 13 jul 2017 18:43

Du har att 19*13x  1*x  x (mod 41) samt att 19*10  26 (mod 41) så kan du alltså förenkla ekvationen till

x  26 (mod 41)

K.Ivanovitj 399 – Fd. Medlem
Postad: 13 jul 2017 23:04

Okej, då har vi a klart, om vi tar b uppgiften ska vi då börja med 8a1mod42  som ger 8a-42b1

Om man sedan sätter 42=5×8+28=4×2+0

Stokastisk 3597 – Fd. Medlem
Postad: 14 jul 2017 07:31

Lägg märke till att du har att 8a - 42b =2(4a - 21b), det är alltså alltid ett jämnt tal så du kan inte finna några heltalslösningarna till ekvationen 8a - 42b =1 då HL är udda. Utan du har att

8x  38 (mod 42)

betyder att 8x - 38 = 42y för något heltal y. Detta är ekvivalent med 4x - 19 =21y  4x  19 (mod 21) så försök lösa denna ekvation istället.

K.Ivanovitj 399 – Fd. Medlem
Postad: 14 jul 2017 09:29

okej ska vi då sätta

21=5×4+14=2×2+0

Stokastisk 3597 – Fd. Medlem
Postad: 14 jul 2017 10:17

Du har inte gjort Euclides algoritm där. Du har att

21 =5·4 + 1

Vilket alltså innebär att (-5)·4 - (-1)·21 =1, så du har att -5 är en invers. Därför får man att

(-5)·4x (-5)·19 (mod 21) x (-5)·(-2)  10 (mod 21)

Så lösningarna är att x =10 + 21n. Det finns två lösningar i det angivna intervallet, dessa är 10 och 31.

K.Ivanovitj 399 – Fd. Medlem
Postad: 14 jul 2017 16:07

okej då förstår jag nu, tack för hjälpen

Svara
Close