Sayılar Teorisi

Bölünebilme

• a | b: b = a·k olacak şekilde k ∈ ℤ vardır. a | b ve a | c ise a | (mb + nc).
• Bölme algoritması: a = bq + r, 0 ≤ r < |b|; q ve r tektir.
• Bölünebilme kuralları: 2 (son basamak çift), 3 (rakamlar toplamı 3'e bölünür), 4 (son iki basamak), 5 (son basamak 0 veya 5), 8 (son üç basamak), 9 (rakamlar toplamı), 11 (sağdan itibaren rakamların +, − işaretli toplamı 11'in katı).

EBOB, EKOK ve Öklid Algoritması

• Öklid algoritması: ebob(a, b) = ebob(b, a mod b); kalan sıfır olana kadar bölme sürdürülür.
• Bézout özdeşliği: ebob(a, b) = ax + by olacak şekilde x, y tam sayıları vardır.
• ebob(a, b)·ekok(a, b) = a·b (a, b pozitif). ebob(a, b) = 1 ise a ve b aralarında asaldır.
• Lineer Diofant denklemi: ax + by = c'nin tam sayı çözümü vardır ⟺ ebob(a, b) | c. Bir çözüm (x₀, y₀) ise genel çözüm x = x₀ + (b/d)t, y = y₀ − (a/d)t.

Asal Sayılar

• Aritmetiğin temel teoremi: 1'den büyük her tam sayı asal çarpanlarına tek türlü ayrılır (sıra dışında).
• Öklid teoremi: Sonsuz sayıda asal sayı vardır.
• Bir n sayısının asal olup olmadığını anlamak için √n'den küçük asallara bölünüp bölünmediğine bakmak yeterlidir (Eratosthenes kalburu).
• Pozitif bölen sayısı: n = p₁^a₁·p₂^a₂·…·pₖ^aₖ ise d(n) = (a₁ + 1)(a₂ + 1)…(aₖ + 1). Bölenler toplamı: σ(n) = Π (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1).
• Mükemmel sayı: Kendisi hariç bölenleri toplamı kendisine eşit (6, 28, 496).

Modüler Aritmetik (Denklik)

• a ≡ b (mod n) ⟺ n | (a − b). Denklik toplama, çıkarma, çarpma ve üs almaya göre korunur.
• Doğrusal denklik: ax ≡ b (mod n)'nin çözümü vardır ⟺ d = ebob(a, n) | b; bu durumda mod n'de d tane çözüm vardır.
• Fermat'ın küçük teoremi: p asal ve p ∤ a ise a^(p−1) ≡ 1 (mod p); her a için aᵖ ≡ a (mod p).
• Euler fonksiyonu φ(n): n'den küçük ve n ile aralarında asal pozitif tam sayıların sayısı. φ(p) = p − 1; φ(pᵏ) = pᵏ − pᵏ⁻¹; aralarında asal m, n için φ(mn) = φ(m)φ(n); φ(n) = n·Π(1 − 1/p).
• Euler teoremi: ebob(a, n) = 1 ise a^φ(n) ≡ 1 (mod n).
• Wilson teoremi: p asal ⟺ (p − 1)! ≡ −1 (mod p).
• Çin kalan teoremi: Modülleri ikişer ikişer aralarında asal olan denklik sistemlerinin, modüllerin çarpımına göre tek bir çözümü vardır.

Diğer Konular

Taban aritmetiği (sayıların farklı tabanlarda yazılması), rakam problemleri, Fibonacci dizisi ve özellikleri (ardışık iki Fibonacci sayısı aralarında asaldır), Pisagor üçlüleri (m² − n², 2mn, m² + n²), birim basamağı bulma (döngüler), faktöriyelde sondaki sıfır sayısı (⌊n/5⌋ + ⌊n/25⌋ + …).