Bir \( A \) pozitif tam sayısının asal olup olmadığını bulmak için sayının kendisinden küçük tüm pozitif tam sayılara bölünebilirliğini kontrol etmemize gerek kalmadan, sadece \( 1 \lt p \le \sqrt{A} \) koşulunu sağlayan asal sayılara bölünebilirliğini kontrol etmemiz yeterlidir. \( A \) sayısı bu aralıktaki asal sayılardan en az birine kalansız bölünüyorsa asal değildir.
ÖRNEK:
\( 191 \) sayısının bir asal sayı olup olmadığını bulmaya çalışalım ve önce sayının karekökünü alalım.
\( \sqrt{191} = 13,8... \)
\( 1 \lt p \le 13,8 \) koşulunu sağlayan asal sayılar kümesi \( P \) olmak üzere,
\( P = \{ 2, 3, 5, 7, 11, 13 \} \)
\( 191 \) \( P \) kümesinin elemanlarından en az birine kalansız bölünüyorsa asal değildir.
\( 191 \bmod{2} = 1 \Longrightarrow \) 2'ye tam bölünmez.
\( 191 \bmod{3} = 2 \Longrightarrow \) 3'e tam bölünmez.
\( 191 \bmod{5} = 1 \Longrightarrow \) 5'e tam bölünmez.
\( 191 \bmod{7} = 2 \Longrightarrow \) 7'ye tam bölünmez.
\( 191 \bmod{11} = 4 \Longrightarrow \) 11'e tam bölünmez.
\( 191 \bmod{13} = 9 \Longrightarrow \) 13'e tam bölünmez.
\( 191 \) sayısı bu asal sayılardan hiçbirine tam bölünmediği için bir asal sayı olduğu sonucuna varabiliriz. Bu yöntemi kullanarak 191'in sadece 6 sayıya bölünebilirliğini kontrol ederek asal olup olmadığını belirlemiş olduk.
Öncelikle \( A \) sayısının asallığını belirlemek için sayının kendisinden küçük tüm tam sayılar yerine sadece kendisinden küçük asal sayılara bölünebilirliğini kontrol etmemiz yeterlidir.
Bunun sebebi, \( A \) sayısının asal olmadığını gösterebilmek için sayıyı aşağıdaki gibi kendisinden küçük bir ya da daha fazla asal sayının çarpımı şeklinde yazabiliyor olmamız gerekir, dolayısıyla \( A \) sayısını kalansız bölen kendisinden küçük en az bir asal sayı bulmamız yeterlidir.
\( A = x^a \cdot y^b \cdot z^c \)
Bu yöntemin diğer bir kuralı \( A \) sayısından küçük tüm asal sayılar yerine sadece aşağıdaki aralıktaki asal sayıları kontrol etmemizin yeterli olmasıdır.
\( 1 \lt p \le \sqrt{A} \)
\( A \) sayısı bileşik ise, aşağıdaki gibi iki sayının çarpımı şeklinde yazabiliriz.
\( 1 \lt m \lt A, \quad 1 \lt n \lt A \) olmak üzere,
\( A = m \cdot n \)
Çarpanların her ikisinin de \( A \)'nın karekökünden büyük olduğunu varsayalım.
\( m \gt \sqrt{A} \)
\( n \gt \sqrt{A} \)
Bu durum iki sayının çarpımının \( A \)'dan büyük olması anlamına gelir, bu da yukarıdaki eşitliğe aykırıdır.
\( m \cdot n \gt \sqrt{A} \cdot \sqrt{A} \)
\( m \cdot n \gt A \)
Buna göre, \( A \) sayısı bir bileşik sayı ise çarpanlarından en az biri kareköküne eşit ya da daha küçük olmalıdır. Dolayısıyla \( A \) sayısının kareköküne eşit ya da daha büyük her çarpanı için kareköküne eşit ya da daha küçük bir çarpanı da olacaktır.