MAT2033 · 7. hafta · divisibility, modular arithmetic, primes

Bölünebilme, modüler aritmetik ve asal sayılar

a | b, bölme algoritması (div ve mod), kongrüans, asal çarpanlara ayırma, EBOB/EKOK ve Öklid algoritması. Kriptografi haftasının temeli, final konusu.

dividesdivision algorithmquotientremainderdivmodcongruence modulo mprimecompositeFundamental Theorem of Arithmeticgreatest common divisor (gcd)least common multiple (lcm)Euclidean algorithmBezout's identityrelatively prime

Bu hafta sayılar teorisine giriyoruz. Vizede yok, final konusu. Ama sonraki hafta (kriptografi, RSA) tamamen bunun üstüne kurulu: EBOB, mod alma ve Öklid algoritması orada her soruda lazım. Altın kurallar:

$a \mid b$ bir önermedir, bir sayı değil. “3 divides 12” doğru ya da yanlış olur; $12/3 = 4$ ise bir sayıdır.
Kalan asla negatif olmaz: $0 \le r < d$ . Negatif sayıda bölüm bir aşağı iner.
mod m’de toplama ve çarpmadan önce sayıları küçült. Büyük çarpımı hiç yapmana gerek yok.
EBOB için Öklid: $\gcd(a, b) = \gcd(b, a \bmod b)$ , kalan 0 olana kadar.
İspat sorusunda tanımı yaz: $a \mid b$ ise $b = ak$ . İspatın yarısı bu satır.

Bölünebilme (divisibility)

$a \ne 0$ olsun. a divides b ( $a \mid b$ ) demek, $b = ac$ olacak bir tam sayı $c$ var demek. $a$ ‘ya $b$ ‘nin böleni (factor, divisor), $b$ ‘ye $a$ ‘nın katı (multiple) denir.

Örnekler: $4 \mid 28$ çünkü $28 = 4 \cdot 7$ . $5 \nmid 28$ çünkü $28/5 = 5.6$ tam sayı değil. $7 \mid 0$ çünkü $0 = 7 \cdot 0$ .

Temel özellikler ( $a, b, c$ tam sayı):

Özellik	Anlamı
$a \mid b$ ve $a \mid c$ ise $a \mid (b + c)$	Ortak bölen toplamı da böler
$a \mid b$ ise her $c$ için $a \mid bc$	Bölen, katı da böler
$a \mid b$ ve $b \mid c$ ise $a \mid c$	Geçişlilik (transitivity)
$a \mid b$ ve $a \mid c$ ise $a \mid (mb + nc)$	Her doğrusal kombinasyonu böler

Tam yazılmış ispat

Geçişlilik özelliğini sınavda yazacağın gibi ispatlayalım.

Claim. If a | b and b | c, then a | c.
Proof. Suppose a | b and b | c. Then there are integers k and l
such that b = ak and c = bl.
Substituting, c = bl = (ak)l = a(kl).
Since kl is an integer, a | c by the definition of divisibility. ∎

Dikkat: iki ayrı bölünebilme için iki ayrı harf ( $k$ ve $l$ ) kullandık. Aynı harfi kullanmak ” $b$ ile $c$ aynı katsayıyla” demek olur, ispat bozulur.

Bölme algoritması (division algorithm)

Her tam sayı $a$ ve pozitif tam sayı $d$ için tek bir $q$ ve $r$ vardır:

$a = dq + r, \qquad 0 \le r < d.$

$q = a \textbf{ div } d$ (bölüm, quotient), $r = a \bmod d$ (kalan, remainder).

101 = 7 * 14 + 3      ->  101 div 7 = 14,  101 mod 7 = 3
-23 = 6 * (-4) + 1    ->  -23 div 6 = -4,  -23 mod 6 = 1

TUZAK · negatif sayının kalanı. $-23 = 6 \cdot (-3) - 5$ yazıp kalanı $-5$ demek yanlış: kalan $0 \le r < 6$ olmalı. Bölümü bir aşağı indir ( $-4$ ), kalan pozitif çıkar ( $1$ ). Java’nın % operatörü burada $-5$ verir, matematikteki mod ise $1$ .

Kongrüans ve modüler aritmetik

