Opdracht computer algebra bij het behandelde op 21 januari 2003 i) Maak een programma dat ofwel zegt dat het systeem van vergelijkingen x=a(mod b) (x is congruent aan a mod b). x=c(mod d) (x is congruent aan c mod d). geen oplossing heeft, ofwel een oplossing geeft van de vorm e(mod f). ii) Doe hetzelfde maar nu voor een systeem van vergelijkingen x=a_0 (mod b_0 x=a_1 (mod b_1) x=a_2 (mod b_2) etc. (Hint: gebruik i)) De situatie onder i) kan geanalyseerd worden mbv. het euclidisch algoritme. Het is niet moeilijk in te zien dat een noodzakelijke en voldoende voorwaarde voor het hebben van een oplossing onder i) is dat a=c (modulo de grootste gemeenschappelijke deler van b en d). Bepaal dus onder i eerst of a=c (mod gcd(b,d)). Zo nee: geen oplossing. Zo ja: schrijf c=a+k*gcd(b,d). Vul dit in en deel uit naar gcd(b,d). We moeten dan oplossen: (x-a)/gcd(b,d)=0(mod b/gcd(b,d)) (x-a)/gcd(b,d)=k(mod d/gcd(b,d)) Dus in essentie y=0( mod b/gcd(b,d)) y=k( mod d/gcd(b,d)) We hebben nu een systeem van moduli gekregen die relatief priem zijn. Dit kan worden opgelost zoals uitgelegd in het college. Dus als we willen oplossen x=a(mod b) x=c(mod d) met b en d relatief priem (grootste gemene deler 1). Bepaal dan e_1 met e_1=1(mod b) en e_1=0(mod d) en e_2 met e_2=0(mod b) en e_2=1(mod d). Oplossing is x=a*e_1+c*e_2(mod bd). Nu is e_1 van de vorm f_1*d met f_1*d=1(mod b), f_1 is dus een inverse van d (mod b). Dus onder i) is het handig eerst een routine te schrijven die het systeem van vergelijkingen x=a(mod b) en x=c(mod d) oplost als b en d relatief priem zijn. (In dit geval is er altijd een unieke oplossing modulo b*d, ongeacht a en b. Dit is de chinese reststelling). Merk op dat b/gcd(b,d) en d/gcd(b,d) relatief priem zijn. Later toegevoegd: Eelco vond mijn uitleg over het oplossen van een vergelijking van de vorm x=a(mod b) x=c(mod d) niet helemaal duidelijk (in een eerde e-mail). Ik zal het nog een keer proberen. Als er een oplossing van het bovenstaande stelsel bestaat, dan hebben we dus a+geheel getal*b = c + geheel getal*d, het verschil a-c is dus van de vorm (1) geheel getal*b+geheel getal*d en zit dus in het ideaal voortgebracht door b en d, (b,d), maar (b,d)=(gcd(b,d)). Je mag ook direct opmerken dat een combinatie van de vorm (1) deelbaar is door gcd(b,d). Een NOODZAKELIJKE voorwaarde voor het bestaan van een oplossing van ons stelsel is dus dat (2) a=c(mod gcd(b,d)). Dus ons algoritme laten we eerst testen of aan deze voorwaarde voldaan is. Zo nee, dan: ER IS GEEN OPLOSSING. Is nu aan (2) voldaan, dan berekenen we het gehele getal k=(a-c)/gcd(b,d). We moeten dan oplossen x=a (mod b) x=a+k*gcd(b,d) (mod d) ofwel x-a=0 (mod b) x-a=k*gcd(b,d) (mod d) Uit deze vergelijking zien we dat x-a een veelvoud van gcd(b,d) moet zijn. Laten we dus delen door gcd(b,d): (x-a)/gcd(b,d) = 0 (mod b/gcd(b,d)) (x-a)/gcd(b,d) = k (mod d/gcd(b,d)) Omdat nu b/gcd(b,d) en d/gcd(b,d) relatief priem zijn (ga na), kunnen we nu het chinese reststellings algoritme voor relatief prieme moduli toepassen. We lossen dus op y=0 (mod b/gcd(b,d)) y=k (mod d/gcd(b,d)) daarna vinden we onze x uit (x-a)/gcd(b,d)=y. Deze constructieve methode laat nu zien dat de NOODZAKELIJKE voorwaarde a=c(mod gcd(b,d)), ook VOLDOENDE is, met andere woorden we hebben nu bewezen dat ons oorspronkelijke stelsel een oplossing heeft dan en slechs dan als a=c(mod gcd(b,d)). De oplossingen van het y stelsel zijn van de vorm y_0+veelvouden van b*d/(gcd(b,d))^2 (het product van de moduli). Dit levert voor het x-stelsel x_0+veelvouden van b*d/gcd(b,d). Merk op dat b*d/gcd(b,d)=lcm(b,d) (kleinste gemene veelvoud). Dit argument kan triviaal worden uitgebreid en leidt dan tot de volgende stelling: Stelling: Een systeem vergelijkingen x=a_i (mod b_i), 1<= i< =r heeft GEEN oplossing als er i en j te vinden zijn met a_i niet congruent aan a_j mod gcd(b_i,b_j) en anders heeft het een unieke oplossing modulo het kleinste gemene veelvoud van b_1 tot en met b_r. Merk op dat deze stelling inderdaad de ons bekende met relatieve prieme moduli generaliseert. Een andere methode om ons stelsel te beschouwen is b en d in priemmachten te ontbinden. Volgens de chinese reststelling krijgen we dan een stelsels congruencties mod priemmachten. Door dat te beschouwen kun je de bovenstaande stelling ook afleiden, dit is misschien inzichtelijker, maar algoritmisch veel minder geschikt (waarom ?)