Stelling van Wilson

De kleine stelling van Fermat zegt ons dat voor een priemgetal p geldt dat a^p \equiv a \mod{p}. Maar dan zijn 1,2, … , p – 1 allemaal nulpunten van de veelterm X^{p-1}-1 in de verzameling \mathbb{Z}_p[X] en dus kunnen we, omdat er geen nuldelers zijn, volgende ontbinding neerschrijven: X^{p-1}-1 = (X-1)(X-2) \cdots (X-(p-1)).
Door hierin X te vervangen door 0, vinden we een deel van volgende stelling:

    \[p \text{ is priem  als en slechts als } (p-1)! \equiv -1 \mod{p}\]

Dit resultaat staat bekend als de stelling van Wilson, naar de Engelse wiskundige John Wilson (1741-1793). Nochtans komt dit resultaat een eerste keer voor bij Abu Ali al-Hasan ibn al-Haytham (965-1040)

Bovendien had Wilson geen bewijs van de stelling. Het was Lagrange die in 1771 het eerste bewijs ervan formuleerde.

Het is ook duidelijk dat als n een samengesteld getal is, groter dan 4,  dat  (n-1)! \equiv 0 \mod{n}.

Een algemene vorm is voor ieder oneven priemgetal p en voor ieder positief geheel getal k kleiner dan p:

    \[(k-1)!(p-k)! \equiv (-1)^k \mod{p}\]

Deze veralgemening danken we aan C.F.Gauss

De Chinese reststelling

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

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

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

Antwoord Klik hier

Modulorekenen

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.

dis

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.