Vorige week zijn we in de congruenties gedoken en heb je kennis gemaakt met een formele benadering van congruentierekening met behulp van restklassen. Deze week richten we ons op slechts één rekenoperatie op restklassen: delen.
Vergeet niet om ook week 3 goed af te ronden – kijk met name zorgvuldig naar de verwerkingsopgaven van week 3!
Basis
De basis deze week bevat wat herhaling van dingen die je al elders bent tegengekomen. En daarnaast wordt de heuristiekboom-opdracht vrijgegeven – een onderdeel van de toetsing die je aan het einde van cursus moet inleveren.
Inverteerbaarheid
Je hebt vorige week al kort kennisgemaakt met inverteerbare restklassen: restklassen $a$ waarvoor er een restklasse $b$ is zodat het product van $a$ en $b$ de identiteit is. Zorg dat je de definitie van inverteerbaarheid goed beheerst, want het staat deze week centraal.
| Kern: | |
 | Bestudeer nogmaals de definitie van inverteerbaarheid van restklassen helemaal aan het einde van §9 van de reader |
| Extra ondersteuning: | |
 | Agendeer dit thema voor de bijeenkomst |
Software
In lesweek 6 is de RSA-computeropdracht. Dit is een goed moment om de software te installeren.
Bij de computeropdracht over cryptografie is software nodig. Deze is gratis beschikbaar, maar voor de installatie moet wel Java worden geactiveerd. Soms geeft installeren hiervan wat gedoe, dus zorg dat je het op tijd probeert. Zie de instructies. Per tweetal is één laptop waarop het werkt in principe voldoende. Neem gerust contact op met de docent als het niet lukt. In lesweek 6 gaan we de computeropdracht tijdens de werksessie maken en meteen ook afronden, maar als dat je beter uitkomt, mag je het ook buiten die sessie om doen.
Mensen die van dit soort uitdagingen houden, kunnen als alternatief proberen om het uiterst krachtige programma Pari te installeren. Er is een korte handleiding beschikbaar.
Heuristiekboom-opdracht
De heuristiekboom-opdracht is onderdeel van de toetsing. De opdracht komt binnenkort beschikbaar. Inleveren doe je aan het einde van de periode – één product per groepje volstaat. Je krijgt een stelling aangereikt. De opdracht is om hier een heuristiekboom bij te ontwerpen aan de hand van de fases van probleemaanpak van Pólya. Beoordeling gebeurt aan de hand van een rubric. Getoetst wordt in hoeverre je de structuur van een bewijs weet te doorgronden. De opdracht wordt beoordeeld met een cijfer.
Je kunt de web-app gebruiken om je heuristiekboom te maken, maar dat is niet verplicht. Je mag het ook op papier (foto) of bijvoorbeeld in Powerpoint doen.
| Extra ondersteuning: | |
 | Je kunt je verdiepen in de theoretische achtergrond van heurtistiekbomen. |
Verdieping
De $\varphi$-functie van Euler
Allereerst hoor je vertrouwd te zijn met de formele notaties gerelateerd aan inverteerbare restklassen – en in het bijzonder met de verzameling $\ZZ_n^*$ van inverteerbare restklassen modulo $n$ die in dit thema wordt geïntroduceerd. Vervolgens kun je je op hoger niveau vragen stellen: in dit geval over het aantal inverteerbare restklassen. Dit leidt tot de $\varphi$-functie van Euler. Er wordt van je verwacht dat je met deze functie kunt redeneren.
| Kern: | |
| §10 van de reader |
| Extra ondersteuning: | |
 | Inverteerbare restklassen |
| De $\varphi$-functie van Euler |
 | §2.4 in het boek van De Weger biedt in opgaven 2.40–2.45 oefeningen in redeneringen met de $\varphi$-functie |
 |
Controleer en produceer je eigen oefeningen: $\varphi\Bigl($$\Bigr)={}$ Let op: het hier gebruikte algoritme is heel inefficiënt (want we gebruiken het trage algoritme uit opgave 4 van week 2 als deelstap in de berekening van $\varphi(n)$). Het advies is daarom om alleen getallen $<10^8$ in te voeren, tenzij je zin hebt in koffie. Wil je je niet laten beperken, gebruik dan slimmere algoritmes zoals die in Wolfram Alpha (voorbeeld-instructie: eulerphi(12345)) of de software die gebruikt wordt bij de RSA-computeropdracht in lesweek 6 (zie hiervoor). |
| Agendeer dit thema voor de bijeenkomst |
Verwerking
De volgende stellingen bieden oefening in het gebruik van de definitie van inverteerbaarheid, en het vinden van inversen.
Opgave 1
Los de volgende vergelijking respectievelijk congruentie op.
- $\overline{7}x=\overline 1$, waarbij $x\in\ZZ_{13}$
- $4321x\equiv 321\pmod{12347}$, waarbij $x\in\ZZ$
 | Loop je vast? Probeer de heuristiekboom bij onderdeel a en die bij onderdeel b |
 |
