Wiskunde is leuk

De Chinese reststelling

Geplaatst op 3 mei 2018 door admin

Naast lineaire congruenties , kan je ook werken met stelsels van lineaire congruenties. Zoals bijvoorbeeld:

Volgens de Chinese reststelling geldt dan: Als elke $a_i$ en $m_i$ onderling ondeelbaar zijn en als alle $m_i$ twee aan twee onderling ondeelbaar zijn, dan heeft dit stelsel een unieke oplossing modulo $m_1.m_2.\cdots.m_n$ .

Los op:
$\begin{cases} x\equiv 2 \text{ mod }5 \\3x\equiv 1 \text{ mod }8 \end{cases}$ of $\begin{cases} x\equiv 2 \text{ mod }5 \\x\equiv 3 \text{ mod }8 \end{cases}$

Dit betekent dat $x=2+5k=3+8l$ . Dus $5k \equiv 1 \text{ mod } 8$ of $k \equiv 5 \text{ mod } 8$ . Hieruit volgt dat $k=5+8p$ en dus is $x=2+5(5+8p)=27+40p$ .

De unieke oplossing van het gegeven stelsel is $x=27 \text{ mod } 40$ .

Lineaire congruenties

Geplaatst op 1 mei 2018 door admin

Naast lineaire vergelijkingen , kunnen we ook lineaire congruenties bekijken:

$ax \equiv b \text{ mod } m \text{ met } a,b,m\in \mathbb{Z}$

Hier is de vraag of er een gehele x te vinden is zodat $ax-b$ deelbaar is door m. Het is duidelijk dat als $x_0$ een oplossing is, dan zijn alle getallen uit de restklasse $x_0 \text{ mod } m$ ook oplossingen. De oplossingsverzameling verandert ook niet als we a en b veranderen in andere getallen uit hun restklasse mod m. Onder een oplossing van een lineaire congruentie verstaat men dus een restklesse mod m.

Wanneer is een congruentie oplosbaar? Dat is zo als en slechts als de grootste gemene deler van a en m een deler is van b. Als a en m onderling ondeelbaar zijn, bestaat het inverse element van a mod m en is dus $x=a^{-1}b \text{ mod } m$ . Als de grootste gemene deler d van a en m niet 1 is , dan delen we eerst door d en dan krijgen we vorige situatie.
In het geval dat ggd(a,m) = 1 hebben we een unieke oplossing. Als echter ggd(a,m) = d , dan hebben we d oplossingen. We krijgen immers 1 oplossing mod $\frac{m}{d}$ en deze geeft precies volgende verschillende restklassen mod m: $x_0, x_0+\frac{m}{d},x_0+2\frac{m}{d},\cdots, x_0+(d-1)\frac{m}{d}$ .

Los op : $6x \equiv 8 \text{ mod }10$ .

Delen door de ggd(6,10) = 2 geeft $3x \equiv 4 \text{ mod } 5$ .
Omdat $3.2 = 6 \equiv 1 \text{ mod } 5$ is $3^{-1} =2$
En dus is $x\equiv 2.4 \equiv 3 \text{ mod } 5$ .
Alle oplossingen zijn dus de restklassen 3 en 8 modulo 10. De oplossingsverzameling is:
$\{3+10k, 8+10l \text{ met } k,l\in \mathbb{Z}\}$

Opgave 9

Geplaatst op 6 januari 2018 door admin

Definieer $a_1=2018$ en $a_{n+1}=9^{a_n}$ voor n=1,2,…
Bepaal de laatste twee cijfers van $a_{2018}$ .

Antwoord

We kunnen voor $k=1,2,...,10$ de laatste twee cijfers berekenen van $9^k$ . We vinden $9^{10}=3486784401$ en eindigt dus op $01$ .
Als $(9^{10})^n$ eindigt op 01, dan zal ook $(9^{10})^{n+1}$ eindigen op 01, want $(9^{10})^{n+1}=(9^{10})^n.9^{10}=(\cdots 01).(\cdots 01)=(\cdots 01)$ .
Door inductie hebben we dus bewezen dat elke macht van $9^ {10}$ eindigt op 01.
Dan is $a_2=9^{2018}=(9^{10})^{201}.9^8=(\cdots01).43046721$ en dus eindigt $a_2$ op 21.
Verder is $a_3=9^{\cdots 21}=(9^{10})^{\cdots 2}.9^1=(\cdots 01).9=\cdots 09$ . Bijgevolg eindigt $a_3$ op 09.
Nu is $a_4=9^{\cdots 09}=(9^{10})^{\cdots 0}.9^9=(\cdots 01).387420489=\cdots 89$ .
Het is duidelijk dat alle verdere termen van de rij op 89 zullen eindigen.
Dus $a_{2018}$ eindigt op 89.

Modulorekenen

Geplaatst op 12 oktober 2016 door admin

De eindige rekenkunde, ook wel modulaire rekenkunde genoemd, wordt beschreven in het boek Disquisitiones Arithmeticae van Gauss, een buitengewoon invloedrijk werk uit 1801, toen de auteur nog maar vierentwintig jaar oud was.

