] >
De hoofdstelling van de rekenkunde zegt dat natuurlijke getallen een eenduidige priemfactorontbinding hebben. Zo’n priemfactorontbinding zegt veel over het getal. Wil je er wat aan hebben dan moet je zo’n ontbinding wel kunnen vinden. Voor grote getallen is dat moeilijk en op dat feit berusten toepassingen in de cryptografie, zie paragraaf 13.5. Er zijn snelle algoritmen waarmee geconstateerd kan worden dat een getal samengesteld is. Drie van zulke testen worden in paragraaf 13.2 behandeld. Met deze testen is met zeer grote zekerheid te zeggen of een getal priem is. Ze leveren er geen wiskundig bewijs van. In paragraaf 13.3 geven we één test die wel zekerheid biedt. Sinds de jaren 70 van de vorige eeuw zijn er steeds meer en steeds betere algoritmen bedacht voor het vinden van factoren van getallen. Omdat het feitelijke ontbinden van een getal veel moeilijker is dan het constateren dat het samengesteld is, zijn er uiteraard getallen, waarvan we weten dat ze samengesteld zijn, maar waar we niet één priemfactor van kennen. Een voorbeeld daarvan is , het 20ste Fermatgetal. We beginnen met eenvoudige technieken die al voor de jaartelling gebruikt werden.