Minder leerzaam: de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
Opgave 2
Gegeven $n\in\NN_{\ge1}$ en $a\in\ZZ$. Onder welke voorwaarden geldt: $$\hbox{voor alle $x,y\in\ZZ_n$:}\quad \overline ax=\overline ay\Rightarrow x=y\quad?$$
| Loop je vast? Probeer de heuristiekboom! |
|
Minder leerzaam: de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
De volgende twee opgaven bieden oefening in het berekenen van de waarde van de $\varphi$-functie van Euler.
Opgave 3
Een definitie van Eulers $\varphi$-functie luidt
$\varphi(n)$ is het aantal gehele getallen vanaf $1$ (inclusief) tot $n$ die relatief priem zijn met $n$.Gebruik alleen (!) deze definitie om de volgende waarden te bepalen.
- $\varphi(11)$
- $\varphi(6)$
- $\varphi(24)$
- $\varphi(p)$ met $p$ priem
- $\varphi(pq)$ met $p\not=q$ priem
- $\varphi(p^3)$ met $p$ priem
Er is ook een handige formule: $$\varphi\bigl(p_1^{a_1}\ldots p_r^{a_r}\bigr) = (p_1-1)p_1^{a_1-1}\ldots (p_r-1)p_r^{a_r-1}.$$
- Bepaal bovenstaande waarden nu direct met deze formule.
|
Controleer je antwoorden: $\varphi\Bigl($$\Bigr)={}$ |
|
Maar je kunt ook kijken in de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
Opgave 4
Bepaal $\varphi(n)$ voor de volgende waarden van $n$.
- $101$
- $105$
- $2^{10}$
|
Controleer je antwoorden: $\varphi\Bigl($$\Bigr)={}$ |
|
Maar je kunt ook kijken in de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
In de volgende opgaven keren we de boel om: je gaat op zoek naar inverse beelden bij Eulers $\varphi$-functie.
Opgave 5
Bepaal alle $n\in\NN$ met $\varphi(n)=8$.
| Loop je vast? Probeer de heuristiekboom! |
|
Minder leerzaam: de uitwerking |
|
Controleer je antwoorden: $\varphi\Bigl($$\Bigr)={}$ |
| Agendeer deze vraag voor de komende bijeenkomst |
Opgave 6
Bepaal alle $n\in\NN$ met $\varphi(n)=14$.
| Loop je vast? Probeer de heuristiekboom! |
|
Minder leerzaam: de uitwerking |
|
Controleer je antwoorden: $\varphi\Bigl($$\Bigr)={}$ |
| Agendeer deze vraag voor de komende bijeenkomst |
Opgave 7
Voor welke $n\in\NN_{\ge1}$ geldt $\varphi(n)|n$ ?
| Loop je vast? Probeer de heuristiekboom! |
|
Minder leerzaam: de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
We ronden af met een klassieker: de Stelling van Wilson.
Opgave 8
Zij $n\in\ZZ$ met $n>1$. Stelling: $$\hbox{$n$ is priem} \qquad\iff\qquad (n-1)!\equiv-1\pmod n.$$
- Bewijs eerst '$\Leftarrow$' door aan te nemen dat de congruentie geldt terwijl $n$ samengesteld is.
Voor het bewijs van '$\Rightarrow$' nemen we aan dat $n$ priem is en oneven (het enige geval dat dan overblijft, $n=2$, is 'triviaal'!). Bekijk nu het volgende tussenresultaat:
De verzameling $\{2,\ldots,n-2\}$ is op te delen in paartjes waarvan het product steeds congruent is met $1$ (modulo $n$).
Het bewijs hiervan gaat als volgt. Voor iedere $x\in\{2,\ldots,n-2\}$ is er een unieke $y$ in het interval $[0,n-1]$ zodat $xy\equiv 1\pmod n$; de inversen in $\ZZ_n$ zijn immers uniek. Voor deze $y$ geldt zelfs weer $2\le y\le n-2$ [$*$]. Wat rest is te bewijzen dat $x\not=y$. Maar als $x=y$ dan geldt $x^2\equiv 1\pmod n$ en dus is $x$ een oplossing van de vergelijking $(x-1)(x+1)\equiv 0\pmod n$. Dus $n|(x\pm1)$ en dus $x\equiv 1\pmod n$ of $x\equiv -1\pmod n$; tegenspraak.
- Verklaar de zin waar een $*$ achter staat.
- Op welke plekken (mogelijk meerdere) in het bewijs wordt gebruikt dat $n$ priem is?
- Maak het bewijs van '$\Rightarrow$' af.
| Loop je vast? Probeer de heuristiekboom bij onderdeel a en bij onderdeel b en bij onderdeel d! |
|
Minder leerzaam: de uitwerking |
| Agendeer deze vraag voor de komende bijeenkomst |
PROGRAMMA LESWEEK 7
26 maart 2025
 | Als je graag dingen op papier wil, zijn hier alle opgaven van deze week, met uitwerkingen. Ook is er de volledige reader. Maar denk om het milieu! |