MAT106U-MATEMATİK-II
Ünite 6: Asal Sayılar ve Modüler Aritmetik
Asal Sayılar Ve Modüler Aritmetik
Bu ünitede, ilk kısımda asal sayılar, birleşik sayılar tanımlanarak, sayıların hangi durumlarda asal ya da birleşik olduğu incelenmiştir. En büyük ortak bölen (Ebob) ve en küçük ortak kat (Ekok) kavramları ayrıntılı örnekler ile anlatılmıştır. İkinci kısımda ise, modüler aritmetik kavramı ve denkliklerin belirli özellikleri üzerinde durularak ayrıntılı örnekler verilmiştir. Son kısımda ise bir bilinmeyenli doğrusal denklemler anlatılmıştır.
Bir doğal sayı, farklı şekillerde çarpanlarına ayrılabiliyorsa bu sayılara bileşik sayılar, ayrılamıyorsa asal sayılar denir. 12 bir bileşik sayıdır. Çünkü: 3.4, 2.6 veya 1.12 şeklinde yazılabilir. 7 bir asal sayıdır. Çünkü sadece 1.7 şeklinde yazılabilir.
1’den büyük olan ve sadece 1’e ve kendisine bölünen doğal sayılara asal sayı denir. İlk 10 asal sayı: 2, 3, 5, 7, 11, 13, 17, 19, 23 ve 29 şeklinde yazılabilir.
1 < a < n ve 1 < b < n olmak üzere n = a.b şeklindeki doğal sayılara bileşik sayı denir. Verilen bir tamsayıyı bölen asal sayıya asal bölen ya da asal çarpan denir.
24 = 2.2.2.3= 23.3 şeklinde yazılarak 24 sayısı asal
çarpanlarına ayrılır. Bunlar 2 ve 3’dür.
Aritmetiğin Temel Teoremi: Her n >1 doğal sayısı asal sayıların çarpımı şeklinde sıra değişikliği hariç tek türlü yazılabilir. Bu teorem şifreleme tekniklerinde kullanıldığı için büyük bir önem taşımaktadır.
a ve b gibi iki doğal sayıdan her ikisini de bölen doğal sayıların en büyük olanına, bu sayıların en büyük ortak böleni denir ve ebob(a,b) şeklinde gösterilir.
a ve b gibi iki doğal sayıdan her ikisine de bölünen doğal sayıların en küçük olanına, bu sayıların en küçük ortak katı denir ve ekok(a,b) şeklinde gösterilir.
m ve n gibi iki doğal sayının en büyük ortak böleni ve en küçük ortak katı bulunurken aşağıdaki teknikler uygulanır.
1. m ve n asal çarpanlarına ayrılır. 2. Ortak olan asal çarpanlardan, üsleri en küçük olanlarının çarpımı bu sayıların en büyük ortak bölenidir.(Ortak asal çarpan yoksa en büyük ortak bölen 1’dir.) 3. Ortak olan asal çarpanlardan üsleri en büyük olanlar ile ortak olmayanların hepsinin çarpımı bu sayıların en küçük ortak katıdır.
a ve b doğal sayılar olmak üzere ebob(a, b) = 1 ise a ve b sayılarına aralarında asaldır denir. 6 ile 11 sayılarının en büyük ortak böleni 1 olduğu için 6 ile 11 aralarında asaldır. 8 ve 12 düşünüldüğünde bu sayıların en büyük ortak böleni 4 olduğu için aralarında asal değildir.
Asal mı Değil mi?
Eratosthenes Kalburu: Çok büyük olmayan sayılara uygulanılan bir metotdur.1 den 100 kadar olan asal sayılar
bulunmak istendiğinde bu metot kullanılabilir. 𝑛 sayısına kadar olan asal sayılar bulunmak istediğinde: 1 den n’e kadar bütün sayılar bir tablo şeklinde yazılır. Daha sonra 2’nin katları elenir. Geriye kalan sayıların ilki 3 olduğu için daha sonra 3’ün katları elenir. Daha sonra geriye kalan ilk sayı 5 olduğu için 5’in katları elenir ve bu şekilde devam edilir. Geriye kalan sayıların aranan asal sayılar olduğu görülür. Bu teknik Eratosthenes tarafından bulunduğu için bu ismi almıştır.
Eratosthenes (M.Ö. 276 − 194). Matematik ve doğa bilimlerine büyük katkılar sağlamıştır. Yerkürenin çevresini ilk olarak hesaplayan kişidir. Aynı zamanda güneşin dünyadan uzaklığını hesaplamış ve o zaman bilinen dünyanın haritasını çıkarmıştır.
Asal sayıların bir başka bulunuş şekli ise şöyledir: 𝑛 bir bileşik sayı ise
𝑛 = 𝑎. 𝑏
olur. Burada 1 < 𝑎 ≤ 𝑏 < 𝑛 olduğunu varsayarız ve
𝑎. 𝑎 ≤ 𝑎. 𝑏 = 𝑛 𝑣𝑒 𝑎 ≤ 𝑛
elde ederiz. Bu nedenle 𝑛’in 𝑛’yi geçmeyen bir asal böleni vardır.
Kaç Tane Asal Sayı Vardır?
M.Ö 300 civarında, Öklid asal sayıların sonsuz olduğunu ispat etmiştir. Şu ana kadar bilinen en büyük basamaklı asal sayı Los Angeles California Üniversitesi (UCLA) matematik bölümünden Edson Smith ve ekibi tarafından 2008 yılında bulunmuştur. Bu sayı 12978189 basamaklıdır.
Asal Sayılar Nerede Kullanılır?
Asal sayılar birçok alanda oldukça faydalı şekilde kullanılmaktadır. En çok kullanıldığı alanlardan biri internet güvenliğidir. Önemli verilerin şifrelenmesi konusunda çok önemlidir. Bu doğrultuda, şifreleme tekniklerini güçlendirmek amacıyla asallar hakkında araştırmaları teşvik eden bir vakıf bulunmaktadır. 2005 yılında, Almanya’da bir göz uzmanı olan ve matematikle amatör olarak ilgilenen Dr. Martin Nowak, kişisel bilgisayarında 50 gün çalışarak 7 milyon 816 bin 230 rakamdan oluşan ve 2!"#$%#"& − 1
olarak ifade edilen bir asal sayı buldu. Bu sayı, Mersenne asal sayıları olarak bilinen gruba ait 42. sayıdır.
Modüler Aritmetik
Bir m tam sayısını sıfırdan farklı bir n doğal sayısına böldüğümüzde 0 ≤ 𝑟 < 𝑛 olmak üzere
𝑚 = 𝑘 · 𝑛 + 𝑟
koşulunu sağlayan r tam sayısına kalan denir.
Adına modül diyeceğimiz özel bir n doğal sayısı seçerek, her tam sayıyı n’ye bölümünden kalan sayı ile yer değiştirdiğimiz bu tekniğe Modüler Aritmetik adı verilir. a ve b tam sayıları, sıfırdan farklı pozitif bir n tam sayısı tarafından bölündüğünde aynı kalanı veriyorsa bu sayılara n modülüne göre denktir ya da kısaca mod n’ye göre denktir deriz ve
𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) ile gösteririz.
17, 2.7+3 şeklinde yazılabilir. Yani 17, 7’ye bölündüğünde bölümü 2, kalanı 3’dür. Ve 17≡ 3 (mod 7) şeklinde yazılabilir.
a, b, n tam sayılar ve n > 0 olmak üzere a ve b sayılarının n’ye bölümünden kalanlar aynı ise a ve b sayıları n modülüne göre denktir denir ve 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) şeklinde gösterilir. 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) olması demek 𝑎 −b sayısının n sayısı ile bölünmesi demektir.
3 ≡ 23 (𝑚𝑜𝑑 5) biliniyor. Verilen tanım kullanılarak,
23 − 3 = 20 olup 5 sayısı 20 sayısını tam olarak böldüğünden dolayı 3 ≡ 23 (𝑚𝑜𝑑 5) denkliği sağlanmış olur.
Denklik kavramı yardımıyla sayıları sınıflara ayırabiliriz. Herhangi iki çift sayının farkı çift olup 2 ile bölünebildiğinden çift sayılar 𝑚𝑜𝑑 2 ’ye göre denktir. Benzer şekilde, herhangi iki tek sayının farkı da çift olup 2 ile bölünebildiğinden tek sayılar da 𝑚𝑜𝑑 2’ye göre denktir. Ama bir çift sayı ile bir tek sayı 𝑚𝑜𝑑 2’ye göre denk değillerdir. Çünkü, farkları bir tek sayı olup 2 ile bölünmez. Böylece 𝑚𝑜𝑑 2’ye göre sayılar, tek sayılar ve çift sayılar olmak üzere iki sınıfa ayrılabilir.
Denkliklerin üç adet temel özelliği vardır. n bir doğal sayı, a, b ve c tam sayılar olmak üzere, bunlar şöyle ifade edilir:
1. Simetri özelliği: 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) 𝑖𝑙𝑒 𝑏 ≡ 𝑎 (𝑚𝑜𝑑 𝑛) denktir. 3 ≡ 23 (𝑚𝑜𝑑 5) 𝑖𝑙𝑒 23 ≡ 3 (𝑚𝑜𝑑 5) aynı şeylerdir.
2. Yansıma özelliği: 𝑎 ≡ 𝑎 (𝑚𝑜𝑑 𝑛)
3 ≡ 3 (𝑚𝑜𝑑 4)’tür. Çünkü 4 sayısı 3 − 3 = 0
sayısını böler.
3. Geçişme özelliği:
𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) 𝑣𝑒 𝑏 ≡ 𝑐 (𝑚𝑜𝑑 𝑛) 𝑖𝑠𝑒 𝑎 ≡ 𝑐 (𝑚𝑜𝑑 𝑛)
2 ≡ 12 (𝑚𝑜𝑑 5) 𝑣𝑒 12 ≡ 22 (𝑚𝑜𝑑 5) olup geçişme özelliğine göre 2 ≡ 22 (𝑚𝑜𝑑 5 )’tir. Gerçekten, 22−2 farkı 5 ile bölünür.
Denklikler toplama, çıkarma ve çarpma işlemleri altında korunur ve bu özellikler şöyledir: a, a′ , b, b′ ∈ Z ve n bir doğal sayı olmak üzere,
1. Toplama işlemleri: 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 𝑣𝑒 𝑎! ≡ 𝑏! 𝑚𝑜𝑑 𝑛 ! 𝑖𝑠𝑒 𝑎 + 𝑎 ≡ 𝑏 + 𝑏′ (𝑚𝑜𝑑 𝑛)
2. Çıkarma işlemleri:
𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 𝑣𝑒 𝑎! ≡ 𝑏! 𝑚𝑜𝑑 𝑛 𝑖𝑠𝑒
𝑎 − 𝑎′ ≡ 𝑏 − 𝑏′ (𝑚𝑜𝑑 𝑛)
3. Çarpma işlemleri: 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 𝑣𝑒 𝑎! ≡ 𝑏! 𝑚𝑜𝑑 𝑛 𝑖𝑠𝑒
𝑎 · 𝑎′ ≡ 𝑏 · 𝑏′ (𝑚𝑜𝑑 𝑛)
Bu özelliklere göre, bir denkliğin her iki tarafını bir tam sayı ile toplar, çıkarır veya çarparsak denkliğin bozulmayacağı görülür. a, b, k tam sayılar ve n bir doğal sayı olmak üzere 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) olsun. Bu durumda;
i. 𝑎 + 𝑘 ≡ 𝑏 + 𝑘 (𝑚𝑜𝑑 𝑛) ii. 𝑎 − 𝑘 ≡ 𝑏 − 𝑘 (𝑚𝑜𝑑 𝑛) iii. 𝑎 · 𝑘 ≡ 𝑏 · 𝑘 (𝑚𝑜𝑑 𝑛)
bulunur. Ancak bu bölme işlemi için sağlanmaz.
Bölme işlemi yapabilmek için
a, b, k, n tam sayılar ve n > 0 olmak üzere
𝑎 · 𝑘 ≡ 𝑏 · 𝑘 (𝑚𝑜𝑑 𝑛)
olsun. Eğer 𝑒𝑏𝑜𝑏(𝑘, 𝑛) = 1 ise 𝑘 ile her iki tarafı böldüğümüzde 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) olarak buluruz.
Modüler aritmetik kavramı birçok alanda kullanılır. Bugün günlerden Çarşamba ise 40 gün sonra günlerden ne olur?
Bu sorunun çözümünde bugün günlerden Çarşamba ise 7 gün sonra da 14 gün sonrada 21 gün sonra da Çarşamba olacaktır. Bu mantıkla 40’ın mod 7’deki karşılığı bulunur.
40=5.7+5 şeklinde yazılabilir. Yani Çarşamba’dan itibaren 5 gün sayacağız. O da bir Perşembe, iki Cuma, üç Cumartesi, dört Pazar dersek, beş Pazartesi olur. Yani 40 gün sonra günlerden Pazartesi’dir.
Bir Bilinmeyenli Doğrusal Denklikler
Birinci dereceden bir bilinmeyenli denklemlere benzer olarak, x bilinmeyen, a ve b tam sayılar olmak üzere
𝑎 · 𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑛)
şeklindeki bir denkliğe bir bilinmeyenli doğrusal denklik denir. Bu denkliği sağlayan x bilinmeyenine de bu doğrusal denkliğin çözümü denir. Eğer 𝑥 ! = 𝑥! sayısı
𝑎 · 𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑛)
Denkliğinin bir çözümü ve 𝑥 ! = 𝑥! (𝑚𝑜𝑑 𝑛) ise
𝑎 · 𝑥! ≡ 𝑎 · 𝑥! ≡ 𝑏 (𝑚𝑜𝑑 𝑛)
olduğundan 𝑥! de bu denkliğin bir çözümüdür. Yani,
𝑎 · 𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑛)
şeklindeki bir denkliğin bir çözümü mevcut ve𝑥! olsun. Bu durumda 𝑥!’a 𝑚𝑜𝑑 𝑛’ye göre denk olan her tam sayı da bu denkliğin bir çözümüdür.
Bir bilinmeyenli doğrusal denkliklerin çözümleri olmayabilir. 𝑎 · 𝑥 ≡ 𝑏 𝑚𝑜𝑑 𝑛 şeklindeki bir doğrusal denkliğin çözümünün olması için gerek ve yeter koşul 𝑒𝑏𝑜𝑏(𝑎, 𝑛) sayısının b sayısını bölmesidir.