Stel $a,b,m \in \mathbb{Z},m>1$ . Indien $a$ en $b$ bij deling door $m$ dezelfde rest geven, d.w.z. indien $a-b=cm$ voor zekere $c \in \mathbb{Z}$ , heten $a$ en $b$ congruent modulo $m$ . We noteren $a\equiv b$ mod m.Zo is bijvoorbeeld $3\equiv 63$ mod 5, $7\equiv -1$ mod 8 en $12^2\equiv 1$ mod 13.

Enkele eigenschappen :

Als $a\equiv b$ mod m en $b\equiv c$ mod m, dan is $a\equiv c$ mod m.
Als $a\equiv b$ mod m en $c\equiv d$ mod m, dan is $a+c\equiv b+d$ mod m.
Als $a\equiv b$ mod m en $n \in \mathbb{N}$ , dan is $a^n\equiv b^n$ mod m.
Als $a\equiv b$ mod m dan is voor elke $c \in \mathbb{Z}$ : $ac\equiv bc$ mod m.
Als $a\equiv b$ mod m en $c\equiv d$ mod m, dan is $ac\equiv bd$ mod m.

Rekenen met congruenties lijkt erg op het rekenen met vergelijkingen. Er is echter een belangrijk verschil: uit $ac\equiv bc$ mod m met $c\neq 0$ mod m hoeft niet te volgen dat $a\equiv b$ mod m. Zo is $6.12\equiv 6.7$ mod 10 maar 12 is niet congruent met 7 modulo 10. In andere gevallen gaat het wel op. De voorwaarde waarop de vereenvoudiging met $c$ wel kan, is dat $c$ onderling ondeelbaar is met $m$ .
Dus als $ac\equiv bc$ mod m en ggd(c,m) = 1, dan is $a\equiv b$ mod m.
Als ggd(c,m) = d, dan volgt uit $ac\equiv bc$ mod m dat $a\equiv b$ mod( $\frac{m}{d}$ ).

Rekent men modulo $m$ , dan zijn er $m$ verschillende soorten getallen, al naar gelang ze verschillende resten geven bij deling door $m$ . De verzameling van alle gehele getallen die eenzelfde rest geven heet een restklasse modulo $m$ . Er zijn dus precies $m$ verschillende restklassen modulo $m$ . De restklasse die een getal $a$ bevat, noteert men als $\overline{a}$ . Deze notatie is natuurlijk niet eenduidig bepaald, want als $a\equiv b$ mod m, stellen $\overline{a}$ en $\overline{b}$ dezelfde restklasse modulo $m$ voor en omgekeerd.

Werken we modulo 4 dan is $\overline{0}=\left\{0,4,8,12,\cdots}\right\}$ , $\overline{1}=\left\{1,5,9,13,\cdots\right\}$ , $\overline{2}=\left\{2,6,10,14,\cdots\right\}$ , $\overline{3}=\left\{3,7,11,15,\cdots\right\}$ .

Men kan in de verzameling restklassen modulo $m$ , genoteerd door $\mathbb{Z}_m$ , een optelling en een vermenigvuldiging defini\”eren via $\overline{a}+\overline{b}=\overline{a+b}$ en $\overline{a}.\overline{b}=\overline{ab}$ . Deze rekenregels lijken erg op de regels van optelling en vermenigvuldiging van gehele getallen.

Eigenschappen :

$\forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}+\overline{b}=\overline{b}+\overline{a}.$
$\forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}.\overline{b}=\overline{b}.\overline{a}.$
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}+\overline{b})+\overline{c}=\overline{a}+(\overline{b}+\overline{c})$ .
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}.\overline{b}).\overline{c}=\overline{a}.(\overline{b}.\overline{c})$ .
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : \overline{a}.(\overline{b}+\overline{c})=\overline{a}.\overline{b}+\overline{a}.\overline{c}$ .
$\forall \overline{a}\in \mathbb{Z}_m : \overline{a}+\overline{0}=\overline{a}.$
$\forall \overline{a}\in \mathbb{Z}_m : \overline{a}.\overline{1}=\overline{a}.$
Er is een unieke restklasse $\overline{x}$ met $\overline{a}+\overline{x}=\overline{0}$ , namelijk $\overline{x}=\overline{-a}$ .

Veronderstel dat we de rest willen bepalen van $73\times52$ bij deling door 7. Omdat $73 \equiv 3$ mod 7 en $52 \equiv 3$ mod 7, moet $73\times52 \equiv 3\times 3$ mod 7 $\equiv 9$ mod 7 $\equiv 2$ mod 7. Dus de rest bij deling van $73\times52$ door 7 is 2. We moeten daarvoor het product niet uitrekenen.

Definieer en voor n=1,2,… Bepaal de laatste twee cijfers van .

Antwoord

Definieer $a_1=2018$ en $a_{n+1}=9^{a_n}$ voor n=1,2,…
Bepaal de laatste twee cijfers van $a_{2018}$ .