WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Congruentie met deling

Hallo, ik ben op zoek naar het antwoord op de volgende 2 vergelijkingen.

(9802190a-1)/(5107-a)º62 (mod 1919) en
(6482011a+2)/(5107-a)º41 (mod 1269)

Ik ben op de hoogte van de standaard (mod m) methode, waarbij: axºb (mod m), maar met de deling door (5107-a) kan ik helemaal niets. Ik kan hier ook geen duidelijke informatie over vinden.

Aan de hand van een zelfgeschreven programaatje, die simpelweg alle getallen (vanaf 1) probeert, kom ik o.a. uit op 866.

Aan de hand van dit programma zie ik echter iets veel interessanters. De antwoorden op deze functies bestaan uit groepen die oplopende waarden bevatten. De groepen worden echter wel steeds kleiner (en later weer groter). Zo kun je proberen om waarden over te slaan bij het berekenen van de antwoorden.

Is er een mogelijkheid om zonder factoriseren van een bepaald getal (want ook dan moet je weer alle getallen proberen), en zonder alle getallen te proberen (while/for-lus van 1-5106) tot een oplossing te komen met een bepaalde formule?

Vr Gr,

c.p.

c.p.
Iets anders - vrijdag 22 oktober 2004

Antwoord

Het vraagstuk heeft niet zóveel vanzien met modulorekenen. Toch wil ik eerst een aantal dingen rechtzetten en aantonen dat modulorekenen niet zo eenvoudig is. Als de onderliggende grond ervan niet gekend is, dan ontstaan er snel problemen. Om uit te leggen hoe het feitelijk zit, moet je eigenlijk een hele cursus algebra geven. Ik wil het wel even situeren.

