Onlayn əsas nömrəni müəyyənləşdirin. Sadə ədədləri necə tapmaq olar
Bu yazıda biz araşdıracağıq sadə və mürəkkəb ədədlər. Əvvəlcə sadə və mürəkkəb ədədlərin təriflərini verəcəyik, həmçinin nümunələr verəcəyik. Bundan sonra bunu sübut edəcəyik sadə ədədlər sonsuz sayda. Sonra, biz sadə ədədlər cədvəlini yazacağıq və Eratosthenes ələk adlanan üsula xüsusi diqqət yetirərək, sadə ədədlər cədvəlini tərtib etmək üsullarını nəzərdən keçirəcəyik. Yekun olaraq, verilmiş ədədin sadə və ya mürəkkəb olduğunu sübut edərkən nəzərə alınmalı olan əsas məqamları qeyd edəcəyik.
Səhifə naviqasiyası.
Baş və Mürəkkəb ədədlər - Təriflər və Nümunələr
Sadə ədədlər və mürəkkəb ədədlər anlayışları birdən böyük olan ədədlərə aiddir. Belə tam ədədlər müsbət bölənlərinin sayından asılı olaraq sadə və mürəkkəb ədədlərə bölünür. Yəni başa düşmək üçün sadə və mürəkkəb ədədlərin tərifləri, siz bölənlərin və qatların nə olduğunu yaxşı başa düşməlisiniz.
Tərif.
Sadə ədədlər tam ədədlərdir, böyük vahidlərdir, yalnız iki müsbət bölən var, yəni özləri və 1.
Tərif.
Kompozit ədədlərən azı üç müsbət bölənləri olan böyük tam ədədlərdir.
Ayrı-ayrılıqda qeyd edirik ki, 1 rəqəmi nə sadə, nə də mürəkkəb ədədlərə aid deyil. Vahidin yalnız bir müsbət bölməsi var, o da 1 rəqəminin özüdür. Bu, 1 rəqəmini ən azı iki müsbət bölən olan bütün digər müsbət tam ədədlərdən fərqləndirir.
Müsbət tam ədədlərin olduğunu və birinin yalnız bir müsbət bölən olduğunu nəzərə alsaq, sadə və mürəkkəb ədədlərin qeyd olunan təriflərinin başqa düsturlarını verə bilərik.
Tərif.
Sadə ədədlər yalnız iki müsbət bölən olan natural ədədlərdir.
Tərif.
Kompozit ədədlər ikidən çox müsbət bölənləri olan natural ədədlərdir.
Qeyd edək ki, birdən böyük hər bir müsbət tam ədəd ya sadə, ya da mürəkkəb ədəddir. Başqa sözlə desək, nə sadə, nə də mürəkkəb olmayan tək bir tam ədəd yoxdur. Bu, 1 və a rəqəmlərinin həmişə istənilən a tam ədədinin bölənləri olduğunu bildirən bölünmə xüsusiyyətindən irəli gəlir.
Əvvəlki bənddəki məlumatlara əsaslanaraq, kompozit ədədlərin aşağıdakı tərifini verə bilərik.
Tərif.
Sadə olmayan natural ədədlər adlanır kompozit.
verək sadə və mürəkkəb ədədlərin nümunələri.
Mürəkkəb ədədlərə misal olaraq 6, 63, 121 və 6,697 ədədlərini göstərmək olar. Bu bəyanata da aydınlıq gətirilməlidir. 6 rəqəmi, 1 və 6 müsbət bölənlərindən əlavə, 2 və 3 bölənlərinə də malikdir, çünki 6 = 2 3 olduğundan, 6 həqiqətən mürəkkəb ədəddir. 63-ün müsbət amilləri 1, 3, 7, 9, 21 və 63 rəqəmləridir. 121 ədədi 11·11 hasilinə bərabərdir, ona görə də onun müsbət bölənləri 1, 11 və 121-dir. Və 6,697 ədədi mürəkkəbdir, çünki onun müsbət bölənləri, 1 və 6,697-dən başqa, 37 və 181 ədədləridir.
Bu fikri yekunlaşdıraraq bir fakta da diqqət çəkmək istərdim ki, sadə ədədlər və əlavə ədədlər eyni şeydən uzaqdır.
Sadə ədədlər cədvəli
Rahatlıq üçün sadə ədədlər sonrakı istifadə, sadə ədədlər cədvəli adlanan cədvəldə qeyd olunur. Aşağıdadır sadə ədədlər cədvəli 1000-ə qədər.
Məntiqi sual yaranır: “Niyə biz sadə ədədlər cədvəlini yalnız 1000-ə qədər doldurduq, bütün mövcud sadə ədədlərin cədvəlini yaratmaq mümkün deyilmi”?
Əvvəlcə bu sualın birinci hissəsinə cavab verək. Sadə ədədlərin istifadəsini tələb edən problemlərin əksəriyyəti üçün min daxilində olan sadə ədədlər kifayət edəcəkdir. Digər hallarda, çox güman ki, bəzi xüsusi həll üsullarına müraciət etməli olacaqsınız. Baxmayaraq ki, təbii ki, biz ixtiyari böyük sonlu tam ədədə qədər sadə ədədlər cədvəli yarada bilərik. müsbət rəqəm, istər 10.000, istərsə də 1.000.000.000, növbəti abzasda sadə ədədlərin cədvəllərinin tərtib edilməsi üsullarından danışacağıq, xüsusən də adlanan metodu təhlil edəcəyik.
İndi bütün mövcud sadə ədədlərin cədvəlini tərtib etməyin mümkünlüyünə (daha doğrusu, qeyri-mümkünlüyünə) baxaq. Bütün sadə ədədlərin cədvəlini yarada bilmərik, çünki sonsuz sayda sadə ədədlər var. Sonuncu müddəa aşağıdakı köməkçi teoremdən sonra sübut edəcəyimiz teoremdir.
Teorem.
Birdən böyük natural ədədin 1-dən başqa ən kiçik müsbət böləni sadə ədəddir.
Sübut.
Qoy a – natural ədəd, birdən böyük və b a ədədinin ən kiçik müsbət və vahid olmayan bölənidir. Ziddiyyətlə b-nin sadə ədəd olduğunu sübut edək.
Fərz edək ki, b mürəkkəb ədəddir. Onda b ədədinin (bunu b 1 qeyd edək) bölən var ki, bu da həm 1, həm də b-dən fərqlidir. Bölənin mütləq qiymətinin dividentin mütləq qiymətindən artıq olmadığını da nəzərə alsaq (bunu bölünmə xüsusiyyətlərindən bilirik), onda 1-ci şərt yerinə yetirilməlidir.
Şərtə görə a ədədi b-yə bölündüyündən və b-nin b 1-ə bölündüyünü söylədiyimiz üçün bölünmə anlayışı q və q 1 tam ədədlərinin mövcudluğundan danışmağa imkan verir ki, a=b q və b=b olsun. 1 q 1 , buradan a= b 1 ·(q 1 ·q) . Buradan belə nəticə çıxır ki, iki tam ədədin hasili tam ədəddir, onda a=b 1 ·(q 1 ·q) bərabərliyi b 1-in a ədədinin bölücü olduğunu göstərir. Yuxarıdakı bərabərsizlikləri nəzərə alaraq 1
İndi sonsuz sayda sadə ədədlərin olduğunu sübut edə bilərik.
Teorem.
Sonsuz sayda sadə ədədlər var.
Sübut.
Tutaq ki, belə deyil. Yəni fərz edək ki, cəmi n ədəd sadə ədəd var və bu sadə ədədlər p 1, p 2, ..., p n-dir. Gəlin göstərək ki, biz həmişə göstərilənlərdən fərqli sadə ədəd tapa bilərik.
p 1 ·p 2 ·…·p n +1-ə bərabər olan p ədədini nəzərdən keçirək. Aydındır ki, bu ədəd p 1, p 2, ..., p n sadə ədədlərinin hər birindən fərqlidir. Əgər p ədədi sadədirsə, teorem isbat olunur. Əgər bu ədəd mürəkkəbdirsə, onda əvvəlki teorem əsasında bu ədədin baş böləni var (onu p n+1 işarə edirik). Göstərək ki, bu bölən p 1, p 2, ..., p n ədədlərinin heç biri ilə üst-üstə düşmür.
Əgər bu belə olmasaydı, onda bölünmə xüsusiyyətlərinə görə p 1 ·p 2 ·…·p n hasilatı p n+1-ə bölünəcəkdi. Lakin p ədədi də p n+1-ə bölünür, p 1 ·p 2 ·…·p n +1 cəminə bərabərdir. Buradan belə nəticə çıxır ki, p n+1 bu cəminin birə bərabər olan ikinci həddini bölməlidir, lakin bu mümkün deyil.
Beləliklə, sübut edilmişdir ki, əvvəlcədən müəyyən edilmiş heç bir sadə ədədin sırasına daxil edilməyən yeni sadə ədəd həmişə tapıla bilər. Buna görə də sonsuz sayda sadə ədədlər var.
Deməli, sadə ədədlərin sonsuz sayda olmasına görə, sadə ədədlərin cədvəllərini tərtib edərkən siz həmişə özünüzü yuxarıdan hansısa ədədlə məhdudlaşdırırsınız, adətən 100, 1000, 10000 və s.
Eratosthenes ələk
İndi biz sadə ədədlər cədvəlinin yaradılması yollarını müzakirə edəcəyik. Tutaq ki, 100-ə qədər olan sadə ədədlər cədvəlini tərtib etməliyik.
Bu problemi həll etməyin ən bariz üsulu 2-dən başlayaraq 100-lə bitən müsbət tam ədədləri 1-dən böyük və yoxlanılan ədəddən kiçik olan müsbət bölənin varlığını ardıcıl olaraq yoxlamaqdır (bizim bildiyimiz bölünmə xüsusiyyətlərindən). bölənin mütləq dəyərinin dividendlərin mütləq dəyərindən artıq olmaması, sıfırdan fərqli). Əgər belə bölən tapılmazsa, yoxlanılan ədəd sadədir və o, sadə ədədlər cədvəlinə daxil edilir. Əgər belə bir bölən tapılarsa, o zaman sınaqdan keçirilən ədəd mürəkkəbdir; Bundan sonra, bölən varlığı üçün eyni şəkildə yoxlanılan növbəti nömrəyə keçid var.
İlk bir neçə addımı təsvir edək.
2 nömrəsi ilə başlayırıq. 2 rəqəminin 1 və 2-dən başqa müsbət bölənləri yoxdur. Buna görə də sadədir, ona görə də onu sadə ədədlər cədvəlinə daxil edirik. Burada demək lazımdır ki, 2 ən kiçik sadə ədəddir. Gəlin 3 nömrəyə keçək. Onun 1 və 3-dən başqa mümkün müsbət bölməsi 2 rəqəmidir. Lakin 3 2-yə bölünmür, ona görə də 3 sadə ədəddir və onu da sadə ədədlər cədvəlinə daxil etmək lazımdır. Gəlin 4 nömrəyə keçək. Onun 1 və 4-dən başqa müsbət bölənləri 2 və 3 rəqəmləri ola bilər, onları yoxlayaq. 4 rəqəmi 2-yə bölünür, ona görə də 4 mürəkkəb ədəddir və sadə ədədlər cədvəlinə daxil edilməsinə ehtiyac yoxdur. Nəzərə alın ki, 4 ən kiçik kompozit ədəddir. Gəlin 5 nömrəyə keçək. 2, 3, 4 ədədlərindən heç olmasa birinin onun bölən olub olmadığını yoxlayırıq. 5 2, 3 və ya 4-ə bölünmədiyi üçün o, sadədir və onu sadə ədədlər cədvəlinə yazmaq lazımdır. Sonra 6, 7 və s. 100-ə qədər rəqəmlərə keçid var.
Sadə ədədlər cədvəlini tərtib etmək üçün bu yanaşma idealdan uzaqdır. Bu və ya digər şəkildə onun mövcud olmaq hüququ var. Qeyd edək ki, tam ədədlər cədvəlinin qurulmasının bu üsulu ilə siz bölünmə meyarlarından istifadə edə bilərsiniz ki, bu da bölənlərin tapılması prosesini bir qədər sürətləndirəcək.
adlanan sadə ədədlər cədvəlini yaratmağın daha rahat yolu var. Adda mövcud olan "ələk" sözü təsadüfi deyil, çünki bu metodun hərəkətləri sadə olanları mürəkkəb olanlardan ayırmaq üçün Eratosthenes ələkindən tam ədədləri və böyük vahidləri "ələməyə" kömək edir.
50-yə qədər sadə ədədlər cədvəlini tərtib edərkən Eratosthenes ələkini hərəkətdə göstərək.
Əvvəlcə 2, 3, 4, ..., 50 rəqəmlərini sıra ilə yazın.
Yazılan ilk ədəd, 2, sadədir. İndi 2 nömrədən ardıcıl olaraq iki rəqəmlə sağa keçirik və tərtib olunan nömrələr cədvəlinin sonuna çatana qədər bu nömrələri kəsirik. Bu, ikiyə çox olan bütün nömrələri siləcək.
2-dən sonra xətt çəkilməyən ilk rəqəm 3-dür. Bu rəqəm əsasdır. İndi 3 nömrədən ardıcıl olaraq üç rəqəmlə sağa keçirik (artıq kəsilmiş nömrələri nəzərə alaraq) və onları kəsirik. Bu, üçə çox olan bütün nömrələri siləcək.
3-dən sonra xətt çəkilməyən ilk rəqəm 5-dir. Bu rəqəm əsasdır. İndi 5 rəqəmindən ardıcıl olaraq 5 rəqəmlə sağa keçirik (əvvəllər kəsilmiş nömrələri də nəzərə alırıq) və onları kəsirik. Bu, beşə çox olan bütün nömrələri siləcək.
Sonra, 7-nin, sonra 11-in qatlarının və s. olan ədədləri kəsirik. Artıq kəsiləcək nömrə qalmadıqda proses başa çatır. Aşağıda Eratosthenes ələkindən istifadə edərək əldə edilmiş 50-yə qədər sadə ədədlərin tamamlanmış cədvəli verilmişdir. Bütün çarpaz ədədlər sadədir və üzərindən xətt çəkilmiş bütün ədədlər mürəkkəbdir.
Eratosfen süzgəcindən istifadə edərək sadə ədədlər cədvəlinin tərtib edilməsi prosesini sürətləndirəcək bir teoremi də formalaşdıraq və sübut edək.
Teorem.
Mürəkkəb ədədin birdən fərqli olan ən kiçik müsbət bölən a-dan çox deyil, burada a-dandır.
Sübut.
Birdən fərqli olan a kompozit ədədinin ən kiçik bölənini b hərfi ilə işarə edək (b ədədi əvvəlki abzasın lap əvvəlində sübut edilmiş teoremdən aşağıdakı kimi sadədir). Onda q tam ədədi var ki, a=b·q (burada q tam ədədlərin vurulması qaydalarından irəli gələn müsbət tam ədəddir) və (b>q üçün b-nin a-nın ən kiçik bölücü olması şərti pozulur) , çünki a=q·b ) bərabərliyinə görə q həm də a ədədinin bölənidir. Bərabərsizliyin hər iki tərəfini müsbətə və birdən böyük tam ədədə vurmaqla (bunu etməyə icazə verilir) , hansı və .
Sübut edilmiş teorem Eratosthenes ələk ilə bağlı bizə nə verir?
Birincisi, b ədədinin çoxluğu olan mürəkkəb ədədlərin üstündən xətt çəkmək ona bərabər olan ədədlə başlamalıdır (bu bərabərsizlikdən irəli gəlir). Məsələn, ikiyə çarpan ədədlərin üstündən xətt çəkmək 4 rəqəmi ilə, üçə vurmaq 9 rəqəmi ilə, beşə vurmaq 25 rəqəmi və s. ilə başlamalıdır.
İkincisi, Eratosthenes ələkindən istifadə edərək n ədədinə qədər sadə ədədlər cədvəlini tərtib etmək, sadə ədədlərin qatları olan bütün mürəkkəb ədədlər -dən çox olmayan zaman tam hesab edilə bilər. Nümunəmizdə n=50 (çünki biz 50-yə qədər sadə ədədlər cədvəli hazırlayırıq) və buna görə də Eratosfen ələk 2, 3, 5 və 7 sadə ədədlərinin qatları olan bütün mürəkkəb ədədləri aradan qaldırmalıdır. arifmetik kvadrat kökdən 50-dən çox olmamalıdır. Yəni, 11, 13, 17, 19, 23 və s. 47-yə qədər olan sadə ədədləri axtarmağa və üzərindən xətt çəkməyə ehtiyacımız yoxdur, çünki onlar artıq kiçik sadə ədədlər 2-nin qatları kimi üzərindən xətt çəkiləcək. , 3, 5 və 7.
Bu ədəd sadədir, yoxsa kompozit?
Bəzi tapşırıqlar verilmiş ədədin sadə və ya mürəkkəb olduğunu öyrənməyi tələb edir. Ümumiyyətlə, bu tapşırıq sadə deyil, xüsusən yazısı əhəmiyyətli sayda simvoldan ibarət olan nömrələr üçün. Əksər hallarda, onu həll etmək üçün müəyyən bir yol axtarmaq lazımdır. Bununla belə, sadə hallar üçün düşüncə qatarına istiqamət verməyə çalışacağıq.
Əlbəttə ki, verilmiş ədədin kompozit olduğunu sübut etmək üçün bölünmə testlərindən istifadə etməyə cəhd edə bilərsiniz. Əgər, məsələn, bəzi bölünmə testi verilmiş ədədin birdən böyük müsbət tam ədədə bölündüyünü göstərirsə, onda ilkin ədəd mürəkkəbdir.
Misal.
898,989,898,989,898,989-un mürəkkəb ədəd olduğunu sübut edin.
Həll.
Bu ədədin rəqəmlərinin cəmi 9·8+9·9=9·17-dir. 9·17-ə bərabər olan ədəd 9-a bölündüyü üçün 9-a bölünmə ilə ilkin ədədin də 9-a bölündüyünü deyə bilərik. Buna görə də kompozitdir.
Bu yanaşmanın əhəmiyyətli çatışmazlığı ondan ibarətdir ki, bölünmə meyarları ədədin sadəliyini sübut etməyə imkan vermir. Buna görə də, bir ədədin sadə və ya mürəkkəb olduğunu yoxlamaq üçün test edərkən, hər şeyi fərqli etmək lazımdır.
Ən məntiqli yanaşma verilmiş ədədin bütün mümkün bölənlərini sınamaqdır. Mümkün bölənlərdən heç biri verilmiş ədədin həqiqi bölməsi deyilsə, bu ədəd sadə, əks halda isə mürəkkəb olacaqdır. Əvvəlki paraqrafda sübut edilmiş teoremlərdən belə çıxır ki, verilmiş a ədədinin bölənləri -dən çox olmayan sadə ədədlər arasında axtarılmalıdır. Beləliklə, verilmiş a ədədini ardıcıl olaraq sadə ədədlərə bölmək olar (onlar sadə ədədlər cədvəlindən rahat şəkildə götürülür), a ədədinin bölənini tapmağa çalışırlar. Bölən tapılarsa, a sayı mürəkkəbdir. -dən çox olmayan sadə ədədlər arasında a ədədinin bölməsi yoxdursa, a ədədi sadədir.
Misal.
Nömrə 11 723 sadə yoxsa mürəkkəb?
Həll.
11.723 ədədinin bölənlərinin hansı sadə ədədə qədər ola biləcəyini öyrənək. Bunu etmək üçün gəlin qiymətləndirək.
Bu olduqca aydındır , 200-dən 2 =40.000 və 11.723<40 000
(при необходимости смотрите статью ədədlərin müqayisəsi). Beləliklə, 11,723-ün mümkün əsas amilləri 200-dən azdır. Bu artıq işimizi xeyli asanlaşdırır. Əgər bunu bilməsəydik, onda 200-ə qədər deyil, 11.723-ə qədər olan bütün sadə ədədləri nəzərdən keçirməli olardıq.
İstəsəniz, daha dəqiq qiymətləndirə bilərsiniz. 108 2 =11,664 və 109 2 =11,881 olduğundan 108 2<11 723<109 2
, следовательно, . Beləliklə, 109-dan kiçik sadə ədədlərdən hər hansı biri potensial olaraq verilmiş 11.723 ədədinin sadə amilidir.
İndi 11.723 ədədini ardıcıl olaraq 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 sadə ədədlərə böləcəyik. , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . 11.723 ədədi yazılmış sadə ədədlərdən birinə bölünsə, o, mürəkkəb olacaqdır. Yazılan sadə ədədlərdən heç birinə bölünmürsə, ilkin ədəd sadədir.
Biz bütün bu monoton və monoton bölünmə prosesini təsvir etməyəcəyik. Dərhal deyək ki, 11.723
Məsələ 2.30
Natural ədədlərdən ibarət birölçülü A massivi verilmişdir. Massivdəki sadə ədədlərin sayını göstərin.
Əvvəlcə sadə ədədlərin nə olduğunu xatırlatmaq istəyirəm.
İndi tapşırığa keçək. Əslində bizə sadə ədədləri təyin edən proqram lazımdır. Elementləri çeşidləmək və onların dəyərlərini yoxlamaq texnologiya məsələsidir. Eyni zamanda, biz yalnız saymaq deyil, həm də massivin sadə nömrələrini göstərə bilərik.
Paskalda sadə ədədi necə təyin etmək olar
Paskalda ətraflı təhlili ilə həll alqoritmini təqdim edəcəyəm. Həllini C++ dilindəki nümunə proqramda görə bilərsiniz.
ƏHƏMİYYƏTLİ!
Bu, bir çox insanın səhv edə biləcəyi yerdir. Tərif sadə ədədin olduğunu söyləyir hamar iki fərqli bölücü Buna görə də, 1 rəqəmi sadə deyil (həmçinin sadə deyil, çünki sıfır istənilən ədədə bölünə bilər).
Biz özümüz yaradacağımız ədədin əsas olub-olmadığını yoxlayacağıq. Bu funksiya əgər rəqəm əsasdırsa, TRUE qaytaracaq.
Funksiyada əvvəlcə ədədin ikidən az olub olmadığını yoxlayacağıq. Əgər belədirsə, o, artıq sadə rəqəm deyil. Əgər rəqəm 2 və ya 3-dürsə, o, aydındır və heç bir əlavə yoxlama tələb olunmur.
Ancaq N sayı üçdən böyükdürsə, bu halda 2-dən (N-1) başlayaraq bütün mümkün bölənlər arasında dövr edəcəyik. Əgər N ədədi hər hansı bir bölməyə qalıqsız bölünürsə, o da sadə ədəd deyil. Bu halda biz döngəni kəsirik (çünki əlavə yoxlamağın mənası yoxdur) və funksiya FALSE qaytarır.
Ədədin özünə bölünüb-bölünmədiyini yoxlamağın mənası yoxdur (buna görə də dövrə yalnız N-1-ə qədər davam edir).
Mən burada funksiyanın özünü təqdim etməyəcəyəm - buna nümunə proqramlarda baxın.
Paskalda 2.30 məsələsinin həlli mytask; //**************************************************** **************** //SABİTLER //******************************** ********* ************************************ SAYI = 100; //Massivdəki elementlərin sayı //**************************************** *********** ************************ // FUNKSİYA VƏ PROSEDURLAR //************ ************ **************************************** ** //******** **************************************** * ******** // Ədədin sadə olub-olmadığını yoxlayır // INPUT: N - ədəd // ÇIXIŞ: TRUE - N ədədi sadədir, FALSE - sadə deyil //************ **************************************** **** IsPrimeNumber(N: WORD) : ; var i: ; başlamaq := TRUE;
N 0..3: başlanğıc N Çıxış; son;
Məqalədə sadə və mürəkkəb ədədlər anlayışları müzakirə olunur. Belə ədədlərin tərifləri misallarla verilmişdir. Sadə ədədlərin sayının qeyri-məhdud olduğunu sübut edirik və onu Eratosthenes metodundan istifadə edərək sadə ədədlər cədvəlində qeyd edəcəyik. Ədədin sadə və ya mürəkkəb olduğunu müəyyən etmək üçün dəlillər veriləcək.
Yandex.RTB R-A-339285-1
Baş və Mürəkkəb ədədlər - Təriflər və Nümunələr
Baş və mürəkkəb ədədlər müsbət tam ədədlər kimi təsnif edilir. Onlar birdən çox olmalıdır. Bölənlər də sadə və mürəkkəb bölünür. Mürəkkəb ədədlər anlayışını başa düşmək üçün əvvəlcə bölənlər və çoxalmalar anlayışlarını öyrənməlisiniz.
Tərif 1
Sadə ədədlər birdən böyük olan və iki müsbət bölən, yəni özləri və 1 olan tam ədədlərdir.
Tərif 2
Mürəkkəb ədədlər birdən böyük olan və ən azı üç müsbət bölənləri olan tam ədədlərdir.
Biri nə sadə, nə də mürəkkəb ədəddir. Onun yalnız bir müsbət bölən var, ona görə də bütün digər müsbət ədədlərdən fərqlidir. Bütün müsbət tam ədədlərə natural ədədlər deyilir, yəni hesablamada istifadə olunur.
Tərif 3
Sadə ədədlər yalnız iki müsbət bölən olan natural ədədlərdir.
Tərif 4
Kompozit nömrə ikidən çox müsbət bölən olan natural ədəddir.
1-dən böyük hər hansı bir ədəd sadə və ya mürəkkəbdir. Bölünmə xüsusiyyətindən əldə edirik ki, 1 və a ədədi həmişə istənilən a ədədi üçün bölən olacaq, yəni özünə və 1-ə bölünəcək. Tam ədədlərin tərifini verək.
Tərif 5
Sadə olmayan natural ədədlərə mürəkkəb ədədlər deyilir.
Sadə ədədlər: 2, 3, 11, 17, 131, 523. Onlar yalnız özlərinə və 1-ə bölünürlər. Mürəkkəb ədədlər: 6, 63, 121, 6697. Yəni 6 rəqəmini 2 və 3-ə, 63-ü isə 1, 3, 7, 9, 21, 63 və 121-i 11, 11-ə bölmək olar, yəni onun bölənləri 1, 11, 121 olacaq. 6697 rəqəmi 37 və 181-ə bölünür. Qeyd edək ki, sadə ədədlər və əlavə ədədlər anlayışları fərqli anlayışlardır.
Sadə ədədlərdən istifadəni asanlaşdırmaq üçün cədvəldən istifadə etməlisiniz:
Bütün mövcud natural ədədlər üçün cədvəl qeyri-realdır, çünki onların sonsuz sayda var. Rəqəmlər 10000 və ya 1000000000 ölçülərinə çatdıqda, Eratosthenes ələkindən istifadə etməyi düşünməlisiniz.
Son ifadəni izah edən teoremi nəzərdən keçirək.
Teorem 1
Birdən böyük natural ədədin 1-dən başqa ən kiçik müsbət böləni sadə ədəddir.
Sübut 1
Fərz edək ki, a 1-dən böyük natural ədəddir, b a-nın ən kiçik bir olmayan bölənidir. Ziddiyyət üsulu ilə b-nin sadə ədəd olduğunu sübut etmək lazımdır.
Fərz edək ki, b mürəkkəb ədəddir. Buradan əldə edirik ki, b üçün bölən var, o, 1-dən, eləcə də b-dən fərqlidir. Belə bölən b 1 kimi işarələnir. 1-ci şərt lazımdır< b 1 < b tamamlandı.
Şərtdən aydın olur ki, a bölünür b, b bölünür b 1, yəni bölünmə anlayışı aşağıdakı kimi ifadə edilir: a = b q və b = b 1 · q 1 , buradan a = b 1 · (q 1 · q) , burada q və q 1 tam ədədlərdir. Tam ədədlərin vurulması qaydasına əsasən, tam ədədlərin hasilinin a = b 1 · (q 1 · q) şəklində bərabərliyə malik tam ədəd olduğunu əldə edirik. Görünür ki, b 1 a ədədinin bölənidir. Bərabərsizlik 1< b 1 < b yox uyğun gəlir, çünki tapırıq ki, b a-nın ən kiçik müsbət və 1 olmayan bölənidir.
Teorem 2
Sonsuz sayda sadə ədədlər var.
Sübut 2
Ehtimal ki, biz sonlu sayda natural ədəd n götürüb onları p 1, p 2, …, p n kimi işarələyirik. Göstərilənlərdən fərqli sadə ədədin tapılması variantını nəzərdən keçirək.
p 1, p 2, ..., p n + 1-ə bərabər olan p ədədini nəzərə alaq. p 1, p 2, ..., p n formasının sadə ədədlərinə uyğun gələn ədədlərin hər birinə bərabər deyil. p sayı sadədir. Onda teorem isbat edilmiş sayılır. Əgər kompozitdirsə, onda p n + 1 qeydini götürməlisiniz və bölmənin p 1, p 2, ..., p n heç biri ilə üst-üstə düşmədiyini göstərin.
Əgər bu belə olmasaydı, məhsulun bölünmə xüsusiyyətinə əsaslanaraq p 1, p 2, ..., p n , pn + 1-ə bölünəcəyini tapırıq. Qeyd edək ki, p n + 1 ifadəsi p ədədinin bölünməsi p 1, p 2, ..., p n + 1 cəminə bərabərdir. Alırıq ki, p n + 1 ifadəsi Bu cəmin 1-ə bərabər olan ikinci həddi bölünməlidir, lakin bu mümkün deyil.
Görünür ki, verilmiş sadə ədədlərin istənilən sayda arasında istənilən sadə ədəd tapıla bilər. Buradan belə nəticə çıxır ki, sonsuz sayda sadə ədədlər var.
Sadə ədədlər çox olduğundan, cədvəllər 100, 1000, 10000 və s. rəqəmləri ilə məhdudlaşır.
Sadə ədədlər cədvəlini tərtib edərkən nəzərə almalısınız ki, belə bir tapşırıq 2-dən 100-ə qədər rəqəmlərin ardıcıl yoxlanılmasını tələb edir. Bölən yoxdursa, o, birləşirsə, cədvəldə qeyd olunur, o zaman cədvələ daxil edilmir.
Gəlin buna addım-addım baxaq.
Əgər 2 rəqəmi ilə başlasanız, onda onun yalnız 2 bölən var: 2 və 1, yəni onu cədvələ daxil etmək olar. 3 nömrəsi ilə eynidir. 4 rəqəmi mürəkkəbdir; 2 və 2-yə parçalanmalıdır. 5 rəqəmi əsasdır, yəni onu cədvəldə qeyd etmək olar. Bunu 100 rəqəminə qədər edin.
Bu üsul əlverişsiz və vaxt aparır. Cədvəl yaratmaq mümkündür, ancaq çox vaxt sərf etməli olacaqsınız. Bölünmə meyarlarından istifadə etmək lazımdır ki, bu da bölənlərin tapılması prosesini sürətləndirəcək.
Eratosthenes ələkindən istifadə üsulu ən əlverişli hesab olunur. Aşağıdakı nümunə cədvəllərinə baxaq. Başlamaq üçün 2, 3, 4, ..., 50 rəqəmləri yazılır.
İndi 2-yə çoxlu olan bütün nömrələri silmək lazımdır. Ardıcıl cızıqları yerinə yetirin. Belə bir cədvəl alırıq:
Biz 5-in qatları olan nömrələri kəsməyə davam edirik. Biz əldə edirik:
7, 11-in qatları olan ədədləri kəsin. Nəhayət, masa belə görünür
Gəlin teoremin tərtibinə keçək.
Teorem 3
Əsas a ədədinin ən kiçik müsbət və 1 olmayan bölməsi a-dan çox deyil, burada a verilmiş ədədin arifmetik köküdür.
Sübut 3
a kompozit ədədinin ən kiçik bölənini b işarələmək lazımdır. q tam ədədi var, burada a = b · q və bizdə b ≤ q var. Formanın qeyri-bərabərliyi qəbuledilməzdir b > q,çünki şərt pozulur. b ≤ q bərabərsizliyinin hər iki tərəfi 1-ə bərabər olmayan istənilən müsbət b ədədinə vurulmalıdır. Biz b · b ≤ b · q alırıq, burada b 2 ≤ a və b ≤ a.
Sübut edilmiş teoremdən aydın olur ki, cədvəldə ədədlərin üstündən xətt çəkmək, b 2-yə bərabər olan və b 2 ≤ a bərabərsizliyini təmin edən ədəddən başlamaq lazım olduğuna gətirib çıxarır. Yəni, əgər 2-yə çarpan ədədləri kəsirsinizsə, onda proses 4-dən, 3-ün qatları isə 9-dan başlayır və s. 100-ə qədər davam edir.
Eratosfen teoremindən istifadə edərək belə bir cədvəl tərtib etmək onu deməyə əsas verir ki, bütün mürəkkəb ədədlərin üstündən xətt çəkildikdə n-dən çox olmayan sadə ədədlər qalacaq. N = 50 olan nümunədə bizdə n = 50 var. Buradan əldə edirik ki, Eratosthenes süzgəci dəyəri 50-nin kökünün dəyərindən çox olmayan bütün mürəkkəb ədədləri süzür. Rəqəmlərin axtarışı üzərindən xətt çəkməklə həyata keçirilir.
Həll etməzdən əvvəl ədədin sadə və ya mürəkkəb olduğunu öyrənməlisiniz. Bölünmə meyarlarından tez-tez istifadə olunur. Buna aşağıdakı nümunədə baxaq.
Misal 1
898989898989898989 ədədinin mürəkkəb olduğunu sübut edin.
Həll
Verilmiş ədədin rəqəmlərinin cəmi 9 8 + 9 9 = 9 17-dir. Bu o deməkdir ki, 9 · 17 rəqəmi 9-a bölünmə testinə əsasən 9-a bölünür. Bundan belə nəticə çıxır ki, o, kompozitdir.
Bu cür əlamətlər ədədin sadəliyini sübut edə bilməz. Doğrulama tələb olunarsa, digər tədbirlər görülməlidir. Ən uyğun yol rəqəmləri sadalamaqdır. Proses zamanı siz sadə və mürəkkəb ədədləri tapa bilərsiniz. Yəni, rəqəmlər bir dəyərdən çox olmamalıdır. Yəni, a sayı əsas amillərə bölünməlidir. bu təmin olunarsa, onda a ədədini sadə hesab etmək olar.
Misal 2
11723 mürəkkəb və ya sadə ədədini təyin edin.
Həll
İndi 11723 rəqəminin bütün bölənlərini tapmaq lazımdır. Qiymətləndirmək lazımdır 11723 .
Buradan görərik ki, 11723< 200 , то 200 2 = 40 000 , və 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
11723 rəqəmini daha dəqiq qiymətləndirmək üçün 108 2 = 11 664 ifadəsini yazmalısınız və 109 2 = 11 881 , Bu 108 2 < 11 723 < 109 2 . Buradan belə çıxır ki, 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Genişləndirən zaman tapırıq ki, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 , 89 , 97 , 101 , 103 , 107 hamısı sadə ədədlərdir. Bütün bu prosesi bir sütuna bölmək kimi təsvir etmək olar. Yəni 11723-ü 19-a bölün. 19 rəqəmi onun amillərindən biridir, çünki biz qalıqsız bölmə alırıq. Bölməni sütun şəklində təqdim edək:
Buradan belə çıxır ki, 11723 mürəkkəb ədəddir, çünki özünə və 1-ə əlavə olaraq 19-a bölən var.
Cavab: 11723 mürəkkəb ədəddir.
Mətndə xəta görsəniz, onu vurğulayın və Ctrl+Enter düymələrini basın
İlyanın cavabı düzgündür, lakin çox təfərrüatlı deyil. 18-ci əsrdə, yeri gəlmişkən, biri hələ də sadə rəqəm hesab olunurdu. Məsələn, Eyler və Qoldbax kimi böyük riyaziyyatçılar. Qoldbax minilliyin yeddi problemindən birinin - Qoldbax fərziyyəsinin müəllifidir. Orijinal tənzimləmə hər bir cüt ədədin iki sadə ədədin cəmi kimi göstərilə biləcəyini bildirir. Üstəlik, ilkin olaraq 1 sadə ədəd kimi nəzərə alınıb və biz bunu görürük: 2 = 1+1. Bu, fərziyyənin orijinal formalaşdırılmasını təmin edən ən kiçik nümunədir. Daha sonra düzəliş edildi və formula müasir bir forma aldı: "4-dən başlayan hər bir cüt ədəd iki sadə ədədin cəmi kimi göstərilə bilər."
Tərifi xatırlayaq. Sadə ədəd yalnız 2 müxtəlif təbii böləni olan p natural ədədidir: p özü və 1. Tərifdən nəticə: p sadə ədədinin yalnız bir sadə bölməsi var - p-nin özü.
İndi fərz edək ki, 1 sadə ədəddir. Tərifə görə, sadə ədədin yalnız bir sadə bölməsi var - özü. Onda belə çıxır ki, 1-dən böyük istənilən sadə ədəd ondan fərqli (1-ə) sadə ədədə bölünür. Amma iki fərqli sadə ədədi bir-birinə bölmək olmaz, çünki əks halda onlar sadə ədədlər deyil, mürəkkəb ədədlərdir və bu tərifə ziddir. Bu yanaşma ilə belə çıxır ki, yalnız 1 sadə ədəd var - vahidin özü. Amma bu absurddur. Deməli, 1 sadə ədəd deyil.
1, eləcə də 0 ədədlərin başqa sinfini - cəbr sahəsinin bəzi alt çoxluğunda n-ar əməliyyatlarına münasibətdə neytral elementlər sinfini təşkil edir. Bundan əlavə, toplama əməliyyatına gəldikdə, 1 həm də tam ədədlərin halqası üçün yaradan elementdir.
Bunu nəzərə alaraq, digər cəbri strukturlarda sadə ədədlərin analoqlarını tapmaq çətin deyil. Tutaq ki, 1: 2, 4, 8, 16, ... və s.-dən başlayaraq 2-nin səlahiyyətlərindən formalaşmış multiplikativ qrupumuz var. 2 burada formalaşdırıcı element kimi çıxış edir. Bu qrupdakı sadə ədəd ən kiçik elementdən böyük və yalnız özünə və ən kiçik elementə bölünən ədəddir. Qrupumuzda yalnız 4-də belə xüsusiyyətlər var. Qrupumuzda daha sadə rəqəmlər yoxdur.
Qrupumuzda 2 də sadə ədəd olsaydı, onda birinci abzasa baxın - yenə belə çıxır ki, yalnız 2 sadə ədəddir.
Bölənlərin sadalanması. Tərifinə görə, sayı n yalnız 2-yə və 1 və özündən başqa digər tam ədədlərə bərabər bölünmədikdə sadədir. Yuxarıdakı düstur lazımsız addımları aradan qaldırır və vaxta qənaət edir: məsələn, ədədin 3-ə bölünüb-bölünmədiyini yoxladıqdan sonra onun 9-a bölünüb-bölünmədiyini yoxlamağa ehtiyac yoxdur.
- mərtəbə(x) funksiyası x-i x-dən kiçik və ya bərabər olan ən yaxın tam ədədə yuvarlaqlaşdırır.
Modul arifmetika haqqında məlumat əldə edin.“x mod y” əməliyyatı (mod latın “modulo”, yəni “modul” sözünün abbreviaturasıdır) “x-i y-yə bölmək və qalanı tapmaq” deməkdir. Başqa sözlə, modul arifmetikada müəyyən bir dəyərə çatdıqdan sonra deyilir modul, ədədlər yenidən sıfıra “çevrilir”. Məsələn, saat 12 modulu ilə vaxtı saxlayır: 10, 11 və 12-ni göstərir və sonra 1-ə qayıdır.
- Bir çox kalkulyatorda mod açarı var. Bu bölmənin sonunda bu funksiyanın böyük ədədlər üçün əl ilə necə qiymətləndirilməsi göstərilir.
Fermatın Kiçik Teoreminin tələləri haqqında məlumat əldə edin. Test şərtlərinə cavab verməyən bütün nömrələr kompozitdir, qalan nömrələr yalnızdır ehtimal sadə kimi təsnif edilir. Yanlış nəticələrin qarşısını almaq istəyirsinizsə, axtarın n"Carmichael nömrələri" (bu testi təmin edən mürəkkəb nömrələr) və "yalançı əsas Fermat ədədləri" (bu nömrələr yalnız bəzi dəyərlər üçün test şərtlərinə cavab verir) siyahısında a).
Əgər əlverişlidirsə, Miller-Rabin testindən istifadə edin. Bu metodu əl ilə hesablamaq kifayət qədər çətin olsa da, kompüter proqramlarında tez-tez istifadə olunur. O, məqbul sürəti təmin edir və Fermat metodundan daha az səhv yaradır. Dəyərlərin ¼-dən çoxu üçün hesablamalar aparılarsa, kompozit ədəd sadə ədəd kimi qəbul edilməyəcək. a. Əgər təsadüfi olaraq müxtəlif dəyərləri seçsəniz a və onların hamısı üçün test müsbət nəticə verəcək, biz kifayət qədər yüksək dərəcədə əminliklə güman edə bilərik ki, n sadə ədəddir.
Böyük ədədlər üçün modul arifmetikadan istifadə edin.Əlinizdə modlu bir kalkulyator yoxdursa və ya kalkulyatorunuz belə böyük rəqəmləri idarə etmək üçün nəzərdə tutulmayıbsa, hesablamaları asanlaşdırmaq üçün güclərin və modul arifmetikanın xüsusiyyətlərindən istifadə edin. Aşağıda bir nümunədir 3 50 (\displaystyle 3^(50)) mod 50:
- İfadəni daha rahat formada yenidən yazın: mod 50. Əllə hesablamalar apararkən əlavə sadələşdirmələr lazım ola bilər.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Burada modul vurmanın xassəsini nəzərə aldıq.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25))) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
- = 1849 (\displaystyle =1849) mod 50.
- = 49 (\displaystyle =49).