$a \equiv b \pmod m$ (a is congruent to b modulo m) demek $m \mid (a - b)$ demektir. Aynı şey: $a$ ile $b$ ‘nin $m$ ‘ye bölümünden kalanlar aynı.

Örnek: $38 \equiv 14 \pmod{12}$ , çünkü $38 - 14 = 24 = 12 \cdot 2$ . Saat 38. saatte de 14. saatte de 2’yi gösterir.

Kurallar: $a \equiv b$ ve $c \equiv d \pmod m$ ise

$a + c \equiv b + d \pmod m, \qquad ac \equiv bd \pmod m.$

Bu yüzden büyük ifadeleri hesaplarken önce her parçayı küçültürsün:

(17 * 29 + 8) mod 5
17 mod 5 = 2,  29 mod 5 = 4,  8 mod 5 = 3
2 * 4 + 3 = 11,  11 mod 5 = 1
Kontrol: 17 * 29 + 8 = 501 = 5 * 100 + 1

İPUCU · büyük kuvvetler. $a^n \bmod m$ sorusunda önce $a^k \equiv 1$ olan küçük bir $k$ ara. Bulursan $n$ ‘yi $k$ ‘ya böl, kalan kuvveti hesapla. $k$ yoksa kriptografi haftasındaki hızlı üs alma (repeated squaring) yöntemini kullan.

Asal sayılar (primes)

$p > 1$ ve tek pozitif bölenleri $1$ ile $p$ ise $p$ asaldır (prime). 1’den büyük asal olmayan sayı bileşiktir (composite). 1 ne asal ne bileşik.

Aritmetiğin temel teoremi (Fundamental Theorem of Arithmetic): 1’den büyük her tam sayı, sıralama dışında tek bir biçimde asalların çarpımı olarak yazılır. Örnek: $600 = 2^3 \cdot 3 \cdot 5^2$ .

Deneme bölmesi (trial division): $n$ bileşikse $\sqrt{n}$ ‘den küçük-eşit bir asal böleni vardır. Sebebi: $n = ab$ ve ikisi de $\sqrt{n}$ ‘den büyük olsaydı $ab > n$ olurdu. Bu yüzden 97’nin asal olduğunu göstermek için sadece 2, 3, 5, 7’yi denemek yeter ( $\sqrt{97} \approx 9.8$ ). Hiçbiri bölmez, 97 asal.

Sonsuz tane asal var (Euclid). Kısa ispat fikri: sonlu olsun, $p_1, \dots, p_n$ . $Q = p_1 p_2 \cdots p_n + 1$ sayısı hiçbir $p_i$ ‘ye bölünmez (kalan hep 1). Ama $Q$ ‘nun bir asal böleni olmalı. Listede olmayan bir asal çıktı: çelişki.

EBOB ve EKOK (gcd ve lcm)

$\gcd(a, b)$ : ikisini de bölen en büyük tam sayı. $\operatorname{lcm}(a, b)$ : ikisinin de böldüğü en küçük pozitif tam sayı. $\gcd(a, b) = 1$ ise $a$ ve $b$ aralarında asaldır (relatively prime).

Çarpanlara ayırma ile: EBOB için her asalın küçük üssü, EKOK için büyük üssü. Ve her zaman

$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab.$

Örnek: $\gcd(12, 18) = 6$ , $\operatorname{lcm}(12, 18) = 36$ , $6 \cdot 36 = 216 = 12 \cdot 18$ .

Öklid algoritması (Euclidean algorithm)

Büyük sayılarda çarpanlara ayırmak zor. Öklid algoritması şu gerçeğe dayanır: $a = bq + r$ ise $\gcd(a, b) = \gcd(b, r)$ . Kalan sıfır olana kadar böl; sıfırdan önceki son kalan EBOB’dur.

gcd(2024, 748)
2024 = 2 * 748 + 528
 748 = 1 * 528 + 220
 528 = 2 * 220 + 88
 220 = 2 * 88  + 44
  88 = 2 * 44  + 0     ->  gcd = 44
lcm = 2024 * 748 / 44 = 34408

Bezout özdeşliği (Bezout’s identity)

$\gcd(a, b) = sa + tb$ olacak tam sayılar $s, t$ her zaman vardır. Bulmak için Öklid adımlarını geriye doğru yerine koyarsın:

