Uit het hoofd betekent dat we niets gaan opschrijven. We gebruiken puur hoofdrekenen. Hoofdrekenen is leuk. Het traint je hersenen, het traint je kortetermijngeheugen, en je kan iets wat nog weinig mensen meer kunnen. Ieder getal kun je op
unieke wijze schrijven als vermenigvuldiging van priemgetallen. We noemen dit priemfactorisatie. Met behulp van de eerdere artikelen over deelbaarheid, gaan we nu proberen om getallen te ontbinden in priemfactoren. Omdat het hoofdrekenen is, is de grootte van de getallen natuurlijk beperkt. Typisch getallen van drie cijfers, maar met wat oefening kan je ook getallen van vier cijfers aan.

Voor we eraan beginnen, bespreken we eerst een paar zaken die ons het leven gemakkelijk gaan maken. Bij hoofdrekenen proberen we de bewerkingen zo te plannen dat je niet te veel tegelijk moet onthouden. Ten eerste, als we delers zoeken van een getal $N$, hoeven we enkel priemfactoren $p$ te proberen als delers. We moeten dus eigenlijk enkel de deelbaarheid testen door $2, 3, 5, 7, 11, 13, 17, \ldots$. We beginnen met de kleinste priemgetallen, want daar maken we de meeste kans. Waarom werkt dit? Wel, je hoeft niet te testen of een getal deelbaar is door $6$, als je al vastgesteld hebt dat het niet deelbaar is door $2$. Je hoeft niet te testen of een getal deelbaar is door $9$ als het al niet deelbaar is door $3$.

Ten tweede, kan je natuurlijk proberen delen door alle priemgetallen die kleiner zijn dan ons getal $N$. Maar dat hoeft niet. We proberen natuurlijk zo efficiënt mogelijk te werk te gaan. Nee, de echte grens om te stoppen is de wortel van ons getal $N$. Waarom? Noem die wortel $M$. Dan is $N = M^²$. Stel dat je alle priemgetallen $p$ kleiner dan $M$ al geprobeerd hebt, en je hebt nog geen deler gevonden. Als je nu verder zou proberen en je zou toch nog een priemgetal $q$ vinden, groter dan $M$ en dat toch een deler zou zijn van $N$. Hoe zit het dan met het getal $N/q$? $N/q = M^2/q = M \times (M/q)$ is kleiner dan $M$ want $(M/q)$ is kleiner dan $1$. Maar dan heb je toch een deler kleiner dan $M$, en je had al vastgesteld dat er geen deler kleiner dan $M$ bestond. Dat is dus een tegenspraak. Dus is de oorspronkelijke veronderstelling niet waar. 

Dus als er geen delers zijn kleiner dan $M$, dan zijn er ook geen groter dan $M$ (behalve de triviale delers $1$ en $N$ zelf natuurlijk, maar daar hebben we het hier niet over).

Fase 1: de gemakkelijke priemdelers

Als je de vorige delen uit de reeks deelbaarheid hebt gelezen zullen de volgende trucjes je bekend voor komen:

$\color{Green}2$ en $\color{Green}5$	Bekijk het eindcijfer. Is dat $0, 2, 4, 5, 6$ of $8$ dan heb je al een deler gevonden.
$\color{Green}3$	Tel alle cijfers op en kijk of de som deelbaar is door $3$.
$\color{Green}7$ en $\color{Green}{13}$	Als $abc$ deelbaar is door $7$ en/of $13$ dan is $(a - 1)(b + 1)(c - 1)$ ook deelbaar door $7$ en/of $13$.
$\color{Green}{11}$	Tel de cijfers van de even rangen op en trek er de cijfers van de oneven rangen vanaf. Is het resultaat deelbaar door $11$? Dan dit getal ook.

Fase 2: de andere priemgetallen

Stel we hebben een getal $N$ dat eindigt op $1, 3, 7$ of $9$. Onze volgende priemgetallen die we moeten testen zijn $17, 19, 23, 29, 31, \ldots$, ook allemaal getallen die eindigen op $1, 3, 7$ of $9$. Deze eindgetallen kan je opdelen in twee
groepen: $\{1, 9\}$ en $\{3, 7\}$. 