Bij het rekenen met de 4 hoofdbewerkingen zijn wij gewoon om te rekenen in $\mathbf{Q}$. Waarom het rekenen in $\mathbf{Q}$ zo goed werkt komt omdat $\mathbf{Q}$ en de definities die we voor + en × geven aan heel wat voorwaarden voldoen. We noemen ($\mathbf{Q}$,+,×) een veld omdat het aan die voorwaarden voldoet. Andere velden zijn ($\mathbf{R}$,+,×), ($\mathbf{C}$,+,×) en ($\mathbf{Z}$_p,+,×) (=($\mathbf{Z}$/p$\mathbf{Z}$,+,×)), met dat laatste bedoel ik modulo p, met p een priemgetal. Voor dat laatste veld wordt rekenen wel al moeilijker, want het is een eindig veld (over de verzameling {0,1,...,p-1} (de restklassen van 0,1,...,p-1.
($\mathbf{Z}$_n,+,×) is echter geen veld, maar een zwakkere structuur (een ring). Daarom moeten we bij rekenen heel goed opletten wat we doen. Onthoud dat we ons best aan strikte regels houden (tenzij je er al een beetje mee weg bent).

De vraag luidt ook wat het 'delen' hier betekent. Algemeen betekent 'delen door': 'vermenigvuldigen met het invers voor de maal'. Het invers van x voor de maal is het element x^-1 zodat x×x^-1=1, met 1 het neutraal element voor de maal.
Het neutraal element voor de maal bij rekenen modulo n is 1, ik bedoel de restklasse van het getal 1, modulo n.
vb: 5^-1 mod 9=2, want 5×2º1 mod 9.
Een techniek om het invers (bij grote n) te berekenen zonder te moeten overlopen wordt op deze site al gegeven.

Het programmaatje dat je schreef rekent (denk ik) gewoon in het veld $\mathbf{Q}$ i.p.v. $\mathbf{Z}$_n. Het berekent (9802190a-1)/(5107-a) en kijkt of dat 62 (mod 1919) is.
In feite is dat verkeerd, maar indien je 62 uitkwam zal dit wel juist zijn (door een aantal regels van modulorekenen). Je zou echter als je een niet-geheel getal x/y uitkwam dit nog moeten 'omvormen' via x×y^-1 mod 1919 (en kijken of dit 62 geeft).
vb:
7/5 mod 9=7×5^-1 mod 9=7×2 mod 9=5.
25/5 mod 9=25×5^-1 mod 9=25×2 mod 9=5.
(dit moest hetzelfde zijn, want modulo 9 zijn 7 en 25 'vertegenwoordigers' van hetzelfde element 7 (de restklasse van 7 = de restklasse van 25); 7º25 mod 9)
echter gewoon uitgerekend zoals jouw programma:
25/5=5 waarbij je dus ook dezelfde uitkomst vindt. Daarentegen kan jouw programma met iets als 7/5 niet overweg.
Bovendien dient je programma a niet alleen van 1 tot 5106 te overlopen. Het moet alle gehele getallen van -$\infty$ tot +$\infty$ overlopen, wat natuurlijk onmogelijk is; (modulo gaat over $\mathbf{Z}$ en niet enkel over $\mathbf{N}$, bvb -2º7 mod 9).

Om nu op het probleem zelf terug te komen. Een invers berekenen zal hier (toevallig (geënsceneerd)) niet nodig blijken. Je zoekt oplossingen a in $\mathbf{Z}$, dus

(1) ' a $\in$ $\mathbf{Z}$: (9802190a-1)/(5107-a)º62 mod 1919
$\Leftrightarrow$(1857a-1)×(1269-a)^-1º62 mod 1919 (we mogen de getallen eerst moduleren, ze vertegenwoordigen dezelfde restklasse en zijn dus modulorekenen gelijk)
$\Leftrightarrow$1919|((1857a-1)×(1269)^-1-62)(1)('|' betekent 'is deler van') (Dit is één van de vrij triviale regels i.v.m. modulorekenen: xºy mod n $\Leftrightarrow$ n|(x-y) ((x, y $\in$ $\mathbf{Z}$)). Hierbij moet je goed bedenken wat je opschrijft. Ik schrijf '^-1' i.p.v. gewoon te delen omdat 'is deler van slechts geldt tussen gehele getallen; dus interpretatie: Je moet in (1) de uitdrukking die rechts van '|' staat voor een welbepaalde a modulo 1919 eerst uitrekenen (zoals erboven staat), zodat de x en y (ingevuld in (1)) inderdaad gehele getallen zijn)
$\Leftrightarrow$1919|(((1857a-1)-62(1269-a))×(1269-a)^-1)
$\Leftrightarrow$1919|((1919a-78679)×(1269-a)^-1)
$\Leftrightarrow$1919|(1919×(a-41)×(1269-a)^-1) (dat je 1919 kunt afzonderen is toevallig en door degene die de opgave maakte geënsceneerd)
$\Leftrightarrow$ggd(1919,1269-a)|(a-41) (denk na!..., hier mag je voor ^-1 aan delen denken omdat voor zover die factoren van belang zijn dat dan toch geheel blijft (jouw programma klopte ook terwijl het geen rekening hield met modulorekenen bij de deling)

Noem nu ggd(...)=d, dan geldt voor d:
d|(1269-a) $\to$ a=1269-md, m $\in$ $\mathbf{Z}$ en
d|(a-41) $\to$ a=41+nd, n $\in$ $\mathbf{Z}$.
Uit beide volgt:
1269-md=41+nd
(n+m)d=1228
n+m=1228/d
heeft gehele oplossingen n en m $\Leftrightarrow$ d|1228.
Voor d(=ggd(...)) zijn uit de ontbinding van 1919 de mogelijkheden 1, 19, 101, 1919. We vinden dus enkel oplossingen n en m als d=1.
Dus mogelijkheden voor a: Alle a $\in$ $\mathbf{Z}$: ggd(1919,1269-a)=1.

(2) Analoog (doe het zelf eens)
oplossingen: alle a $\in$ $\mathbf{Z}$ met ggd(1269,31-a)=1 OF ggd(1269,31-a)=3.

Er zijn dus veel meer oplossingen dan je programma vond.

Joeri

Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 26 oktober 2004

Re: Congruentie met deling