44 = 220 - 2*88
   = 220 - 2*(528 - 2*220)        = 5*220 - 2*528
   = 5*(748 - 528) - 2*528        = 5*748 - 7*528
   = 5*748 - 7*(2024 - 2*748)     = 19*748 - 7*2024
s = -7, t = 19.  Kontrol: -14168 + 14212 = 44

Bu hesap gelecek hafta mod tersini (modular inverse) bulmanın tam yöntemi olacak. Burada iyice otur.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
$a \mid b$ ile $a / b$ aynı şey	$a \mid b$ önerme (T/F), $a/b$ sayı
$-23 \bmod 6 = -5$	Kalan $0 \le r < 6$ : $-23 \bmod 6 = 1$
$1$ asaldır	1 ne asal ne bileşik
Asallık için $n-1$ ‘e kadar dene	$\sqrt{n}$ ‘e kadar asallar yeter
EBOB için büyük üsler	EBOB küçük üs, EKOK büyük üs
Öklid’de son bölen EBOB	Sıfırdan önceki son kalan EBOB
İspatta $b = ak$ , $c = ak$	Farklı harfler: $b = ak$ , $c = al$
$(a \cdot b) \bmod m$ için önce tam çarpım	Önce $a \bmod m$ ve $b \bmod m$ , sonra çarp

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Find the quotient and remainder when 157 is divided by 12.

Cevabı göster

q = 13, r = 1

12'nin 157'ye sığan en büyük katı $12 \cdot 13 = 156$ . Kalan $157 - 156 = 1$ . Yani $157 = 12 \cdot 13 + 1$ , $0 \le 1 < 12$ şartı sağlanıyor.

Soru 2orta

Find $-47 \textbf{ div } 9$ and $-47 \bmod 9$ .

Cevabı göster

-6 and 7

Kalan negatif olamaz: $0 \le r < 9$ . $9 \cdot (-5) = -45$ denersen $-47 - (-45) = -2$ , negatif, olmaz. Bir aşağı in: $9 \cdot (-6) = -54$ , $-47 - (-54) = 7$ . Yani $-47 = 9 \cdot (-6) + 7$ : div $= -6$ , mod $= 7$ .

Soru 3kolay

Is $17 \equiv -8 \pmod 5$ ? Justify.

Cevabı göster

Yes

Tanım: $a \equiv b \pmod m \iff m \mid (a - b)$ . $17 - (-8) = 25 = 5 \cdot 5$ . 5, 25'i böler, yani evet. Kontrol: $17 \bmod 5 = 2$ ve $-8 \bmod 5 = 2$ , kalanlar aynı.

Soru 4orta

Without multiplying out, compute $(73 \cdot 58 + 41) \bmod 11$ .

Cevabı göster

Her sayıyı önce mod 11'e indir: $73 \bmod 11 = 7$ , $58 \bmod 11 = 3$ , $41 \bmod 11 = 8$ . Sonra $7 \cdot 3 + 8 = 29$ , $29 \bmod 11 = 7$ . Kontrol: $73 \cdot 58 + 41 = 4275 = 11 \cdot 388 + 7$ .

Soru 5kolay

Find the prime factorization of 1260.

Cevabı göster

2^2 · 3^2 · 5 · 7

Küçük asallardan başla: $1260 = 2 \cdot 630 = 2^2 \cdot 315$ . $315 = 3 \cdot 105 = 3^2 \cdot 35$ . $35 = 5 \cdot 7$ . Sonuç $1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7$ .

Soru 6orta

Is 221 prime? Justify by trial division.

Cevabı göster

No, 221 = 13 · 17

$\sqrt{221} \approx 14.9$ , yani 14'e kadar olan asalları denemek yeter: 2, 3, 5, 7, 11, 13. 2, 3, 5, 7, 11 bölmez; $221 / 13 = 17$ . Bileşik (composite): $221 = 13 \cdot 17$ .

Soru 7orta

Use the Euclidean algorithm to find $\gcd(1071, 462)$ . Then find $\operatorname{lcm}(1071, 462)$ .

Cevabı göster

gcd = 21, lcm = 23562