We gaan nu als volgt te werk: we gaan verder onze reeks priemgetallen af, van klein naar groot. Noem het priemgetal dat we als volgende willen testen $p$. Als het laatste cijfer van het getal $N$ en het priemgetal $p$ in dezelfde groep zitten, dan tel je $N$ en $p$ samen, of je maakt het verschil zodanig dat je op een veelvoud van $10$ uitkomt. Immers, $1 - 1 = 0$ of $9 + 1 = 10$ of $3 + 7 = 10$ enzovoort. 

Als het laatste cijfer van het getal $N$ en het priemgetal $p$ in de andere groep zitten, dan bereken je eerst $3 \times p$. Het eindcijfer van $N$ en van $3 \times p$ zitten dan wel in dezelfde groep. Dan tel je $N$ en $3 \times p$ samen, of je maakt het verschil zodanig dat je op een veelvoud van $10$ uitkomt. Dat veelvoud van $10$ deel je dan door $10$ en vervolgens ga je na of dat quotiënt $Q$ deelbaar is door $p$.

Is $Q$ deelbaar door $p$, dan heb je een deler van $N$ gevonden, dan is $N$ deelbaar door $p$. Zo niet, dan ga je verder met de volgende $p$ uit het lijstje priemgetallen. Dit herhaal je tot je je afgesproken bovengrens voor $p$ bereikt hebt. In dat geval heb je geen enkele deler gevonden en weet je dat je oorspronkelijke getal $N$ zelf een priemgetal is. 

Voorbeelden zeggen dikwijls meer dan uitleg. Laten we dit even toepassen op een paar zorgvuldig gekozen getallen.

VoOrbEeld N = 437

Ten eerste, hoever moeten we gaan? $20^2 = 400$, we moeten verder gaan dan $20$, maar niet veel verder, hoogstens tot $21$ schat ik. Het eerste priemgetal na $20$ is $23$ en diens kwadraat ligt duidelijk veel verder dan $437$. Als je toch twijfelt, ga je door tot $25$. $25^2 = 625$ dat is zeker groter. En dan nu delers testen.

$\color{Green}2$ en $\color{Green}5$: $437$ eindigt niet op $0, 2, 4, 5, 6$ of $8 \rightarrow$ niet deelbaar

$\color{Green}3$: $4 + 3 + 7 = 14  \rightarrow$ niet deelbaar

$\color{Green}7$ en $\color{Green}{13}$: $437 \rightarrow 073 \rightarrow$ niet deelbaar

$\color{Green}{11}$: $4 - 3 + 7 = 8 \rightarrow$ niet deelbaar

In veel gevallen zou je nu al een deler gevonden hebben. Vele getallen zijn immers deelbaar door één van de kleine priemgetallen.

Nu gaan we over op fase 2.

$\color{Green}{17}$:	$17$ en $437$ eindigen beide op $7$. Prima. $437 - 17 = 430 - 10 = 420$. $420/10 = 42$. $42/2 = 21$, niet deelbaar door $17 \rightarrow$ niet deelbaar
$\color{Green}{19}$:	$19$ en $437$ zitten in een verschillende groep. $3 \times 19 = 57$. $437 - 57 = 430 - 50 = 380$. $80/10 = 38$. $38/2 = 19$. Bingo!

$437$ is dus deelbaar door $19$ en na een beetje reken kom je er op uit dat $437/19 = 23$ en dus is de priemontbinding van $437$ gelijk aan $19 \times 23$.

Voorbeeld N = 4321

Voor het tweede voorbeeld nemen we een groter getal. Dit is niet geschikt voor beginners, maar het illustreert wel duidelijk de methode. Een gevorderde rekenaar kan dit wel aan! Bekijk eerst kwadraten die in de buurt komen. We zien dat $N$ bijna $100$ meer is dan $652$, omdat $662 - 652 = 131$ is $N$ dus kleiner dan $662$. We hoeven slechts het priemgetal $61$ als laatste te testen. Kortom, als $4321$ een priemgetal zou zijn, hebben we wel even te gaan. Maar we weten het nog niet.

$\color{Green}2$ en $\color{Green}5$: $4321$ eindigt niet op $0, 2, 4, 5, 6$ of $8 \rightarrow$ niet deelbaar.

$\color{Green}3$: $4 + 3 + 2 + 1 = 10 \rightarrow$ niet deelbaar 

