İçindekiler
Takvim
Pazartesi ve Cuma sabahlarında buluşuyoruz.
- İlk ders 4 Mart
- 8 ve 12 Nisan bayram
- Son ders 14 Haziran
Konular
Aşağıdakilerini ve fazlasını yeni bir dokümana koydum, pdf ve html biçimlerinde.
Burada hata yapmamaya çalışıyorum, ama sayfanın matematiğinde veya Türkçesinde bir hata bulursanız lütfen bana haber verin.
Öklid Algoritması
Sayma Sayılarında
Sayma sayılarında a1 > a2 olduğunda, öyle
- n,
- a3, …, an+1,
- t1, …, tn
sayılarını bulabiliriz ki
a2 > a3 > … > an+1
ve
a1 | = | a2 | ⋅ | t1 | + | a3, |
a2 | = | a3 | ⋅ | t2 | + | a4, |
… | ||||||
an−1 | = | an | ⋅ | tn−1 | + | an+1, |
an | = | an+1 | ⋅ | tn. |
Bu durumda
an+1 = ebob(a1, a2).
Ayrıca
a1x − a2y = (−1)nan+1
Bézout denklemini çözebiliriz, ve bu şekilde hesaplarımızı kontrol edebiliriz.
Tersine n, t1, …, tn, ve an+1 sayılarını seçerek kendi alıştırmalarımızı yaratabiliriz.
Yukarıdaki durumda
a1/a2 | = | t1 + a3/a2 |
= | t1 + 1/(t2 + a4/a3) | |
= | … | |
= | t1 + 1/(t2 + 1/( … 1/tn)). |
Kısaltma olarak
a1/a2 = [t1, t2, …, tn].
Aslında
a1/a2 | = | β1, |
a2/a3 | = | β2, |
…, | ||
an/an+1 | = | βn |
olduğunda 1 ⩽ k < n ise
⌊ βk ⌋ = tk,
1/(βk−tk) = βk+1,
ve son olarak
βn = tn,
ama βn+1 tanımlanmaz.
Gerçel Sayılarda
Yukarıda β1, kesirli olmayan bir gerçel sayı olabilir, ve bu durumda her k için βk tanımlanır. Şimdi
p1/q1 | = | t1/1 | = | [t1], |
p2/q2 | = | t1 + 1/t2 | = | [t1, t2], |
p3/q3 | = | t1 + 1/(t2 + 1/t3) | = | [t1, t2, t3], |
… |
olsun. Eğer kare olmayan bir d sayma sayısı için β1 = √d ise, o zaman öyle bir n vardır ki
tn+1 = 2t1
ve her k için
tn+k+1 = tk+1.
Bu durumda her ℓ için
pℓn² − dqℓn² = (−1)ℓn.
Bu genel teoremi göstermiyoruz ama her özel durumda gösterebiliriz. Bu şekilde herhangi kare olmayan d için
x² − dy² = 1
Pell denkleminin, sonsuz sayıda çözümlerini bulabiliriz. Ayrıca
√d = limℓ→∞ pℓn/qℓn.
Sayılar Kuramının temelleri
İyisıralanmış bir küme, öyle doğrusal sıralanmış bir kümedir ki her boş olmayan altkümesinin en küçük elemanı vardır.
Eğer iyisıralanmış bir küme boş değilse, o zaman en küçük elemanı vardır. Ayrıca, bu kümenin bir a elemanı, kümenin en büyük elemanı değilse, o zaman a’dan büyük olan elemanların en küçüğü vardır, ve bu eleman, a’nın ardılıdır. Ne en küçük elemanı ne ardıl olan bir eleman, bir limittir.
Postulat. Sayma sayıları,
- boş olmayan,
- en büyük elemanı olmayan,
- limiti olmayan
iyisıralanmış bir küme oluşturur.
Tanım. Sayma sayıları kümesi
ℕ,
ve ℕ’nin en küçük elemanı
1,
ve ℕ’nin her n elemanının ardılı,
n + 1.
Tümevarım Teoremi. Eğer ℕ’nin bir altkümesi
- 1’i içerirse ve
- kümenin her elemanının ardılını da içerirse,
o zaman bu altküme ℕ’nin kendisidir.
Özyineleme Teoremi. Eğer
- A, bir küme,
- b ∈ A,
- f: A → A
işe, o zaman bir ve tek bir g vardır, öyle ki
- g: ℕ → A,
- g(1) = b,
- her zaman g(n + 1) = f(g(n)).
Tanım.
Toplama:
n + (k + 1) = (n + k) + 1.
Çarpma:
n ⋅ 1 = n, n ⋅ (k + 1) = n ⋅ k + n. Kuvvet alma:
n1 = n, n(k + 1) = nk ⋅ n.
Teorem. Toplama ve çarpma, birleşmeli ve değişmelidir, ve çarpma, toplama üzerinde dağılır.
Kanıt. Tümevarım. Değişmeli özelliğin her durumunda üç tümevarım kullanır, çünkü
1 + n | = | n + 1, | 1 ⋅ n | = | n, | |
(k + 1) + n | = | (k + n) + 1, | (k + 1) ⋅ n | = | (k ⋅ n) + n |
eşitlikler de gösterilir. Ayrıntılar, bir alıştırmadır.
Teorem.
ab + c | = | ab ⋅ ac, |
ab ⋅ c | = | (ab)c. |
Kanıt. Bir alıştırmadır.
Teorem. Eğer a < b ise, o zaman
bir ve tek bir z için
a + z = b;
bir ve tek bir y için
a ⋅ y ⩽ b ⩽ a ⋅ y + a;
a > 1 olduğunda bir ve tek bir x için
ax ⩽ b < ax ⋅ a,
dolayısıyla bir ve tek bir y için
ax ⋅ y ⩽ b < ax ⋅ y + ax & y < a.
Örnek.
2024 | = | 210 + 29 + 28 + 27 + 26 + 25 + 23, |
10 | = | 23 + 2, |
3 | = | 2 + 1, |
9 | = | 23 + 1, |
… |
ve sonuç olarak
2024 = 222+1+2 + 222+1+1 + 222+1^^ + 222+2+1 + 222+2 + 222+1 + 22+1
Kalandaşlık
Tanımlar.
ω | = | ℕ ∪ {0}, |
ℤ | = | ω ∪ {−x: x ∈ ℕ}. |
Okulda öğrendimiz gibi toplama ve çarpma, ℤ’de tanımlanır, ve sonuç olarak ℤ, değişmeli bir halka olur. Bu durumda a ∈ ℕ olduğunda
aℤ = (a) = {ax: x ∈ ℤ},
ve n ∈ ℕ olduğunda tanıma göre
ℤn = ℤ/nℤ = ℤ/(n).
Ayrıca ℤ’de
a | b ⇔ ∃x ax = b.
Şimdi n ∈ ℕ olduğunda
a ≡ b (mod n) ⇔ n | a − b,
ve bu durumda a ve b, n modülüsüne göre kalandaştır. Sonuç olarak
a ≡ b (mod n) ⇔ a + (n) = b + (n).
Öklid Lemması. ℤ’de
a | bc & ebob(a,b) = 1 ⇒ a | c.
Kanıt.
a | bc & ax + by = 1
olduğunda
a | acx + bcy & acx + bcy = c.
Teoremler.
a ≡ b (mod n) ⇒ a ≡ b ± n (mod n).
ac ≡ bc (mod n) & ebob(c,n) = 1 ⇒ a ≡ b (mod n).
ac ≡ bc (mod nc) | ⇔ | a ≡ b | (mod n) |
⇔ | a ≡ b ∨ a ≡ b + n ∨ … ∨ a ≡ b + (c − 1) ⋅ n | (mod nc). |
Eğer ebob(a,n) = 1 ise, o zaman öyle c vardır ki
∃y ac + ny = 1,
ve sonuç olarak
ax ≡ b (mod n) ⇔ x ≡ bc (mod n).
Şimdi bir ax ≡ b (mod n) kalandaşlığının çözümü varsa onu bulabiliriz.
Eğer ebob(m,n) = 1 ise, o zaman
a ≡ b (mod mn) ⇔ a ≡ b (mod m) & a ≡ b (mod (n).
Çin Kalan Teoremi. {n1, …, nk} ⊆ ℕ olduğunda
1 ⩽ i < j ⩽ k ⇒ ebob(ni,nj) = 1
olsun. O zaman
N = n1 … nk
olduğunda her durumda
Ni = N/ni
olduğunda öyle bi vardır ki
biNi ≡ 1 (mod ni),
ve sonuç olarak
x ≡ a1 (mod n1) & … & x ≡ ak (mod nk)
sisteminin çözümü,
x ≡ a1b1N1 + … + akbkNk (mod N).
Asallık
Eğer
ebob(a,b) = 1
ise, o zaman a ve b, birbirine asaldır.
Eğer
p > 1 & ∀x ebob(p,x) ∈ {1, p}
ise, o zaman p asaldır.
Aritmetiğin Temel Teoremi. Her sayma sayısı, bir ve tek bir şekilde, öyle
p1 … pn
çarpımıdır ki her pk çarpanı asaldır ve
p1 ⩽ … ⩽ pn.
Burada n = 0 olabilir, ve bu durumda p1 … pn = 1.
Kanıt. Sayma sayıları iyisıralandığından ve sayma sayılarında
a | b ⇒ a ⩽ b
olduğundan
- 1’den büyük olan her sayma sayısının asal bir çarpanı vardır;
- her sayma sayısı, asalların bir çarpımıdır.
Öklid Lemması sayesinde bu çarpım tektir.
Teorem.
ab = ebob(a,b) ⋅ ekok(a,b).
Lamé Teoremi
Sayma sayılarında, bildiğimiz gibi,
a1 | = | a2 | ⋅ | t1 | + | a3, |
a2 | = | a3 | ⋅ | t2 | + | a4, |
… | ||||||
an−1 | = | an | ⋅ | tn−1 | + | an+1, |
an | = | an+1 | ⋅ | tn |
olduğunda,
an+1 = ebob(a1, a2).
Ayrıca tn > 1 varsayılabilir, ve bu durumda, eğer
a2 < 10ℓ
ise, o zaman
n ⩽ 5ℓ.
Zira
a2 | ⩾ | a3 | + | a4, |
… | ||||
an−1 | ⩾ | an | + | an+1, |
an | > | an+1. |
Özyineleme ile
F1 | = | 1, |
F2 | = | 1, |
F3 | = | 2, |
ve genelde
Fk+2 = Fk + Fk+1
olsun. Bunlar, Fibonacci Sayılarıdır. O zaman
an+1 | ⩾ | F2, |
an | ⩾ | F3, |
an−1 | ⩾ | F4, |
… | ||
a2 | ⩾ | Fn+1. |
Şimdi
φ | = | (1 + √5)/2, |
ψ | = | (1 − √5)/2 |
olsun. Burada φ, Altın Orandır. Ayrıca φ ve ψ,
x2 = x + 1
denkleminin çözümleridir. O zaman her (α, β) için
(αφk + βψk) + (αφk+1 + βψk+1) = αφk+2 + βψk+2.
Ayrıca
x | + | y | = | 1 |
φx | + | ψy | = | 1 |
lineer sisteminin çözümü
(φ/(φ − ψ), −ψ/(φ − ψ))
olduğundan
Fk = (φk − ψk)/(φ − ψ)
Binet Formülü’nü elde ediyoruz. Ayrıca tümevarım ile her durumda
Fk > φk/φ2,
çünkü
F1 | = | 1 | > | 1/φ2, |
F2 | = | 1 | > | 1/φ, |
ve eğer
Fk | > | φk/φ2, |
Fk+1 | > | φk+1/φ2 |
ise, o zaman
Fk+2 = Fk + Fk+1 > (φk + φk+1)/φ2 = φk+2/φ2.
Bundan dolayı
a2 > φn−1.
Ayrıca tümevarım ile
φk+1 = Fk+1φ + Fk
olduğundan ve
k | 1 | 2 | 3 | 4 | 5 |
Fk | 1 | 1 | 2 | 3 | 5 |
olduğundan
φ5 = 5φ + 3 = (11 + 5√5)/2.
Son olarak
11 + 5√5 | > | 20 | |
⇔ | 5√5 | > | 9 |
⇔ | 125 | > | 81 |
olduğundan
φ5 > 10.
Şimdi, eğer tekrar
a2 < 10ℓ
ise, o zaman
10(n−1)/5 | < | 10ℓ, |
n−1 | < | 5ℓ, |
n | ⩽ | 5ℓ. |
Örneğin a2 < 1000 ise n ⩽ 15. Αyrıca
k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Fk | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Fk+10 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 |
olduğundan (a1, a2) = (1597, 987) ise n = 15.
Sınavlar
- 19 Nisan. Çözümler (4 sayfa
pdf
) - 24 Mayıs
- Final:
İlk iki sınavdan daha iyisi sayılacak; telafi sınavı olmayacak.
Kaynaklar
Dersin tek resmi kaynağı, derslerdir, ama bunlar için aşağıdakileri kullanabilirim.
Edmund Landau:
- Foundations of Analysis (third edition, Chelsea, 1966), Chapter 1: Natural Numbers (ii + 18 sayfa)
- Elementary Number Theory (Chelsea, 1958): Part I, Chapters 1–7 (greatest common divisors, prime factorization, number-theoretic functions, congruences, quadratic residues, Pell equation)
Elementary Number Theory: notlarım, A5 kağıt, 196 sayfa
Sayılar Kuramına Giriş (Matematik Vakfı, Ankara, Aralık 2000)
Euclid, Elements, Books VII–IX: Heath’s translation with commentary (ii + 150 pages)
David M. Burton, Elementary Number Theory (6th ed., McGraw-Hill, 2007)
Hardy and Wright, An Introduction to the Theory of Numbers (5th ed., Oxford, 1979)