Asallık Testi
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.
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.
İSPATI GÖSTER
Öncelikle bir \( 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ından küçük bileşik sayıların \( A \) sayısından küçük asal sayıları birer çarpan olarak içeriyor olmasıdır, dolayısıyla \( A \) sayısı kendisinden küçük bir bileşik sayıya bölünüyorsa kendisinden küçük ve kendisini bölen bir asal sayı mutlaka vardır.
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 yazılabilir.
\( 1 \lt m \lt A, \quad 1 \lt n \lt A \) olmak üzere,
\( A = mn \)
Ç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.
\( mn \gt \sqrt{A}\sqrt{A} = 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. Bu şekildeki her çarpan için \( A \) sayısının kareköküne eşit ya da daha büyük bir çarpanı da olacaktır.
347 sayısının asal olup olmadığını bulmak için en az kaç tam sayıya kalansız bölünüp bölünmediği kontrol edilmelidir?
Çözümü Göster347 sayısının karekökünden küçük olan asal sayılara bölünebilirliğini kontrol etmemiz bu sayının asal olup olmadığını bulmak için yeterlidir.
\( \sqrt{347} \lt 19 \) olduğu için, 347'nin \( \{2, 3, 5, 7, 11, 13, 17\} \) sayılarına bölünebilirliği kontrol etmemiz yeterlidir.
Buna göre 347'nin asal sayı olup olmadığını bulmak için en az 7 tam sayı ile bölünebilirliğini kontrol etmeliyiz.