Küçük sayılar teorisi. Sayı teorisi: teori ve pratik

Sayı teorisi veya yüksek aritmetik, tam sayıları ve benzer nesneleri inceleyen bir matematik dalıdır.

Sayı teorisi tam sayıların özelliklerinin incelenmesiyle ilgilidir. Şu anda sayı teorisi, doğal sayıların incelenmesinin ötesine geçen çok daha geniş bir konu yelpazesini içermektedir.

Sayı teorisinde sadece doğal sayılar değil aynı zamanda tüm tam sayılar kümesi de dikkate alınır. rasyonel sayılar, ayarlamak cebirsel sayılar. Modern sayı teorisi çok kullanımıyla karakterize edilir çeşitli yöntemler araştırma. Modern sayılar teorisinde yöntemler yaygın olarak kullanılmaktadır. matematiksel analiz.

Modern teori sayılar aşağıdaki bölümlere ayrılabilir:

1) Temel sayılar teorisi. Bu bölüm sayılar teorisinin sorularını içermektedir. doğrudan gelişme bölünebilirlik teorileri ve sayıların temsil edilebilirliğine ilişkin sorular belli bir biçim. Daha genel bir problem, Diophantine denklem sistemlerini, yani bilinmeyenlerin değerlerinin mutlaka tamsayı olması gereken denklemleri çözme problemidir.

2) Cebirsel teori sayılar. Bu bölüm cebirsel sayıların çeşitli sınıflarının incelenmesiyle ilgili soruları içerir.

3) Diophantine yaklaşımları. Bu bölüm reel sayı yaklaşımı çalışmasına ilişkin soruları içermektedir. rasyonel kesirler. Aynı fikir çemberiyle yakından ilişkili olan Diophantine yaklaşımları, çeşitli sayı sınıflarının aritmetik doğasının incelenmesiyle yakından ilgilidir.

4) Analitik sayılar teorisi. Bu bölüm, matematiksel analiz yöntemlerinin uygulanmasının gerekli olduğu çalışmalar için sayı teorisinin sorularını içerir.

Temel kavramlar:

1) Bölünebilirlik, bölme işlemiyle ilişkili aritmetiğin ve sayılar teorisinin temel kavramlarından biridir. Küme teorisi açısından bakıldığında, tam sayıların bölünebilirliği, tam sayılar kümesi üzerinde tanımlanan bir ilişkidir.

Eğer bir a tamsayısı ve bir b tamsayısı için bq = a olacak şekilde bir q tamsayısı varsa, o zaman a sayısının b'ye bölünebildiğini veya b'nin a'yı böldüğünü söyleriz. Bu durumda b sayısına a sayısının böleni denir, a'nın böleni b sayısının katı olacaktır ve q sayısına a'nın b'ye bölümünün bölümü denir.

2) Basit bir sayı mı? tam olarak iki farklı sayıya sahip bir doğal sayıdır doğal bölen: birim ve kendiniz. Biri dışındaki tüm sayılara bileşik sayılar denir.

3) Mükemmel sayı mı? (eski Yunanca ἀριθμὸς τέλειος) - doğal sayı, toplamına eşit tüm kendi bölenleri (yani tümü pozitif bölenler, kendisinden farklı mı? sayılar).

İlk mükemmel sayı 6 (1 + 2 + 3 = 6), sonraki mükemmel sayı ise 28'dir (1 + 2 + 4 + 7 + 14 = 28). Doğal sayılar arttıkça mükemmel sayılar giderek daha az yaygın hale geliyor.

4) İki m ve n tamsayısının en büyük ortak böleni (OBB), ortak bölenlerinin en büyüğüdür. Örnek: 70 ve 105 sayıları için en büyüğü ortak bölen 35'e eşittir.

En büyük ortak bölen mevcuttur ve m veya n sayılarından en az birinin sıfır olmaması durumunda benzersiz bir şekilde belirlenir.

5) m ve n tam sayılarının en küçük ortak katı (LCM), m ve n'ye bölünebilen en küçük doğal sayıdır.

6) m ve n sayılarına birden başka ortak böleni yoksa eş asal sayı denir. Bu tür sayılar için GCD(m,n) = 1. Tersine, eğer GCD(m,n) = 1 ise sayılar aralarında asaldır.

7) Öklid algoritması - iki tam sayının en büyük ortak bölenini veya iki homojen miktarın en büyük ortak ölçüsünü bulmaya yönelik bir algoritma.

İlgilendiğiniz bilgileri bilimsel arama motoru Otvety.Online'da da bulabilirsiniz. Arama formunu kullanın:

