WEEK 2

Diophantische vergelijkingen en de Stelling van Brahmagupta

We kijken naar lineaire diophantische vergelijkingen: dat zijn lineaire vergelijkingen in meerdere variabelen, waarbij we ons beperken tot geheeltallige coëfficiënten en oplossingen. De Stelling van Brahmagupta vertelt je wanneer zo'n vergelijking een oplossing heeft; en wat die oplossingen dan zijn. De stelling moet je niet alleen kunnen toepassen, maar er wordt ook verwacht dat je het bewijs doorgrondt.

Kern:
	§6 van de reader
Extra ondersteuning:
	Stelling van Brahmagupta
	Agendeer dit thema voor de bijeenkomst

Algoritmiek

Doel is dat je algoritmes op een wiskundige manier kunt beschrijven om ze vervolgens te analyseren op correctheid, eindigheid en snelheid (complexiteit of looptijd). We werken hierbij iets losser dan je bij wiskunde gewend bent, omdat dit nou eenmaal geen cursus theoretische informatica is. Het doel is dat je de manier van analyseren onder de knie krijgt; niet dat je formele bewijzen met algoritmes kunt geven. Dat losse blijkt uit de taal ('pseudo-code') die we hanteren en uit de omgang met het fenomeen looptijd.

Kern:
	§5b van de reader
Extra ondersteuning:
	De $\cal O$-notatie
	Algoritmiek en complexiteit
	§1.1 in het boek van De Weger biedt een eenvoudige inleiding tot de algoritmiek; §1.6 gaat vervolgens in op de complexiteit van het euclidische algoritme
	Agendeer dit thema voor de bijeenkomst

Opgave 1

Vind alle (!) oplossingen van de diophantische vergelijking $1485x+1745y=15$.

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Verzin zelf diophantische vergelijkingen en controleer je antwoorden in Wolfram Alpha (voorbeeld-instructie: solve diophantine equation 121x+434y=1).
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 2

Gegeven zijn gehele getallen $a_1$, ..., $a_k$ en $c$. Wanneer heeft de diophantische vergelijking $$a_1x_1+\cdots+a_kx_k=c$$een oplossing? (Dus $x_1,\ldots,x_k\in\ZZ$.) Formuleer een criterium – een bewijs wordt niet gevraagd.

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 3

Gegeven zijn $a,m,n\in\NN$ met $a\ge2$ en $m>n>0$.

1. Stel $r$ is de rest bij deling van $m$ door $n$. Laat zien dat de rest bij deling van $a^m-1$ door $a^n-1$ gelijk is aan $a^r-1$.
2. Voer naast elkaar op papier het euclidisch algoritme uit voor $\ggd(m,n)$ en $\ggd(a^m-1,a^n-1)$, totdat je kunt uitleggen dat $\ggd(a^m-1,a^n-1)={}$$a^{\ggd(m,n)}-1$.

	Loop je vast? Probeer de heuristiekboom bij opgave 3a en bij opgave 3b!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 4

Een methode om te bepalen of een geheel getal $n>1$ een priemgetal is, is door te controleren of het deelbaar is door een getal kleiner dan $n$. In feite is het genoeg om te controleren of $n$ deelbaar is door een getal $i$ met $2\le i\le\sqrt n$.

1. Bewijs dit.
2. Formuleer het algoritme in pseudocode.
3. Beargumenteer dat het algoritme exponentiële complexiteit heeft.

	Loop je vast? Probeer de heuristiekboom bij opgave 4a en bij opgave 4c!
	Minder leerzaam: de uitwerking
	Nadat je onderdeel b hebt beantwoord, kun je het algoritme in werking zien
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 5

Bekijk het euclidische algoritme:

Hier staat $a\bmod b$ voor de rest bij de deling-met-rest van $a$ door $b$.

1. Beargumenteer dat dit algoritme eindig is, wat wil zeggen dat de lus 2–2.3 niet eindeloos wordt herhaald.

Zij $k$ het aantal keer dat de regels 2–2.3 volledig wordt uitgevoerd. Doel is een (scherpe) bovengrens te vinden voor $k$ als functie van $a$ en $b$. Hiervoor gebruiken we de volgende stelling:

als $a>b$ en $r=a\bmod b$, dan $r<\frac12 a$.

2. Bewijs dit.
3. Toon aan dat na twee herhaling van de lus 2–2.3 het getal $r$ meer dan gehalveerd is.
4. Bewijs: $k<2\cdot\log[2]{a}$.
5. Wat is dus de complexiteit van het algoritme?

	Voer het algoritme uit
	Loop je vast? Probeer de heuristiekboom bij opgave 5a, bij opgave 5b, bij opgave 5c, bij opgave 5d en bij opgave 5e!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 6

De Zeef van Eratosthenes wordt in veel schoolboeken als verdiepingsstof behandeld. Het betreft het volgende algoritme:

1. Voer het algoritme handmatig uit met $n=30$, of overtuig je ervan dat het overeenkomt met het algoritme uit de schoolboeken.

Het algoritme kan in iets minder stappen door in regel 4.1 '$j\leftarrow 2p$' te vervangen door '$j\leftarrow p^2$' en in regel 4 '$p\le n$' door '$p^2\le n$'.

2. Waarom verandert dit de uitvoer van het algoritme niet?

Zij $n$ de invoer van het algoritme en laat $X$ de verzameling priemgetallen in het interval $[1,n]$ zijn.

3. Laat zien dat de instructies op regels 4.2.1 en 4.2.2 nooit vaker dan $\sum_{p\in X}\frac np$ maal wordt uitgevoerd.
4. [Facultatief, alleen als je al aan de notatie bent gewend:] Laat zien dat het aantal regels dat wordt doorlopen ${\cal O}(n\ln\ln n)$ is. Je mag het volgende resultaat gebruiken: $\sum\frac1p={\cal O}(\ln\ln n)$.

	Loop je vast? Probeer de heuristiekboom bij opgave 6a en bij opgave 6c!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst