Primtal och faktorer

Om  A är delbart med ett tal k så betyder det att A=k*c. Både k och c kan inte vara större än roten ur A, för då skulle k*c vara större än roten ur A i kvadrat, alltså större än A. Alltså vet vi att det ena av k och c är mindre än roten ur A, så om vi kontrollerat alla tal upp till roten ur A, och inte hittat någon delare till A, så vet vi att A är ett primtal.

Så frågan är hur många siffror roten ur A har, och det är det de har ränat ut till hälften så många som A.

Tänk dig att du har ett tal n (till exempel 221) och vill veta om det är ett primtal. Då behöver du bara kolla primtal som är mindre än $\sqrt{n}$ (dvs upp till 13, eftersom $\sqrt{221}\approx 14,9$ och 14 inte är ett primtal).

Förklaringen är följande. Anta att n är jämt delbart med m. Då finns ett heltal k sådant att $\frac{n}{m}=k$

Men då är mk=n, och då kan inte både m och k vara större än $\sqrt{n}$, för då skulle ju mk>n. Alltså är det så att om man kollar alla primtal upp till $\sqrt{n}$ och n inte varit delbart med någon av dem behöver man inte kolla längre.

Det är den principen boken använder, men för att uppskatta upp till hur många siffror man behöver kolla.