17 numaralı konu hakkında daha fazla bilgi. Sayı teorisinin temel kavramları:

Sayı teorisi, sayıların özelliklerini inceleyen bir matematik dalıdır.

Sayı teorisinin ana amacı doğal sayılardır (bkz. Sayı). Sayı teorisine göre dikkate alınan temel özellikleri bölünebilmedir. Sayı teorisindeki ilk problem aralığı sayıları çarpanlara ayırmadır. Bu ayrıştırmadaki ana “yapı taşları” asal sayılardır; yalnızca 1'e ve kendilerine bölünebilen sayılar; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - bunlar ilk on asal sayılar(1 sayısı asal sayılmaz). Harika teorem Aritmetiğin temel teoremi olarak adlandırılan, şunu belirtir: Her doğal sayı, aşağıdakilere ayrıştırılabilir asal faktörler, Ve tek yol(konum sırasına göre). İki sayıyı asal çarpanlara ayırarak birinin diğerine bölünüp bölünemeyeceğini belirlemek kolaydır. Ancak bunun olup olmadığını öğrenmek yine de zor olabilir. büyük sayı basit, yani kendisinden ve birden başka bir sayıya bölünüp bölünemeyeceği.

Sayıların asal çarpanlara ayrılmasıyla ilgili seri şu şekildedir: aritmetik fonksiyonlar. Bunlardan bazılarını belirtelim. φ(n) - Euler işlevi - n sayısıyla aralarında asal olan 1'den n'ye kadar olan sayıların sayısı (yani n ile paylaşılmayan) ortak faktörler, biri hariç); α(n) n sayısının bölenlerinin sayısıdır, t(n) n sayısının tüm bölenlerinin toplamıdır, π(n) Chebyshev fonksiyonudur - n'yi aşmayan asal sayıların sayısı. Bu fonksiyonlar doğal sayıların birçok özelliğini ifade eder. Öklid teoremi sonsuz sayıda asal sayının bulunduğunu belirtir. Bu, n sayısı arttıkça π(n)→∞ olacağı anlamına gelir. π(n) fonksiyonunun ne kadar hızlı sonsuza yöneldiğini bulmayı başardık. Fonksiyonla yaklaşık olarak aynı olduğu ortaya çıktı

Bu teoreme asal sayıların dağılımının asimptotik yasası denir. P. L. Chebyshev (1849) tarafından formüle edilmiş ve büyük ölçüde kanıtlanmıştır ve yalnızca 50 yıl sonra tamamen kanıtlanmıştır.

Asal sayıların asimptotik dağılımı yasası, sayı-teorik fonksiyonları incelemek için yaygın olarak matematiksel analiz yöntemlerini kullanan analitik sayı teorisi olarak adlandırılan şeyin sonucudur. 19. yüzyılın ikinci yarısında keşfedildi. tamsayılar gibi ayrı bir nesne ile fonksiyonların derin özellikleri arasındaki bağlantının, sayılar teorisinin gelişimi üzerinde büyük etkisi oldu.

