Juij! Eindelijk eentje die ik weet en The Bug niet!
*apetrots enal*
Ok, het is wel niet zo makkelijk om uit te leggen, maar eens je het door hebt is het niet zo moeilijk meer.
Eerst ga ik trachten uit te leggen hoe je gewoon een mod berekent.
Neem even het voorbeeld 13 = 19 (mod 3).
Wat doe je nu, je deelt zowel linker (13) als rechterlid (19) door de mod (3) en neemt daar de rest van. voor beide getallen is de rest 1, en klopt de gelijkheid (normaal is het gelijkaansteken bij zoiets drie streepjes ipv twee, mar die staat niet op mijn klavier
).
Nog iets, als je met een negatief getal zit, moet je een aantal keer de mod bij uw negatief getal optellen, tot je aan een positief getal komt. vb: -8 (mod 5): -8+5=-3; -3+5=2 => -8 (mod 5) = 2.
Dit gezegd zijnde gaan we nu de inverse even van een mod uitleggen, die heb je namelijk ook nodig.
laten we even de inversen zoeken voor de mod 7. Wat is nu juist de bedoeling. Je schrijft alle getallen van 2 tot 6 naast elkaar op een blad papier. Dan probeer je voor elk van deze getallen een getal te zoeken dat je dan vermenigvuldigd met het getal waar je de inverse van zoekt. Als je dan voor het product de mod neemt (hier mod 7) moet die 1 geven. Het getal waarmee je vermenigvuldigd hebt is dan de inverse. Let wel, de inverse moet steeds binnen het interval [1,N] liggen, met N de mod (hier 7) en ieder getal in dit interval mag maar 1 keer gebruikt worden.
Even het voorbeeld uitwerken:
Code: Selecteer alles
2 3 4 5 6
4 5 2 3 6
----------------
8 15 8 15 36 (mod 7)
Dus de inverse van 2 is 4, de inverse van 3 is 5, de inverse van 4 is 2, enz. En dit allemaal voor mod 7.
En dan komen we nu aan je vergelijking.
a*x=b (mod N)
De eerste stap is b (mod N) en a (mod N) uitrekenen (zie eerste uitleg). De tweede stap is de a (of a' indien deze al vereenvoudigd geweest is)overbrengen naar het rechterlid. dan krijg je in het rechterlid a^-1. Dit is de inverse van a voor mod N dat je dan moet zoeken (zie tweede uitleg). En dan bekom je voor x een getal voor mod N.
Mss eens een vbtje uitwerken:
geg: 27*x+3=0 (mod 11)
gevr: x
opl: 1) 27 (mod 11) = 5
2) 5*x = -3 (mod 11)
3) -3 (mod 11) = 8
4) 5*x = 8 (mod 11)
5) x = 8*5^(-1) (mod 11)
6) de inverse van 5 (mod 11) = 9 (5*9=45; 45 (mod 11) = 1)
7) x = 8*9 (mod 11) = 72 (mod 11) = 6 (mod 11)
Ziezo, ik hoop dat het een beetje duidelijk is. Anders is mijn eerste zinnetje wel een beetje een afgang geweest
. Indien er nog vragen zijn, moet je ze maar stellen.
Greetz
Draco
Draco