Hvordan finne primtall

Kan man finne ut om 589 er et primtall på andre måter enn å prøve og feile? Vet at 589 ikke er et primtall fordi$19\cdot 31=589$, men finnes det noen systematisk måte å finne ut av dette på?

Man bruker ofte en systematisk prøve-og-feile-strategi, som i denne sammenhengen kalles å sile, på engelsk 'sieve'. Vi går fram som følger. Det største heltallet som er mindre enn roten av 589 er 24. Primtallene 2, 3, 5, 7, 11, 13, 17, 19 og 23 er dermed de eneste primtallene som er mindre enn roten av 589. Hvis ingen av disse hadde gått opp i 589 hadde du hatt et primtall (Og her ser du hvorfor metoden ikke virker godt på store tall - til slutt er det mange primtall som er mindre enn kvadratroten). Her gikk 19 opp i 589, så det er ikke et primtall, som du sier.

En annen, litt mer teoretisk måte, er å bruke Fermats lille sats. Den sier at om $p$ er et primtall som ikke deler $a$ er $a^{p-1}=1\hspace{0.17em}(\mathrm{mod}\hspace{0.17em}p)$. En metode basert på denne formelen går raskere på datamaskin. Den kan ikke vise at et tall er et primtall, men om dette ikke er oppfylt kan ikke tallet være et primtall.