$\color{Green}7$ en $\color{Green}{13}$: $4321 \rightarrow 3320 \rightarrow 1500 \rightarrow$ niet deelbaar.

$\color{Green}{11}$: $4 - 3 + 2 - 1 = 2 \rightarrow$ niet deelbaar.

Dat ging vlot.

$\color{Green}{17}$:	$7$ en $1$ zitten in de andere groep, dus berekenen we $3 \times 17 = 51$. $4321 - 51 = 4320 - 50 = 4270$. $4270/10 = 427$, $427 - 17 = 420 - 10 = 410$, niet deelbaar door $17$ ($41$ is een priemgetal). Of je kon ook opmerken dat $427$ deelbaar was door $7$. $427/7 = 61$ en dat is een priemgetal, dus zeker niet deelbaar door $17$. Zoals je ziet zijn er verschillende manieren om deelbaarheid te vinden.
$\color{Green}{19}$:	$9$ en $1$ zitten wel in dezelfde groep. $4321 + 19 = 4320 + 20 = 4340$, $4340/10 = 434$, $434/2 = 217$. Idee, $21$ en $7$ zijn beide deelbaar door $7$. Dat is een meevaller $217/7 = 31$, niet deelbaar door $19$.
$\color{Green}{23}$:	$3 \times 23 = 69$, $4321 + 69 = 4320 + 70 = 4390 \rightarrow 439 \rightarrow 439 - 69 = 430 - 60 = 370$, niet deelbaar.
$\color{Green}{29}$:	$4321 + 29 = 4320 + 30 = 4350 \rightarrow 435 \rightarrow 87$, deelbaar door $3$. $87/3 = (90 - 3)/3 = (30 - 1) = 29$. Dit is deelbaar door $29$, dus ons oorspronkelijke getal is ook deelbaar door $29$.

 

We hebben een deler gevonden. Vervolgens zouden we $4321$ uit het hoofd moeten delen door $29$ en dan met het quotiënt verder gaan. Om uit het hoofd te delen kunnen we in bovenstaande berekening op onze stappen terugkeren. $87 = 3 \times 29$, $435 = 5 \times 87 = 15 \times 29 = 4350 = 10 \times 435 = 150 \times 29$, $4321 = 4350 - 29 = (150 - 1) \times 29 = 149 \times 29$. Dus $4321/29 = 149$ en dus geldt er: $4321 = 29 \times 149$. 

En dan nu verder delers zoeken van ons oorspronkelijke getal. We zoeken dus verdere delers van $149$. $149$ is kleiner dan $400$ dus een deler zou kleiner moeten zijn dan $20$, maar die delers hebben we allemaal al geprobeerd. De ontbinding van $4321$ in priemfactoren is dus $29 \times 149$.

 

Opgave 1 Probeer van de volgende getallen uit je hoofd de priemontbinding te vinden: $209$     $529$     $667$ Opgave 2 Voor grotere getallen merken we op dat deze vaak herhalende priemgetallen in hun priemontbinding hebben. Een voorbeeld hiervan is bijvoorbeeld: $4096$.  De priemontbinding van $4096$ is namelijk: $2 \times 2 \times 2 \cdots \times 2$ en dat $12$ keer, oftewel $2^{12}$. Probeer door gebruik te maken van de regels hierboven van de volgende getallen ook priemfactorisaties te maken. Hiervoor mag je een kladpapiertje gebruiken ook al is het nog beter om het uit je hoofd te doen! $5168$    $6859$    $12\ 167$ Opgave 3 In de wiskunde betekent een uitroepteken toch iets heel anders dan het getal gewoon harder noemen. Het uitroepteken in de wiskunde staat voor faculteit. Wat dit betekent is het beste te illustreren met een paar voorbeelden.  $3! = 3 \times 2 \times 1$ en $5! = 5 \times 4 \times 3 \times 2 \times 1$.  Ik denk dat hiermee wel duidelijk is wat "!" precies doet. Bereken van de volgende getallen de priemontbinding: $6!$    $1! + 2! + 3! + 4! + 5!$    $3628800$ Bonus Voor de echte slimmeriken onder jullie is de bonusvraag: Voor welke $x$ geldt het volgende: $x! = 3628800$?