Categorie archieven: Geen categorie

Bewijs door inductie

Geplaatst op door 
domino
Vaak bestaat een probleem erin aan te tonen dat een bepaalde 
eigenschap geldt voor elk natuurlijk getal.
Als je wilt weten of iets waar is voor alle natuurlijke 
getallen n (dus voor n = 1, 2, 3, . . .), kun je ze niet 
allemaal afgaan: daar zou je oneindig lang mee bezig zijn. 

Inductie is eigenlijk een verzameling van bewijstechnieken 
die de waarheid van een stelling voor alle elementen van een 
verzameling aantonen door gebruik te maken van de onderliggende 
structuur van de verzameling. 

Om de geldigheid te bewijzen van een uitspraak van de vorm 
" Voor ieder natuurlijk getal n geldt P(n)", 
waarbij P(n) staat voor een bewering  (propositie) waarin n 
voorkomt, maakt men vaak gebruik van deze  methode. 
Lees  meer hierover in volgend artikel, waar een paar 
voorbeelden worden uitgewerkt en waar ook een heleboel opgaven staan.

Modulorekenen

Geplaatst op door

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.

Hoofdstelling van de rekenkunde

Geplaatst op door

Elk samengesteld getal kan geschreven worden als het product van kleinere factoren. Als minstens 1 van beide samengesteld is , kan men die ook weer schrijven als product van kleinere factoren. Zo kan men doorgaan tot er slechts priemgetallen als factoren overblijven. men kan een samengesteld getal in het algemeen op verschillende manieren via een aantal tussenstappen in priemgetallen ontbinden. Het uiteindelijk resultaat, de ontbinding in priemfactoren, is steeds hetzelfde. Dit resultaat staat bekend als de hoofdstelling van de rekenkunde:

    \[\begin{center}De ontbinding in priemfactoren van een \\ natuurlijk getal is eenduidig bepaald.\end{center}\]

Deze eigenschap is in andere getalsysytemen niet noodzakelijk waar. Beschouw de verzameling van de even getallen \left\{2,4,6,\cdots \right\}. Sommige ervan kan men schrijven als het product van even factoren, bijvoorbeeld 20=2.10. Bij andere is dat niet mogelijk. We noemen even getallen die niet het product zijn van even factoren even-priemgetallen. Een even getal is te schrijven als product van even-priemgetallen, maar zo een ontbinding hoeft niet eenduidig te zijn. Zo is 420=6.70=10.42

Als een getal ontbonden is in priemfactoren, dan kan men het aantal delers bepalen. Stel dat n=2^{e_1}.3^{e_2}.5^{e_3}. \ldots .p_k^{e_k} dan heeft n juist (e_1+1)(e_2+1)(e_3+1).\ldots.(e_k+1) delers.

woestijn