$1071 = 2 \cdot 462 + 147$ , $462 = 3 \cdot 147 + 21$ , $147 = 7 \cdot 21 + 0$ . Sıfırdan önceki son kalan: 21. EKOK için $\gcd \cdot \operatorname{lcm} = ab$ : $\operatorname{lcm} = \frac{1071 \cdot 462}{21} = 51 \cdot 462 = 23562$ .

Soru 8orta

Let $a = 2^3 \cdot 3^2 \cdot 7$ and $b = 2^2 \cdot 3^5 \cdot 5$ . Find $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ .

Cevabı göster

gcd = 36, lcm = 68040

EBOB: her asalın küçük üssü: $2^{\min(3,2)} \cdot 3^{\min(2,5)} \cdot 5^0 \cdot 7^0 = 2^2 \cdot 3^2 = 36$ . EKOK: her asalın büyük üssü: $2^3 \cdot 3^5 \cdot 5 \cdot 7 = 8 \cdot 243 \cdot 35 = 68040$ .

Soru 9zor

Find integers $s$ and $t$ such that $\gcd(252, 198) = 252s + 198t$ .

Cevabı göster

s = 4, t = -5 (gcd = 18)

Öklid: $252 = 1 \cdot 198 + 54$ , $198 = 3 \cdot 54 + 36$ , $54 = 1 \cdot 36 + 18$ , $36 = 2 \cdot 18$ . EBOB 18. Geri yerine koy: $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198$ . Kontrol: $1008 - 990 = 18$ .

Soru 10zor

Prove: if $a \mid b$ and $a \mid c$ , then $a \mid (3b - 2c)$ .

Cevabı göster

3b - 2c = a(3k - 2l) with k, l integers

Tanımı yaz: $a \mid b$ ise $b = ak$ , $a \mid c$ ise $c = al$ ( $k, l$ tam sayı, farklı harfler!). Sonra $3b - 2c = 3ak - 2al = a(3k - 2l)$ . $3k - 2l$ tam sayı olduğu için tanım gereği $a \mid (3b - 2c)$ . ∎

Soru 11orta

Compute $7^{100} \bmod 5$ .

Cevabı göster

$7 \equiv 2 \pmod 5$ , yani $7^{100} \equiv 2^{100}$ . Küçük kuvvetlere bak: $2^4 = 16 \equiv 1 \pmod 5$ . $100 = 4 \cdot 25$ , böylece $2^{100} = (2^4)^{25} \equiv 1^{25} = 1$ .

Soru 12kolay

How many positive divisors does 360 have?

Cevabı göster

$360 = 2^3 \cdot 3^2 \cdot 5$ . Bir bölen $2^a 3^b 5^c$ biçimindedir, $a \in \{0..3\}$ , $b \in \{0..2\}$ , $c \in \{0,1\}$ . Seçenek sayısı $(3+1)(2+1)(1+1) = 24$ .

Doğrulama: Bütün div/mod değerleri, çarpanlara ayırmalar, asallık testleri, gcd/lcm (Öklid ve kaba kuvvetle iki yoldan), Bezout katsayıları (genişletilmiş Öklid), bölen sayısı ve 7^100 mod 5 (BigInt) node ile hesaplandı; a|b, a|c ⇒ a|(3b-2c) küçük aralıkta taranarak kontrol edildi (verify/MAT2033/07.mjs).

Deftere not kartı

a | b <=> b = a*c (c tam sayi) 3 | 12 dogru, 12 | 3 yanlis Bolme algoritmasi: a = d*q + r, 0 <= r < d (q = a div d, r = a mod d) NEGATIF: -23 div 6 = -4, -23 mod 6 = 1 (kalan asla negatif olmaz) a = b (mod m) <=> m | (a - b) <=> a mod m = b mod m Toplama/carpma mod m'de once indir, sonra islem yap Asallik testi: sqrt(n)'e kadar asallari dene Her n > 1 tek bicimde asallarin carpimi (Fundamental Theorem) gcd = kucuk usler, lcm = buyuk usler, gcd*lcm = a*b Euclid: gcd(a,b) = gcd(b, a mod b); sifirdan onceki son kalan Bezout: gcd(a,b) = sa + tb (Euclid'i geri yerine koy) gcd(a,b) = 1 -> relatively prime (aralarinda asal) Ispat: a|b, a|c -> b = ak, c = al (FARKLI harfler) -> a cikar