Modulair rekenen met meerdere variabelen

Mijn vraag is, of de volgende functies oplosbaar zijn (en ook welke waarden er mogelijk ontbreken om de functie wel te kunnen oplossen)?

(1919ab) mod 5107=1
1919(a+1)(b-1) mod 5108=5047
1919(a+2)(b-2) mod 5109=1148
1919(a+3)(b-3) mod 5110=3631

Ik ben bekend met de “Chinese Remainder Theory”, maar weet niet, of deze ook toepasbaar is op meerdere variabelen.

Het kleinste antwoord heb ik trouwens al, nmlk: a=866 en b=1044. Het gaat echter om de berekening.

Het enige dat ik kan proberen is het berekenen van 1919x mod 5107=1. Dit is 1919*(165+5107k) mod 5107. Echter, hiermee heb ik niets met de overige functies gedaan.

Graag zou ik willen weten of er een snellere berekenmethode is dan de methode waarmee 1919(165+5107k) mod 5107 wordt berekend, waarbij voor elke waarde van k, a en b moeten worden gecheckt.

Vr Gr

c.p.
Iets anders - vrijdag 3 december 2004

Antwoord

Voor dit vraagstuk vond ik acht gehele oplossingen. Het gaat als volgt:

a) Stel: we hebben een a en b Î zodat 1919ab mod 5107=1
® $ k Î : ab=165+5107k (via berekenen inverse ...)

We bekijken nu wat opleggen van de andere voorwaarden levert; opnieuw op dezelfde manier:
$ l Î : (a+1)(b-1)=165+5108l
$ m Î : (a+2)(b-2)=163+5109m
$ n Î : (a+3)(b-3)=159+5110n

Uitwerken en de eerste voorwaarde die verondersteld vervuld was ervan aftrekken levert voor deze drie voorwaarden:

$ l Î : b-a=1+l-5107(k-l)
$ m Î : b-a=1+m-5107(k-m)/2
$ n Î : b-a=1+n-5107(k-n)/3

b) We willen dit vereenvoudigen. Deze voorwaarden zijn zeker vervuld als k=l=m=n. Deze oplossingen worden in (c) gezocht. Verder zijn er (uit het algoritme van Euclides om lineaire diophantische vergelijkingen op te lossen (het ggd-algoritme)) enkel eventueel nog oplossingen met k=5109*2555*s en l=5109*2555*t (s en t gehele getallen). Die oplossingen zijn echter niet zo gemakkelijk als via (c) te bepalen (de eliminatie faalt). Ik vermoed echter dat dit geen nieuwe oplossingen levert.

c) Niettemin vinden we voor k=l=m=n 8 oplossingen:
We hebben nog 2 vergelijkingen over die we kunnen combineren tot het zoeken naar gehele oplossingen van volgende vergelijking:
ab=165+5107(b-a-1) (k geëlimineerd, dit is OK omdat b-a-1 altijd geheel is als a en b geheel zijn, we zijn de voorwaarde 'k geheel' dus niet kwijt)
Û a(5107+b)=5107b-4942
stel b=b₀ is oplossing, b₀ Î
dan a=(5107b₀-4942)/(5107+b₀) (b₀¹-5107, b₀=-5107 is geen oplossing)
stel b₀'=5107+b₀ (dus b₀=b₀'-5107)
dan a=5107-(5107²+4942)/b₀'
opdat a geheel zou zijn, moet
b₀'|5107²+4942
of b₀'|4241*6151 (priemfactoren)

We vinden dan oplossingen voor a en b:

a=866, b=1044
a=-1044, b=-866
a=9348, b=-11258
a=11258, b=-9348
a=5106, b=26081284
a=-26081284, b=-5106
a=5108, b=-26091498
a=26091498, b=-5108

Joeri
zondag 9 januari 2005

©2001-2024 WisFaq