Sayıları çarpanlara ayırma, yalnızca çarpmayla ilişkili doğal sayılar kümesinin yapısını (en derin ve en derin) dikkate alır. zor görevler Sayı teorileri toplama ve çarpma işlemlerinin karşılaştırılmasından ortaya çıkar. Bu tür problemler arasında örneğin Goldbach problemi yer alıyor - herhangi bir şey yapmak mümkün mü? çift sayı bunu iki asal sayının toplamı olarak temsil edin; büyük teorem Fermat (bkz. Fermat'ın son teoremi) - bu mümkün mü n'inci güç sayıları şu şekilde temsil edin n'lerin toplamı herhangi iki sayının kuvvetleri vb.

Sayı teorisi çekicidir çünkü birçok basit formülasyon içerir ancak zor ve ilginç görevler. Çözülmüş ve çözülmemiş bu problemlerin çoğu birikmiştir ve sayı teorisi çoğu zaman farklı, zarif bulmacaların bir koleksiyonu gibi görünmektedir. Ancak bu doğru değil. Sayı teorisi kendi harika yöntemlerini yarattı ve bunların birçoğu son yıllarda aktif olarak geliştirildi ve bu, tam da bu konuya yeni bir canlı akım enjekte etti. antik kısım matematik.

Sayı teorisinin klasik yöntemi karşılaştırma yöntemidir. Seçilen bir sayıya bölündüğünde aynı kalanları veren sayıları belirleyerek, çoğu zaman herhangi bir ilişkinin imkansızlığını ortaya koymak mümkündür. Örneğin, 3'e (veya dedikleri gibi modulo 3) bölünmenin kalanları göz önüne alındığında, doğal sayılarda 3x 2 + 4y 2 = 5z 2 denkleminin çözülemezliğini kanıtlamak kolaydır.

Analitik yöntem Daha önce de söylediğimiz gibi, sayılardan yola çıkarak matematiksel analiz yöntemleriyle incelenen fonksiyonları oluşturmalarından ibarettir. Evet, Sovyet bilim adamı akademisyen I.M. Vinogradov, Goldbach probleminin bir versiyonunu kanıtladı - yeterince büyük bir tek sayının üç asal sayının toplamı olarak temsil edilebilirliği.

Örnek olarak Fermat'ın son teoremini kullanarak sayılar teorisinin geometrik yöntemini açıklıyoruz. Bu teoremde hakkında konuşuyoruz tam sayılarda x n + y n = z n denkleminin çözülebilirliği üzerine. Denklemin her iki tarafını z n'ye bölerek ve x/z'yi m ile ve y/z'yi v ile değiştirerek u n + v n = 1 denklemini elde ederiz. Bu denklem, (u, v) koordinatlı düzlem üzerinde belirli bir eğriyi tanımlar. Orijinal denklemin tamsayılardaki çözümleri, yeni denklemin rasyonel sayılardaki çözümlerine karşılık gelir. Bu tür çözümlerin (u, v) her biri, bu düzlem üzerinde rasyonel koordinatlara sahip bir nokta olarak söylenebilir. Şimdi başvurmayı deneyebiliriz geometrik yöntemlerüzerinde rasyonel koordinatlara sahip noktalar kümesini incelemek için u n + v n = 1 eğrisine gidin.

Tamsayılar ve rasyonel sayılardaki denklemlerin çözümlerini bulmayı konu alan sayı teorisinin büyük bir bölümüne, adını antik Yunan bilim adamı Diophantus'tan (3. yüzyıl) alan Diophantine denklemleri teorisi adı verilir.

Sayılar teorisindeki en eski ve iyi bilinen problemlerden biri, sayıların kare toplamları ile temsil edilmesi problemidir. Elde edilen sonuçlardan bazılarını listeliyoruz:

her tam sayı, dört tam sayı karesinin toplamı olarak temsil edilebilir (örneğin: 7 = 2 2 + 1 2 + 1 2 + 1 2);

4n + 1 formundaki her asal sayı, iki tam sayı karesinin toplamı olarak temsil edilebilir (örneğin: 5 = 2 2 + 1 2, 41 = 4 2 + 5 2, vb.), ancak tek bir tam sayı olamaz ( sadece bir asal değil) 4n + 3 formundaki bir sayı bu formda temsil edilemez;

8n - 1 formundaki sayılar dışındaki her asal sayı, üç tam sayının karesinin toplamı olarak temsil edilebilir.

Basit cebirsel kimlik

(a 2 + b 2) (x 2 + y 2) = (ax + by) 2 + (ay - bx) 2

şu sonuca varmamızı sağlar: eğer iki sayı iki karenin toplamı olarak temsil edilebiliyorsa, o zaman bunların çarpımı da iki karenin toplamı olarak temsil edilebilir. Cebirsel yöntemler V son zamanlarda Sayı teorisinde yaygın olarak kullanılır. Bu, görünümü sayı teorisindeki problemler tarafından büyük ölçüde teşvik edilen bir alan gibi genel bir cebirsel kavramın geliştirilmesiyle kolaylaştırılmıştır.

Sayı teorisi neden bu kadar değerli? Sonuçta sonuçlarının doğrudan uygulamasını bulmak zordur. Bununla birlikte, sayı teorisi problemleri yüzyıllar boyunca hem meraklı gençlerin hem de bilim adamlarının ilgisini çekmiştir. Sorun ne burada? Öncelikle bu sorunlar daha önce de belirttiğimiz gibi çok ilginç ve güzel. İnsanlar her zaman buna şaşırdılar basit sorular Sayılarla ilgili bir cevap bulmak çok zor. Bu cevapların aranması çoğu zaman önemi sayı teorisinin kapsamını çok aşan keşiflere yol açmıştır. Sözde idealler teorisinden bahsetmek yeterli Alman matematikçi XIX yüzyıl Fermat'ın son teoremini kanıtlama girişimleriyle bağlantılı olarak doğan E. Kummer.

İsim: Sayı teorisi. 2008.

Ders kitabı sonuçlara dayanmaktadır. temel teori Fermat, Euler, Gauss ve diğerleri gibi klasiklerin eserlerinde oluşturulan sayılar, asal ve bileşik sayılar, aritmetik fonksiyonlar, karşılaştırma teorisi, ilkel kökler ve indeksler, sürekli kesirler, cebirsel ve aşkın sayılar gibi konular ele alınır. Asal sayıların özellikleri, Diophantine denklemleri teorisi, sayı teorisinin algoritmik yönleri ve kriptografideki uygulamaları (büyük asal sayıların asallık açısından kontrol edilmesi, çarpanlara ayırma) büyük sayılar faktörlere ayırma, ayrık logaritma) ve bilgisayar kullanma.
Yükseköğretim kurumlarının öğrencileri için.

Sayı teorisi çalışmasının konusu sayılar ve onların özellikleridir, yani. sayılar burada bir araç veya araç olarak değil, bir çalışma nesnesi olarak ortaya çıkıyor. Doğal seri
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- doğal sayılar kümesi - en önemli araştırma alanıdır, son derece bilgilendirici, önemli ve ilginçtir.
Doğal sayıların incelenmesi 1900'lerde başladı Antik Yunanistan. Öklid ve Eratosthenes sayıların bölünebilirlik özelliklerini keşfettiler, asal sayılar kümesinin sonsuzluğunu kanıtladılar ve bunları oluşturmanın yollarını buldular. Çözümle ilgili sorunlar belirsiz denklemler tam sayılar Diophantus'un yanı sıra bilim adamlarının araştırma konusuydu Antik Hindistan ve Eski Çin, Orta Asya ülkeleri.

İçindekiler
giriiş
Bölüm 1. Sayıların bölünebilirliği hakkında
1.1. Tam Sayıların Bölünebilme Özellikleri
1.2. En küçük ortak kat ve en büyük ortak bölen
1.3. Öklid algoritması
1.4. Tamsayı çözümü doğrusal denklemler

Bölüm 2. Asal ve bileşik sayılar
2.1. Asal sayılar. Eratostenes Eleği. Asal sayılar kümesinin sonsuzluğu
2.2. Aritmetiğin Temel Teoremi
2.3. Chebyshev'in teoremleri
2.4. Riemann Zeta Fonksiyonu ve Asal Sayıların Özellikleri
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 3. Aritmetik Fonksiyonlar
3.1. Çarpımsal fonksiyonlar ve özellikleri
3.2. Möbius fonksiyonu ve ters çevirme formülleri
3.3. Euler işlevi
3.4. Bölenlerin toplamı ve bölenlerin sayısı doğal sayı
3.5. Aritmetik fonksiyonların ortalama değerinin tahminleri
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 4: Sayısal Karşılaştırmalar
4.1. Karşılaştırmalar ve temel özellikleri
4.2. Kesinti sınıfları. Belirli bir modül için kalıntı sınıfları halkası
4.3. Tam ve azaltılmış kesinti sistemleri
4.4. Wilson teoremi
4.5. Euler ve Fermat teoremleri
4.6. Rasyonel sayıların sonsuz olarak gösterimi ondalık sayılar
4.7. Asallık testi ve büyük asal sayılar oluşturma
4.8. Tamsayı çarpanlara ayırma ve kriptografik uygulamalar
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 5. Bir bilinmeyenle karşılaştırmalar
5.1.Temel tanımlar
5.2 Birinci derecenin karşılaştırmaları.
5.3.Çin kalan teoremi
5.4. Polinom karşılaştırmaları basit modül
5.5. Bileşik modüle göre polinom karşılaştırmalarıBağımsız çözüm problemleri
Bölüm 6. İkinci derecenin karşılaştırmaları
6.1. İkinci derece modulo prime'ın karşılaştırmaları
6.2. Legendre'nin sembolü ve özellikleri
6.3. İkinci dereceden karşılıklılık yasası
6.4.Jacobi sembolü ve özellikleri
6.5 İki ve dört karenin toplamı
6.6. Sıfırın temsili ikinci dereceden formlarüç değişkenden
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 7. Terstürev kökler ve indeksler
7.1. Belirli bir modül için bir sayının göstergesi
7.2. İlkel köklerin varlığı modulo prime
7.3. pk ve 2pk modüllerini kullanarak ilkel köklerin inşası
7.4. 2, 4, pk ve 2pk dışındaki modüllerde ilkel köklerin yokluğuna ilişkin teorem
7.5. İndeksler ve özellikleri
7.6. Ayrık logaritma
7.7. Binom karşılaştırmaları
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 8. Devamlı Kesirler
8.1. Gerçek sayıların rasyonel sayılarla yaklaşımına ilişkin Dirichlet teoremi
8.2. Sonlu sürekli kesirler
8.3. Devam eden kesir gerçek sayı
8.4. En İyi Yaklaşımlar
8.5. Eşdeğer sayılar
8.6. İkinci dereceden mantıksızlıklar ve sürekli kesirler
8.7. Bazı Diofant denklemlerini çözmek için sürekli kesirleri kullanma
8.8 e sayısının sürekli kesre ayrıştırılması.
Bağımsız olarak çözülmesi gereken sorunlar
Bölüm 9. Cebirsel ve aşkın sayılar
9.1.Cebirsel sayıların alanı
9.2. Cebirsel sayıların rasyonel sayılara yaklaşımı. Aşkın sayıların varlığı
9.3. Er ve n sayılarının irrasyonelliği
9.4. e sayısının aşkınlığı
9.5. N sayısının aşkınlığı
9.6 Bir dairenin karesinin imkansızlığı
Bağımsız olarak çözülmesi gereken sorunlar
Cevaplar ve yol tarifleri
Referanslar

Ücretsiz indir e-kitap uygun bir formatta izleyin ve okuyun:
Sayı Teorisi - Nesterenko Yu.V. kitabını indirin. - fileskachat.com, hızlı ve ücretsiz indirme.

Djvu'yu indirin
Aşağıda bu kitabı Rusya genelinde teslimatla indirimli olarak en iyi fiyata satın alabilirsiniz.

Sayı teorisi1

1. Bölünebilme teorisinin temel kavramları

Î TANIM. a = b · c eşitliğini sağlayacak şekilde bir c tamsayısı varsa a, sıfırdan farklı bir b sayısıyla bölünebilir.

Tanımlar:

1) a .b a, b'ye bölünür;

2) b | a b a'yı böler;

3) a, b'nin katıdır (kattır), b, a böleninin katıdır.

Kalanlı bölme

a èb ,a Z ,b N gibi iki sayı verilsin, Z bir tamsayılar kümesi ve N bir doğal sayılar kümesi olsun. íàb kalanıyla bölünebilir a =b · q +r , ㅠㅠ 0≤ r aralığında yer alır< b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Teorem 1. Herhangi bir a tamsayısı ve b doğal sayısı için gösterim

a = b q+ r,0 ≤ r< b

sadece.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Varoluş.

düşünelim sonsuz küme sayılar (a − tb) , aaaa ,b sabit sayılar, t herhangi bir sayı, t Z . Buradan negatif olmayan en küçük sayı r =a − q · b'yi seçeceğiz. r'nin içeride olduğunu kanıtlayalım

0 ≤r< b.

Bu sayı bu aralığa ait olmasın. O halde b'den büyük veya eşittir. Yeni bir sayı oluşturalım r ′ =r−b =a−q·b−b =a−b (q +1).

Buradan şunları görebiliriz:

1) r' (a - tb);

2) r' negatif değil;

1 S.V. Eylül 2012. Dersler ve görevler. Serbestçe dağıtılır. Kurs, St. Petersburg Devlet Havacılık Yönetimi Üniversitesi'nde (1997 1999; 2008 2011) ve St. Petersburg Devlet Pedagoji Üniversitesi'nde (2002 2005) öğretildi.

3) r'< r .

Bu nedenle değil r , a r' en küçüktür negatif olmayan sayı(a − tb) kümesinden ise r ≥ b varsayımı yanlıştır.

Varlığı kanıtlandı.

2. Benzersizlik.

Başka bir temsil olsun a =bq ′ +r ′ , şu şartla 0≤r'< b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Şartları taşıma bir yönde ñq ve diğer yönde сr ile b (q − q ′ ) =r ′ − r elde ederiz. Görünüşe göre

÷òî (r ′ − r ) .b . Kalanların her biri b и'den küçüktür

(r′ – r) . B. |r' − r|< b

Sonuç olarak, r ′ − r = 0, bu da r ′ =r èq =q ′ anlamına gelir. Yani kanıtladık

bir sayının diğerine yalnızca bir şekilde bölünebilmesi. Teorem kanıtlandı.

Teorem 2. Eğer a .bèb .c , tòa .c , aaab, c ≠ 0 ise.

a = b · q. b= c t

Bu nedenle a =c · qt. Tanım gereği a .c olduğu açıktır.

Teorem 3. a 1 +a 2 =b 1 +b 2 eşitliği ve a 1, a 2, b 1 .d sayıları sağlansın, sonra b 2 .d olsun.

Ä î ê à ç à ò å ë ü ñ ò â î

a 1 =d · t 1 ,a 2 =d · t 2 ,b 1 =d · t 3 . b 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ) teoreminin koşullarından b 2'yi ifade edelim. Bölünebilirliğin tanımına göre b 2 .d olduğu açıktır.

2. En büyük ortak bölen

Î tanım ise. c, a èb sayısının bir böleni ise, c sayısına a èb sayısının ortak böleni denir.

Tanım: a èb sayılarının ortak bölenlerinin en büyüğüne, a èb sayılarının en büyük ortak böleni (OBB) denir.

Gösterim: (a, b) =d, ㅠㅠㅠ èb sayıları, ad en yaygın olanıdır

bu sayıların böleni.

12 ve 9 sayıları için bir örnek verelim. 12'nin tüm bölenlerini ve 9'un tüm bölenlerini yazalım. 12 için: 1, 2, 3, 4, 6 ve 12; 9 için: 1, 3 ve 9; 1 ve 3 ortak bölenlerinin olduğu açıktır. En büyüğünü 3 seçelim. Böylece (12, 9) = 3 olur.

Tanım: A ve b sayılarına, eğer gcd'leri 1'e eşitse eş asal sayı denir.

Örnek. Çünkü (10,9)=1 ise 10 ve 9 aralarında asal sayılardır.

Bu tanım herhangi bir sayıda sayıya genişletilebilir. (a, b, c, . . ) = 1 ise a, b, c, sayıları. . . karşılıklı olarak basit. Örneğin:

Î ï ð å ä å í è å. (a 1 , a 2 , ...a n ) herhangi bir çiftin gcd'si varsa ikili asal sayılardır bire eşit(a i, a j) = 1,i ≠ j.

Örneğin: 12,17,11 yalnızca eş asal değil, aynı zamanda ikili olarak eş asaldır.

Teorem 1. Eğer a .b ise (a, b ) =b .

Ä î ê à ç à ò å ë ü ñ ò â î

B sayısı kendisinden büyük bir sayıya bölünemez. Bu nedenle b, èb'nin bir OBE'sidir.

Teorem 2. a =bq +r şeklinde bir temsil olsun (r'nin kalan olması şart değildir), o zaman (a, b) = (b, r) olsun.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Herhangi bir ortak böleni düşünün a èb c . Åñëa .c èb .c , tòt

Teorem 1.3 r .c'ye göre t.a.c aynı zamanda bèr'in ortak bölenidir. Herhangi bir ortak bölen a èb, bir ortak bölen b èr'dir.

2. Herhangi bir ortak bölen bèr, a'nın bölenidir. Bu, a, bèb, r ortak bölenlerinin çakıştığı anlamına gelir. Bu aynı zamanda GCD için de geçerlidir.

3. Öklid algoritması

Öklid algoritmasını kullanan herhangi bir a èb sayısı için bulunabilir

Algoritmanın giriş verisi a ,b N ve çıkış verisi (a, b ) =d N olsun.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R2q2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n+1	r n−1 = r nq n

Adım 1. a íàb'yi kalan a =bq 0 +r 1, aaa 0 ile bölün< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Adım 2. b íàr 1'i kalan b =r 1 q 1 +r 2 , aaa 0 ile bölün< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

Ve bu tamamen bölünene kadar devam eder. Eşitlik zincirinden

(a, b) = (b, r 1) = (r 1, r 2) = (r 2, r 3) =... = (r n− 2, r n− 1) = (r n− 1, r n) =rn

bundan, sıfır olmayan son kalan r n en büyük ortak olacak bölen =r n = (a, b ). Çünkü kalanlar azalırsa algoritma tamamlanır son sayı adımlar.

Öklid algoritmasına ilişkin teoremler

Teorem 1. İki sayının toplam çarpımı bu sayıların herhangi bir ortak bölenine bölünebilir

Åñëè (a, b ) =d , òî (a c , c b ) =d c , aaa c ortak bölen a èb .

Ä î ê à ç à ò å ë ü ñ ò â î

Â Öklid algoritmasının girdileri a, b и âñår bizi böleceğim. Aldık

Öklid algoritmasının giriş verileriyle kaydedilmesi a b

bir isim ver		c vec. Buradan anlaşılıyor
bir isim ver
	ve c	c'ye eşittir.

Teorem 2. İki sayıyı genel değerlerine bölersek, göreceli asal sayılar (a d, d b) = 1 elde ederiz.

Ä î ê à ç à ò å ë ü ñ ò â î

Teorem 3. Eğer

c yerine (Teorem 1'den) d'yi kullanırız.

(a, b) = 1, tòîc .b .ac . B

Ä î ê à ç à ò å ë ü ñ ò â î

Teorem 7.1'e göre görece asal a èb sayıları için ax +by = 1 şeklinde bir temsil vardır. Bu eşitliği c ile çarparsak, ac ·x +byc =c elde ederiz,

íî ac =bq ,bqx +byc =c ,b (qx +yc ) =c . Bu nedenle c .b .

Birkaç sayının GCD'si

(a1 , a2 , . . , an ) = dn (a1 , a2 ) = d2

(d 2 , a 3 ) =d 3

(d n− 1 , a n ) =d n

4. En az ortak kat

Î TANIM: İki sayının ortak katı a èb, bu sayıların her ikisine de bölünebilen bir sayıdır.

Î TANIM: En küçük ortak kat a èb'ye, bir èb'nin en küçük ortak katı (LCM) denir.

M .a èM .b olsun, o zaman M a èb'nin ortak katıdır. Bir èb'nin en küçük ortak katını şu şekilde gösteririz:

Teorem 1. İki sayının LCM'si orana eşit yaptıkları çalışmalar

=(a, ab b) .

Ä î ê à ç à ò å ë ü ñ ò â î

a èb sayılarının bazı ortak katlarını M ve ardından M ile gösterelim.

a èM .b . Ek olarak, d = (a, b),a =a ′ d,b =b ′ d ve (a ′, b ′) = 1. Bölünebilirliğin tanımı gereği M =a · k, 々k Z




					a′ dk				a′ k
					b'd				B'

a' b'ye bölünemez çünkü bunlar göreceli olarak asaldır, dolayısıyla Teorem 3.3'ten k .b'

k = b′ t=




M = a · k=
					(a, b)

bir èb'nin herhangi bir ortak katının biçimi. Ïðèt = 1M, a èb sayısının LCM'sidir.

Birkaç sayının LCM'si

[a1, a2, . . . , an ] = Mn [ a1 , a2 ] = M2

M3 = M4

Åñëè (a, b) = 1, tòî =ab. Pr (a ben , a j ) = 1,i ≠ j ,M =a 1 a 2 · . . . BİR.

5. Asal ve bileşik sayılar

Her sayı 1'e ve kendisine bölünebilir. Bu bölenlere önemsiz diyelim.

Tanım: Önemsiz olmayan bölenleri olmayan bir sayıya asal sayı denir. Önemsiz olmayan bir böleni olan bir sayıya bileşik sayı denir. 1 sayısı ne asal ne de bileşiktir.

Teorem 1. Herhangi bir doğal sayı a ve asal sayı p için

tatmin olur veya (a, p ) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

Asal sayı p'nin iki önemsiz böleni vardır. Olası

iki seçenek: a .p èëèa ̸ .p . Åñëèa ̸ .p ise, èp'nin OBEB'si 1'dir. Dolayısıyla (a, p ) = 1.

Teorem 2. Bir tam sayının birden farklı en küçük böleni, birden büyük, bir asal sayıdır.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , åäåp önemsiz olmayan en küçük bölendir. P'nin bileşik bir sayı olduğunu varsayalım. Bu şu anlama gelir:

böyle bir sayı s , ÷òîp .s , ancak o zaman a .s èp değildir en küçük bölen, bu durumla çelişiyor. T.o.p bir asal sayıdır.

Teorem 3. En küçük önemsiz olmayan bölen bileşik sayı kökünü aşamaz.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q b, q ≤ b, q2 ≤ bq= a, q ≤ a.

Eratostenes Eleği

Doğal sayılar kümesini yazalım

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

Birim: özel numara. Kalan sayılarla devam ediyoruz aşağıdaki gibi: Bir sayı alın, onu asal ilan edin ve katlarının üzerini çizin.

Mesela 2 asal sayıdır, ikinin katı olan sayıların üstünü çizeriz, dolayısıyla geriye çift sayı kalmaz. Aynısını üçümüz için de yapalım. 6, 9, 12, 15, 18 vb. sayıların üzerini çizmeniz gerekir. Geriye kalan tüm sayılar asaldır.

Teorem 4. Asal sayılar kümesi sonsuzdur. Kanıt

( 2, 3, 5, . . , P) sonlu bir asal sayılar kümesi olsun ve N = 2· 3· 5· olsun. . .·P +1.N hiçbir asal sayıya bölünemez çünkü bölündüğünde kalan 1'dir. Ancak Teorem 2'ye göre önemsiz olmayan en küçük bölen N bir asal sayıdır ̸ 2(, 3, 5, . . . , P). Sonuç olarak asal sayıların sayısı sonlu değil sonsuz bir kümedir.

6. Sayının kanonik biçimi

Teorem 1 (Aritmetiğin Temel Teoremi). 1'den başka herhangi bir sayı yalnızca asal sayıların çarpımı olarak gösterilebilir.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Varoluş.

Teorem 5.2'ye göre n sayısının asal böleni p 1'dir.

n n 1 = p 1 .

Benzer mantık n 1 sayısı için de geçerlidir

n2 = n1,p2

aaa s.2 asal bölen n 1. Ve böylece n i = 1 elde edilene kadar devam edeceğiz.

2. Benzersizlik.

N sayısının iki asal sayı ayrışımı olsun

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.

Genelliği kaybetmeden l ≤ s'yi kabul ediyoruz. Eğer sol taraf eşitlik 1'e bölünüyorsa sağdaki de 1'e bölünür. Bu, bazı q i =p 1 olduğu anlamına gelir. q 1 =p 1 olsun. Eşitliğin her iki tarafını da 1'e bölün

Aynı şekilde kabul edelim q2 = p2. İfade şeklini alana kadar bu işleme devam edeceğiz.

1 = ql +1 · . . . · qs.

Åñëè l< s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åsëè s =l , tòp i =q i äëÿi ve iki açılım çakışıyor. Teorem kanıtlandı.

Herhangi bir n N sayısı kanonik formda yazılabilir

n = p1 s 1 · . . . · lütfen s l ,

L p i asal sayılardır, s i N.

Kanonik gösterim, bir sayının tüm bölenlerini yazmanıza ve GCD ile LCM'yi belirlemenize olanak tanır.

N sayısının tüm c bölenleri şu şekildedir:

c = p1 ben 1 · p2 ben 2 . . . pl ben l, aaa ij .

GCD ve LCM'yi bulma

a ve b sayıları formda temsil edilsin

a = p1 s 1 · p2 s 2 · . . . · pl s l b= p1 t 1 · p2 t 2 · . . . · pl t l .

Bu gösterim, bazı s i и t i'lerin 0'a eşit olabilmesi açısından kanonik gösterimden farklıdır.

O zaman en büyük ortak bölen a èb

(a, b) = p1 dk (s 1 ,t 1 ) · p2 dk (s 2 ,t 2 ) · . . . · pl min (s l ,t l ),

ve en küçük ortak kat:

[ a, b] = p1 maksimum (s 1 ,t 1 ) · p2 maksimum (s 2 ,t 2 ) · . . . · pl max (s l ,t l ) .

Buradan (a, b)'nin herhangi bir a èb ortak bölenine bölünebildiği de açıktır.

7. İki bilinmeyenli doğrusal Diophantine denklemleri

Î Tanım: İki bilinmeyenli doğrusal bir Diophantine denklemi, şeklinde bir denklemdir.

balta + by= c,

burada a, b, c katsayıları ve bilinmeyenler x, y tam sayılardır, aa ve b aynı anda sıfıra eşit değildir.

Teorem 1 (GCD'nin doğrusal gösterimi üzerine). Herhangi bir (a, b) ((a, b) ≠ (0, 0)) sayı çifti için şöyle x, y Z, ÷òîax +by =(a, b) vardır.

Ä î ê à ç à ò å ë ü ñ ò â î

Sayı kümesini (ax + by) göz önünde bulundurun ve ondan minimumu seçin pozitif sayı d =ax 0 +by 0 .

d'nin b'nin böleni olduğunu kanıtlayalım.

d bölen olmasın, dolayısıyla b =d q +r, yani 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). Şu açıktır:

1) sayı r (ax +by) ;

2) r pozitiftir;

3)r< d .

Ancak d'nin bu kümedeki en küçük pozitif sayı olduğunu varsaydık, dolayısıyla r varsayımımız< d неверно, значитd делительb .

Benzer şekilde a .d olduğunu kanıtlayabiliriz.

Bütün bunlardan d'nin bir èb'nin ortak böleni olduğu sonucu çıkar.

A. (a, b)

Kostak, b. (a, b) d. (a, b), íîd a èb'nin ortak böleni olduğundan d ÍÎÄ a è b olur.

Teorem 2. ax +by =c denkleminin bir çözümü ancak ve ancak c'nin (a, b) ile bölünebilmesi durumunda vardır.

Ä î ê à ç à ò å ë ü ñ ò â î

1. İzin vermekC. (a, b), sonra Teorem 1'e göre balta+ile= (a, b). Denklemi şu şekilde çarpalım: C

( a,b )

A (A,xcB) + B (A,ycB) = C.

Bir çift sayı ( X0 , sen0 ) orijinal denklemin bir çözümü olacak

{ X0 = (a,bxc)sen0 = (a,byc).

2. Denklemin bir çözümü varsa, o zaman şunu kanıtlayalım: C. (a, b).

A. (a, b) , buradan, C( ile de bölünebilir olmalıdır) a, b).

B . ( a, b )