WEEK 5

Stelling van Euler

De Stelling van Euler beschrijft een regelmaat in het modulair machtsverheffen. Je moet de stelling kennen, kunnen bewijzen en kunnen gebruiken. De Kleine stelling van Fermat is een direct gevolg van de stelling van Euler: ook deze moet je beheersen.

Kern:
	§11 van de reader
Extra ondersteuning:
	De Stelling van Euler
	§2.5 in het boek van De Weger gaat uitgebreid in op de Kleine stelling van Fermat
	Agendeer dit thema voor de bijeenkomst

Opgave 1

Bepaal alle $x\in\ZZ$ die voldoen aan de volgende congruenties: $$\begin{array}{rcl} x&\equiv& 2\pmod4\\ x&\equiv& 5\pmod7\\ x&\equiv& 8\pmod{15} \end{array}$$ Vergeet je antwoord niet te controleren!

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

Opgave 2

Bepaal alle $x\in\ZZ$ die voldoen aan de volgende congruenties: $$\begin{array}{rcl} x&\equiv& 3\pmod{542}\\ 9x&\equiv& 1\pmod{421} \end{array}$$

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

Opgave 3

Los het volgende probleem op uit de Chinese oudheid:

Zeventien bandieten hebben een kist met gouden munten buitgemaakt. Wanneer ze de munten eerlijk verdelen, blijken er drie muntstukken over te blijven. In het gevecht dat hierom ontstaat, komt één bandiet om het leven. Opnieuw proberen de bandieten de buit te verdelen, maar nu blijven er tien muntstukken over. Er breekt opnieuw een gevecht uit en deze keer sterven er vijf bandieten. De overlevenden proberen de munten weer te verdelen en nu blijven er vier over. Wederom is er een gevecht met vier doden. De overlevenden kunnen de munten eerlijk verdelen. Wat is het kleinst mogelijke aantal muntstukken in de kist?

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

Opgave 4

Leg uit waarom de Chinese reststelling een bijectie $$\ZZ_M\longrightarrow\ZZ_{m_1}\times\cdots\times\ZZ_{m_r}$$ beschrijft (waarbij $m_1,\ldots,m_r\ge2$ paarsgewijs copriem zijn en $M=m_1\cdots m_r$). (Zie ook §9b in de reader.)

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

Opgave 5

Laat zien dat er een miljoen opeenvolgende gehele getallen bestaan, waarbij voor ieder getal geldt dat het deelbaar is door een kwadraat ongelijk aan $1$.

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

Opgave 6

In de volgende opgaven is de vraag steeds om de kleinste $a\in\NN$ te bepalen. Doe dit op een efficiënte manier, bijvoorbeeld met behulp van de stelling van Euler.

1. $a\equiv 2^{68}\pmod{19}$
2. $a\equiv 68^{141}\pmod{213}$
3. $a\equiv 2^{4312}\pmod{12}$

	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 7

Bepaal de laatste twee decimalen van $3^{1492}$.

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

Opgave 8

Toon aan: $\phi(m)$ is een veelvoud van de orde van $x\in\ZZ_m^*$. (Per definitie is de orde van $x$ het kleinste positieve gehele getal $n$ waarvoor geldt $x^n=\overline{1}$.)

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

Opgave 9

Gebruik o.a. de Chinese reststelling om de kleinste $a\in\NN$ te vinden waarvoor geldt $a\equiv13^{120}\pmod{2310}$. Doe hetzelfde voor $a\equiv 127^{128}\pmod{129}$.

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

Opgave 10

Stel $p$ en $q$ zijn twee priemgetallen die ongelijk zijn aan elkaar en neem $N=pq$. Zij $e\in\NN$ een getal dat copriem is met $\phi(N)$. Zij $a\in\ZZ$.

Bewijs: Er bestaat een $f\in\NN$ zodat $ef\equiv 1\pmod{\phi(N)}$ en voor zo'n $f$ geldt $a^{ef}\equiv a\pmod N$.

(Merk op dat $a$ niet noodzakelijk copriem met $N$ hoeft te zijn.)

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