WEEK 3

Unieke priemfactorisatie

De Hoofdstelling van de rekenkunde zegt dat ieder positief geheel getal een product is van priemgetallen. Verder zegt de stelling dat dit product uniek is, hoewel je wel even zorgvuldig moet zijn in hoe je die uniciteit precies formuleert. Deze stelling kende je waarschijnlijk al en heb je heel vaak nodig. Nieuw is mogelijk het bewijs, dat je voor deze cursus ook moet begrijpen.

Kern:
	§8 van de reader
Extra ondersteuning:
	§1.5 in het boek van De Weger bevat ook een bewijs van de Hoofdstelling
	Agendeer dit thema voor de bijeenkomst

Restklassen

Ook het 'klokrekenen' kan geformaliseerd worden. Dat gebeurt via zogenaamde restklassen. Er wordt verwacht dat je de definitie van restklassen begrijpt en kunt hanteren, net als de verzameling van restklassen-modulo-$m$, genoteerd $\ZZ_m$.

Kern:
	§9 van de reader
Extra ondersteuning:
	De voorkennis in modulorekenen (klokrekenen) wordt overzichtelijk uitgelegd op de site van Henk Hofstede
	Definities van congruentie en restklassen
	Rekenen met restklassen
	Agendeer dit thema voor de bijeenkomst

Opgave 1

Bekijk de Hoofdstelling van de rekenkunde (d.w.z. ieder positief geheel getal is op unieke manier te ontbinden in priemfactoren). Leid hieruit de volgende stelling af.

Ieder getal $x\in\QQ$ ongelijk aan nul is uniek te schrijven als $$x=\varepsilon\prod_{p\in{\cal P}}p^{n_p},$$ waarbij $\varepsilon=\pm1$ en $n_p\in\ZZ$ en $n_p\not=0$ voor slechts eindig veel $p$.

(Hier is ${\cal P}$ de verzameling priemgetallen en duidt de $\prod$-notatie op het product van de termen $p^{n_p}$ waarbij $p\in{\cal P}$.)

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

Opgave 2

Deze opgave gaat over het bewijs van de Hoofdstelling van de rekenkunde (unieke priemfactorontbinding). Het bewijs van uniciteit berust op een lemma:

Als een priemgetal $p$ een product $ab$ deelt, dan $p|a$ of $p|b$.

1. De aanname dat $p$ een priemgetal is, is essentieel. Geef een tegenvoorbeeld in het geval $p$ niet priem is.

In de reader staat een bewijs van dit lemma.

2. Waar wordt in dit bewijs gebruikt dat $p$ een priemgetal is?

In de formulering van de hoofdstelling wordt gesproken over een unieke priemfactorontbinding $p_1^{k_1}p_2^{k_2}\ldots p_r^{k_r}$, waarbij de exponenten positieve natuurlijke getallen zijn en voor de priemfactoren geldt $p_1<p_2<\dots<p_r$.

3. Waarom geldt de stelling niet als niet wordt geëist $p_1<p_2<\dots<p_r$, maar enkel dat de priemgetallen alle verschillend zijn?
4. En waarom geldt de stelling niet als de exponenten ook nul zouden mogen zijn?

Zij $\cal P$ de verzameling priemgetallen. Bekijk de volgende uitspraak: voor ieder positief geheel getal bestaat er een unieke functie $k\colon{\cal P}\to\NN$ zodat het inverse beeld $k^{-1}(\NN_{\ge 1})$ van $\NN_{\ge1}$ eindig veel elementen heeft en$$n=\prod_{p\in{\cal P}}p^{k(p)}.$$

5. Is deze uitspraak een equivalente formulering van de hoofdstelling van de rekenkunde?

In het existentiedeel van het bewijs van de hoofdstelling wordt een algoritme beschreven.

6. Beschrijf dit algoritme voor de invoer $n=256$.
7. Beschrijf dit algoritme voor de invoer $n=101$ (een priemgetal).
8. Beargumenteer: het algoritme heeft exponentiële complexiteit.

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

Opgave 3

Zij $n\in\NN$. Deze opgave gaat over de stelling dat er een rij van $n$ opeenvolgende samengestelde getallen bestaat. (Merk op dat de stelling niet inhoudt dat er twee priemgetallen bestaan waartussen precies $n$ samengestelde getallen liggen; enkel dat er ten minste zoveel tussenliggen.)

