\require{AMSmath}

Modulorekenen

Hoe bereken ik een getal x zodanig dat x=1mod7 en x=5mod11 en x=1mod13? Kunt u mij stap voor stap uitleggen wat de werkwijze is bij het aanpakken van zo een probleem a.u.b.

Mark R
Student universiteit - donderdag 13 mei 2004

Antwoord

*Schrijf eerst het probleem uit als volgt:
x=7l+1 (1)
x=13m+1 (2)
x=11n+5 (3)
waarbij we dus zoeken naar gehele oplossingen voor l,m en n.
(Vergelijkingen waarbij we naar gehele oplossingen zoeken zijn diophantische vergelijkingen.)

*Gelijkstellen van (1) en (2) levert de eenvoudige diophantische vgl 7l+1=13m+1 Û 7l=13m Û l=13t en m=7t met tÎ (omdat ggd(7,13)=1) (of x=91t+1).

*We hebben nu 1 vergelijking voor l. We zoeken een tweede gelijkaardige vgl voor l met een parameter in. Stel nu (3) (wat we nog niet gebruikten) gelijk aan (1):
7l+1=11n+5 Û 7l-11n=4.

ggd(4,7,11)=1. We lossen dus eerst 7x+11y=1 op. Daarna vermenigvuldigen we de oplossing(en) met 4. Dit is een lineaire diophantische vgl en lossen we op met het algoritme van Euclides. Hopelijk ken je die methode. (Pas het algoritme toe en reken nu omgekeerd terug: probeer zelf).
Als oplossing vind je 7.(-3)+11.2=1.
De algemene oplossing vind je door deze oplossing af te trekken van de algemene vgl met x en y: 7(x+3)+11(y-2)=0 Û 7(x+3)=-11(y-2)=t (invoer parameter) Û (x+3)/(-11)=(y-2)/7=t Û x=-11t-3 en y=7t+2, met gehele oplossingen als tÎ.

Voor de vgl 7l-11n=4 wordt dit dus: l=-44t-12 en n=-28t-8 of l=44t-12 en n=28t-8, tÎ.

*We hebben dus voor l:
l=13t
l=44s-12

en dus 13t=44s-12 Û 44s-13t=12.
Deze vgl kun je op dezelfde manier als de vorige oplossen.
We krijgen als resultaat s=156t-60 en t=528z-204, tÎ.

*Nu hadden we x=91t+1 (zie bovenaan) en dus (t invullen) x=48048z-18563.

Ik hoop dat de oplossing juist is. Misschien bestaat er een kortere en betere methode. Het is dus eigenlijk een hoop moduloreken- en prutswerk. Hopelijk ken je de manier om een lineaire diophantische vgl via het algoritme van Euclides op te lossen en geraak je er aan uit. Reageer anders gerust.

Joeri
donderdag 13 mei 2004

©2001-2024 WisFaq