Modulaire arithmetiek

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Gebruikersavatar
Berichten: 524

Modulaire arithmetiek

Hallo,

Het is mij nog niet helemaal duidelijk hoe je moet vermenigvuldigen met equivalentieklassen en hoe je dit bewijst.

Het bewijs voor [ a ] + [ b ] := [a + b] heb ik wel, maar begrijp ik ook nog niet helemaal:

-----

Definieer bewerking + en * op Z (gehele getallen)/n (Z modulo n)

Welgedefinieerdheid: Voor "+" moeten wij laten zien [ a ] = [ a' ], [ b ] = [ b' ], dan ook [a + b] = [a' + b']

(waarom? Waarom moet dat?)

Dus: a ~ a' => Er is een k, k*n = a - a'

b ~ b' => Er is een l, l*n = b - b'

Dan is (a + b) - (a' + b') = kn + ln = (k + l)*n => [a + b] = [a' + b']

(Waarom?)

Welgedefinieerdheid: Voor "*" moeten wij laten zien [ a ] = [ a' ], [ b ] = [ b' ], dan ook [a * b] = [a' * b']

(Denk ik, aangezien ik hier geen bewijs voor heb, maar hoe werk ik dan verder?)

-----

Nu over het rekenen; ik begrijp de volgende opgave:

[5] + x = [1] is een element van Z/9

Hieruit volgt volgens mij berekening dat x = [1 - 5] (door het bewijs van hierboven).

x = [-4]

oftewel: x = { ... , -13, -4, 5, 14, 23, ... }

Maar vervolgens bij het vermenigvuldigen:

[2]x = [7] is een element van Z/11

Het lijkt mij vrij onwaarschijnlijk dat x = [7/2], aangezien het gehele getallen (Z) betreft. Aangezien de ~-waarde hier 11 is, moet ik dan de [7] daarmee vermenigvuldigen of iets dergelijks?

Ik heb namelijk wel uit theorie dat bij Z/12 geldt:

[5]x = [1]

x = [5]

want [1] = [25] en [5] * [5] = [25]

Ik snap de bewerking hier naartoe dus niet.

Ik zou het erg fijn vinden als iemand mij hier mee zou kunnen helpen.

Berichten: 400

Re: Modulaire arithmetiek

Ik ga even snel antwoorden (want ga zo meteen slapen).

Voor uitleg over het goed gedefinieerd zijn heb ik een lange post in dit topic gemaakt die voor jou ook relevant is.

http://www.wetenschapsforum.nl/index.php?showtopic=131103

Verder: heb je een snelle methode gezien voor de inverse bij modulorekenen?

(Ik laat in wat volgt overal de haakjes [] weg); Inderdaad werk je enkel met gehele getallen. Modulo 11 is het antwoord in plaats van 7/2 eigenlijk
\(7\cdot 2^{-1}\)
modulo 11, delen betekent vermenigvuldigen met het invers. Met een methode om de inverse te berekenen vind je het resultaat. De inverse bestaat enkel als de grootste gemene deler van je modulus (11) en je getal waarvan je de inverse wilt (2) gelijk is aan 1 (dus als de getallen relatief priem zijn). Als je modulus een priemgetal is, is dat altijd het geval als je getal verschillend is van 0. Als de grootste gemene deler niet gelijk is aan 1 dan ga je geen inverse vinden, en dus geen oplossing voor je vergelijking. Dit kan enkel soms voorkomen als je modulus geen priemgetal is.

Je kan voor de inverse gewoon alle mogelijkheden uitproberen, maar er zijn snellere methodes. Er zijn maar 11 mogelijke uitkomsten, want maar 11 equivalentieklassen modulo 11, probeer dus gewoon alle getallen van 0 tot en met 10 (11 is opnieuw 0). 0 is natuurlijk nooit een mogelijkheid. Hier is het inverse van 2 duidelijk gelijk aan 6, want 2*6=1 (modulo 11). En 7*6 is dan gelijk aan 42, dus gelijk aan 9 (of -2). Inderdaad is 2*9=18 en dat is 7 modulo 11 (of 2*(-2)=-4 en dat is net hetzelfde modulo 11). Je kon ook rechtstreeks alle 11 mogelijke antwoorden proberen en dan ging je ook 9 vinden als antwoord voor x. Echter zijn er snellere methodes om de inverse te bepalen dan alle mogelijkheden uitproberen. Deze zijn nuttig als je modulus erg groot is en alles uitproberen veel tijd zou vragen.

Gebruikersavatar
Berichten: 524

Re: Modulaire arithmetiek

Eerlijk gezegd snap ik bar weinig van je verhaal, waarom invers?

Het is me gisterenavond gelukt om het op te lossen, op de volgende manier:

-----

[2]x = [7] is een element van Z/11

[7] = [..., -4, 7, 18, ...}

En 18 is een vermenigvuldiging van 2, dus:

[2]x = [18] = [7]

x = [9]

Denk ik er nou te makkelijk over, of is het echt legitiem om het op deze manier te doen?

-----

Hoe zit het trouwens met het bewijs voor [ a ] * [ b ] = [ab]?

Berichten: 400

Re: Modulaire arithmetiek

Dat is goed zo. Het wordt echter moeilijker op die manier als je modulus groter wordt en er niet meer 2 staat. Maar ik weet natuurlijk niet wat je allemaal gezien heb (wat je niveau is).

Delen betekent per definitie vermenigvuldigen met de inverse. Als je werkt met reële getallen en daarmee rekent, dan is de inverse van 2 de breuk 1/2, maar als je werkt modulo 11 dan is de inverse van [2] een (equivelantieklasse van een) geheel getal, namelijk [6]. De bewerking * is bij de reële getallen helemaal verschillend als bij modulorekenen, aangezien een reëel getal (een element van de verzameling reële getallen) ook helemaal verschillend is van een element van de verzameling waarmee je rekent bij rekenen modulo 11 (die elementen zijn namelijk equivalentieklassen van gehele getallen).

Dus om je vergelijking op te lossen (nodig zo te werken in ook moeilijkere gevallen, als je dat zou moeten kunnen):
\([2]\cdot x=[7]\)
\([2]^{-1}\cdot [2]\cdot x=[2]^{-1}\cdot [7]\)
\(x=[2]^{-1}\cdot [7]\)
Vandaar dus de inverse.

Als je goed wil begrijpen waarom je moet nagaan of iets goed gedefinieerd is moet je toch alles nauwkeurig abstract opbouwen. Ik denk dat dat in het topic dat ik doorgegeven heb goed staat uitgelegd in die post. Was dat wel duidelijk?

Voor het bewijs dat de vermenigvuldiging goed gedefinieerd is: Je moet inderdaad aantonen wat je in je post geschreven hebt. Ga op dezelfde manier te werk als bij de optelling. a'=a+k*n en b'=b+l*n en toon dan aan dat [a'*b']=[a*b].

Gebruikersavatar
Berichten: 524

Re: Modulaire arithmetiek

Oké, bedankt. Mijn niveau is alleen nog niet zo hoog om het door middel van inverses uit te rekenen. Ik doe het op de manier zoals op het hoorcollege is uitgelegd, maar het was me toen nog niet helemaal duidelijk.

Ik heb je post wel gelezen, maar vind het nog erg moeilijk, veel termen begrijp ik nog niet.

Berichten: 400

Re: Modulaire arithmetiek

Ok, als je er niet aan uitgeraakt of een vraag hebt, laat maar weten.

Reageer