De truc is om naar de uitdrukking $n!+a$ te kijken voor bepaalde waarden van $a$.

1. Bewijs dat $r$ een deler is van $n!+r$ voor alle $r$ waarvoor geldt $1\le r\le n$.
2. Produceer een rij van $n$ opeenvolgende samengestelde getallen en bewijs dat die getallen inderdaad alle samengesteld zijn.

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

Opgave 4

Geef van elk van de volgende vier uitspraken een bewijs. Steeds is $n$ een positief natuurlijk getal.

1. Als $a_1\equiv a_2\pmod n$ en $b_1\equiv b_2\pmod n$, dan $a_1+b_1\equiv a_2+b_2\pmod n$.
2. Als $a_1\equiv a_2\pmod n$ en $b_1\equiv b_2\pmod n$, dan $a_1b_1\equiv a_2b_2\pmod n$.
3. Gegeven $a,b\in\ZZ$. De congruentie $ax\equiv b\pmod n$ heeft een oplossing precies dan als $b$ een veelvoud is van $\ggd(a,n)$.
4. Gegeven $a,b\in\ZZ$ en een priemgetal $p$. Als $p\nmid a$ dan heeft de congruentie $ax\equiv b\pmod p$ een unieke oplossing [erratum: uniek op veelvouden van $p$ na].

Het is mogelijk de bovenstaande uitspraken te formuleren in termen van restklassen.

5. Doe dat voor uitspraak d.
6. Leg uit waarom onderdeel b het mogelijk maakt vermenigvuldiging van restklassen te definiëren.
7. Bewijs: als $x,y,z\in\ZZ_n$, dan geldt $x(yz)=(xy)z$ (d.w.z. associativiteit van vermenigvuldiging).

	Loop je vast? Probeer de heuristiekboom bij onderdeel a, bij onderdeel b, bij onderdeel c, bij onderdeel d of bij onderdeel g!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 5

Het beroemde binomium van Newton zegt $$(a+b)^n=\sum_{i=0}^n\left({n\atop i}\right)a^ib^{n-i}\qquad(a,b\in\RR,\ n\in\NN).$$

1. Geef een verklaring voor deze gelijkheid.
2. Zij $p$ een priemgetal en zij $a\in\ZZ_p$. Bewijs dat $$(x+a)^p=x^p+a^p$$voor alle $x\in\ZZ_p$.

(Dit resultaat wordt wel de Freshman's dream genoemd: de droom van iedere leerling!)

3. Gebruik onderdeel b met $a=1$ om, middels volledige inductie over $x$, de Kleine stelling van Fermat te bewijzen:$$x^p\equiv x\pmod p\qquad\hbox{voor alle $x\in\ZZ$.}$$

	Loop je vast? Probeer de heuristiekboom bij onderdeel a, bij onderdeel b of bij onderdeel c!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 6

Voor tal van toepassingen is het belangrijk om ogenschijnlijk willekeurige reeksen getallen te kunnen genereren. Computers gebruiken hiervoor vaak een algoritme dat de 'lineaire congruentiegenerator' heet. De programmeur kiest een modulus $m\ge2$ en $a,b,x_0\in\ZZ_m$ met $a\not=0$. Vervolgens wordt een rij 'toevalsgetallen' geproduceerd met de recursievergelijking $$x_{n+1}=ax_n+b.$$

1. Bereken voor $m=45$, $a=\overline{16}$, $b=\overline{2}$ en $x_0=\overline{0}$ een aantal 'toevalsgetallen'.
2. Waarom worden $x_0$, $x_1$, ... pseudo-toevalsgetallen genoemd?
3. Bewijs dat de rij $(x_0,x_1,x_2,\ldots)$ repeterend is.

Windows gebruikt $m=2^{31}-1$, $a=\overline{2147483629}$ en $b=\overline{2147483587}$. De waarde van $x_0$ wordt bij het opstarten bepaald, bijvoorbeeld op grond van het tijdstip van de dag. Zo wordt voorkomen dat iedere keer dezelfde 'toevalsgetallen' worden gegenereerd.

1. Bereken met de computer de eerste tien toevalsgetallen als de startwaarde $x_0=\overline{0}$ is.

	Voer het algoritme uit
	Loop je vast? Probeer de heuristiekboom bij onderdeel c!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst