WisFaq!

Congruentie met meerdere variabelen

Ik ben op zoek naar de methode/functie waarmee ik de volgende vergelijkingen oplos:

Ik heb de volgende vergelijkingen (met de vorm: (y+ba) mod x=0)

89+8a mod x=0
73-27a mod x=0

Als ik het verschil (2x) uitreken, krijg ik de volgende twee vergelijkingen.

16+35a mod x=0
57-62a mod x=0

Volgende de theorie moet ik net zolang het verschil tussen welke vergelijkingen dan ook (zolang ze maar tot de reeks behoren die voortkomen uit eerder berekende vergelijkingen) uitrekenen, totdat gcd(y,b)1. Deze functie levert dan nmlk. minimaal 1 oplossing voor het probleem.

Het is ook mogelijk om vergelijkingen bij elkaar op te tellen, of waarden te vermenigvuldigen, maar ook dit levert geen oplossing (op een voorspelbare termijn).

De vergelijking met het “-“ teken is te herschrijven als: 57 mod x=62a mod x

Een andere mogelijkheid om het probleem op te lossen is door alle a’s te proberen vanaf 1. Hierbij kom ik tot de oplossing a=7. 89+8a mod x=0. Hiermee kan x worden berekend: nmlk. x=29.

Echter, omdat de oplossing van dit probleem eigenlijk ligt in de volgende vergelijking:

y+ba=z+ca, vraag ik me af of er geen eenvoudige methode, of formule is om het probleem op te lossen. Er zijn namelijk alleen lineaire functies gedefinieerd. Daarnaast zijn er een (vrijwel) oneindig aantal vergelijkingen te genereren.

Je kunt je namelijk dezelfde functie met andere grotere getallen voorstellen, waarbij het al snel onmogelijk wordt om a (en daarna x) uit te rekenen, als je alle waarden simpelweg moet proberen.

Vr Gr,

c.p.
28-6-2004

Antwoord

Hallo C.P.,

Dit probleem zou ik als volgt aanpakken:

89 + 8a = 0 (mod x)
73 - 27a = 0 (mod x)

Neem nu 27 keer de eerste plus 8 keer de tweede, dan krijg je 2987 = 0 (mod x). De priem-ontwikkeling daarvan is 2987 = 29·103, dus kennelijk is x = 1, 29, 103 of 2987. Vervolgens gaan we dus gevallen onderscheiden:

- x=1 is triviaal, dan is alles een oplossing.
- x=29: omdat 11·8=88=1 (mod 29) kunnen we de eerste vergelijking vermenigvuldigen met 11 om te vinden dat a=7 (mod 29). Op dezelfde manier volgt uit de tweede vergelijking (omdat -27=2 (mod 29) en 15·2=1 (mod 29)) door vermenigvuldigen met 15 opnieuw dat a=7 (mod 29).
- x=103: omdat 13·8=104=1 (mod 103) volgt uit vermenigvuldiging van de eerste vergelijking met 13 dat a=79 (mod 103). Op dezelfde manier volgt uit de tweede vergelijking (omdat 42·27=1134=1 (mod 103)) opnieuw dat a=79 (mod 103).
- x=2987: in dat geval impliceert gelijkheid (mod x) ook gelijkheid (mod 29) én gelijkheid (mod 103). In het bijzonder volgt dus dat
a = 7 (mod 29)
a = 79 (mod 103)
De chinese reststelling geeft ons dan de oplossing. Omdat 32·29=0 (mod 29) en 32·29=1 (mod 103) is 7+32·29·(79-7)=66823 de oplossing (mod 29) en (mod 103), dus a = 66823 = 1109 (mod 2987).

Ik hoop hiermee je vraag naar tevredenheid beantwoord te hebben. Met vriendelijke groet,

Guido Terra

P.S. Ik heb nu nog bij x=29 en x=103 gecontroleerd dat de oplossing voor beide vergelijkingen hetzelfde geeft (mod x). Het is wel opvallend dat het in alle gevallen goed uitkomt. Ik weet nog niet of dit ook algemeen zo is. Misschien dat je daar zelf achter kunt komen.

gt
29-6-2004