İçindekiler
Takvim
Pazartesi ve Cuma sabahlarında buluşuyoruz.
- İlk ders 4 Mart
- 8 ve 12 Nisan bayram
- Son ders 14 Haziran
Konular
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)