Modulo og knapsack

Først: Hvis du på TI-89 vil indtaste x mod(n) skriver du:
mod(x,n)

Men så til dit spørgsmål, for det fatter jeg heller ikke. Du bevæger dig jo ud fra de hele tal, når du opløfter i minus første?

#1
Der står:

"...
3) Vælg et tal t, således at 0 < t < m, og (m,t) = 1; dvs. t (indeholdt af) Z_m
4) Bestem det inverse element k til t modulo m, altså k = t^(-1)(mod m)
..."

Hjælper det?

Der ligger også en opgave herinde (noget med kryptering) hvor samme formel er anvendt, men der vist heller ingen beregninger... står bare at han har brugt Derive.

Nååååå... Altså nu er jeg ikke så meget inde i sagerne. Men f.eks. til et tal a, der er det additive inverse element 1/a. For modulær aritmetik er jeg ret sikker på, at det betyder noget andet. Altså, at der ikke descideret menes t^(-1). Men jeg er ikke sikker. :)

Søgte lige lidt om det... Det du skal finde er et tal k, sådan at:
t*k = 1 (mod m). Hvis det var normalt aritmetik er det klart, at dette tal ville være t^-1. Men i modular aritmetik er jeg mindre sikker.

Kan sgu ikke lige finde ud af det. Så langt er jeg: Du har ligningen:
899*k = 1 (mod 3245)

Det er klart, at denne er løst, hvis 899*k=3246. Altså, hvis vi må gå ind i de reelle tal er en løsning k = 3246/899. Det vil forsat være en løsning, hvis. Det er også klart, at:
3246 * n - (n-1) = 1 (mod 3245), hvor n er et naturligt tal.
Omskrives til:
899*3246/899*n - n - 1. Så er k = 3246/899*n - n - 1
k skal være et naturligt tal, så n skal bestemmes...

Men det passer desværre bare ingen steder, så der er noget galt. Men det er da derhen ad måske? :D

k*t = 1(mod m)
hvor
m = 3245 og t = 899

Dette løses vha. Euklids algoritme (som samtidig undersøger om det kan løses). Der skal nemlig gælde, at m og t er indbyrdes primiske for at ligningen har en løsning:


Euklids algoritme til at finde største fælles divisor mellem to tal:

3245 - 3*899 = 548
899 - 1*548 = 351
548 - 1*351 = 197
351 - 1*197 = 154
197 - 1*154 = 43
154 - 3*43 = 25
43 - 1*25 = 18
25 - 1*18 = 7
18 - 2*7 = 4
7 - 1*4 = 3
4 - 1*3 = 1

Som nu optrevles trin for trin til:
3245 = (1,0) (skal læses som 1*3245 og -3*899)
899 = (0,1)
548 = (1,-3)
351 = (0,1) - 1*(1,-3) = (-1,4)
197 = (1,-3) - 1*(-1,4) = (2,-7) (prøv selv, at 2*3245 - 7*899 = 197)
154 = (-1,4) - 1*(2,-7) = (-3,11)
43 = (2,-7) - 1*(-3,11) = (5,-18)
25 = (-3,11) - 3*(5,-18) = (-18,65)
18 = (5,-18) - 1*(-18,65) = (23,-83)
7 = (-18,65) - 1*(23,-83) = (-41,148)
4 = (23,-83) - 2*(-41,148) = (105,-379)
3 = (-41,148) - 1*(105,-379) = (-146,527)
1 = (105,-379) - 1*(-146,527) = (251,-906)

Derfor opnås fra sidste linje ligningen:

1 = 251*3245 - 906*899

<=>

-906*899 = -251*3245 + 1

Hvor man nu kan bruge ligningen:

3245*899 = 899*3245

til at justere den ovenstående, så man opnår positive løsninger:

(3245-906)*899 = (899-251)*3245 + 1

Altså med k = 3245-906 = 2339 kan man se, at:

k*t = 1 (mod m)

Hov...

(1,0) læses som 1*3245 + 0*899

(0,1) læses som 0*3245 + 1*899

og f.eks. læses

(1,-3) som 1*3245 - 3*899 som giver 548, hvilket det netop skal

beklager fejlen, den er med til at forvirre!

#6

Jeg forstår ikke, hvordan du kommer frem til dette:

548 = (1,-3)
351 = (0,1) - 1*(1,-3)
197 = (1,-3) - 1*(-1,4
154 = (-1,4) - 1*(2,-7)
43 = (2,-7) - 1*(-3,11)
25 = (-3,11) - 3*(5,-18)
18 = (5,-18) - 1*(-18,65)
7 = (-18,65) - 1*(23,-83)
4 = (23,-83) - 2*(-41,148)
3 = (-41,148) - 1*(105,-379)
1 = (105,-379) - 1*(-146,527)

Og lige et tillægsspørgsmål: Hvis jeg nu har valgt m til at være 3457, hvad må t så være? (jf. #2)

Og tusind tak for hjælpen allerede! Nu kan jeg pludselig se, hvordan det hænger sammen med det bevis for største fælles divisor for to givne hele tal jeg skal lave.

Nevermind, jeg har fundet ud af det hele.