100'den küçük bir sayının asal olduğunu test etme

Question

Sav:
$n>1$ bileşik bir tam sayı ise $n$ tam sayısının $\sqrt n$ değerinden küçük eşit bir asal böleni vardır. (İspatı cevaplarda verilecek.)

Çıkarım (İlkel asallık testi):
$n>1$  bir tam sayı olmak üzere $n$ tam sayısının $\sqrt n$ değerinden küçük bir asal böleni yoksa $n$ asal bir sayıdır.

100'den küçük asallar için:

$n$ tam sayısı $100$ değerinden küçük ise $$\sqrt n\le \sqrt{100} =10$$ olur. Bu nedenle $n$ sayısının asallığı için $10$ değerinden küçük asallara bakmamız yeterli. Bu asallar ise $$2,\ 3, \ 5,\ 7$$ değerleridir.

Bazı $n$ değerleri için hepsine bakmaya elbet gerek yok, örneğin $43$ için $7$ asalına bölünebilirliğini kontrol etmeye ihtiyaç duymayız. 

Örnekler:

87 tam sayısı 
$2$ ile bölündüğünde $1$ kalanını verir,
$3$ ile tam bölünür, asal değildir.

89 tam sayısı 
$2$ ile bölündüğünde $1$ kalanını verir,
$3$ ile bölündüğünde $2$ kalanını verir,
$5$ ile bölündüğünde $4$ kalanını verir,
$7$ ile bölündüğünde $5$ kalanını verir.
Bu nedenle $89$ asaldır.

91 tam sayısı 
$2$ ile bölündüğünde $1$ kalanını verir,
$3$ ile bölündüğünde $1$ kalanını verir,
$5$ ile bölündüğünde $1$ kalanını verir,
$7$ ile tam bölünür, asal değildir.

Answer 1

Bileşik sayılar:
$n>1$ asal olmayan bir pozitif tam sayı ise $$n=a\cdot b$$ olacak şekilde $a,b>1$ tam sayıları vardır.  

Çarpan sıralaması:
Bu çarpanları için $a\le b$ olacak şekilde yazabiliriz. 

Kök ile ilişkisi:
Bu durumda elimizde $$a^2\ = \ a\cdot a \ \le \ a \cdot b\ = \ n$$ eşitsizliği olur.

Kök fonksiyonu artan bir fonksiyon olduğundan $$a\le \sqrt n$$ eşitsizliği sağlanır.

Asal bölenlerle ilişkilerdirme:
$a>1$ bir pozitif tam sayı olduğundan bir asal $p$ tam böleni vardır. Dolayısıyla $$p\le a\le \sqrt n$$ eşitsizliği sağlanır.

$p$ tam böler $a$ ve $a$ tam böler $n$ olduğundan, tam bölmenin geçişgenliği gereği, $p$ asalı $n$ bileşik tam sayını böler.