Кіріспе

Негізгі сандар шексіз көп, бұл – негізгі сандардың шексіздігі туралы теорема.

Евклид теоремасы – сандар теориясының негізгі мәлімдемесі, ол негізгі сандардың шексіз көп екенін көрсетеді. Оны алғаш рет Евклид өзінің "Элементтер" еңбегінде дәлелдеген. Теореманың бірнеше дәлелдемелері бар.

Евклидтің дәлелі

Евклид өзінің "Элементтер" еңбегінде (IX кітап, 20-ұсыным) жариялаған дәлелді ұсынды, ол осы жерде қайта айтылады. Кез келген шекті жай сандар тізімін қарастырайық: p1, p2, ..., pn. Осы тізімде жоқ кем дегенде бір қосымша жай санның бар екендігі көрсетілуі керек. P тізімдегі барлық жай сандардың көбейтіндісі болсын: P = p1p2…pn. q = P + 1 болсын. Онда q жай сан болады немесе болмайды:

Егер q жай сан болса, онда тізімде жоқ тағы бір жай сан бар, атап айтқанда, өзінің q-сы. Егер q жай сан болмаса, онда q-ны бөлетін p жай санның бір бөлшегі табылады. Егер осы p бөлшегі біздің тізімізде болса, онда ол P-ді бөлуі керек (өйткені P тізімдегі барлық сандардың көбейтіндісі); бірақ p сонымен қатар P + 1 = q-ны да бөледі, жоғарыда айтылғандай. Егер p P-ді де, q-ны да бөлетін болса, онда p олардың айырмасын да бөлуі керек, яғни (P + 1) – P немесе жай 1-ді. Бірақ ешқандай жай сан 1-ді бөле алмайды, сондықтан p тізімде бола алмайды. Бұл осы тізімнен басқа кем дегенде бір жай санның бар екенін білдіреді. Осылайша, кез келген шекті жай сандар тізіміне сол тізімде жоқ жай санның бар екендігі дәлелденді. Евклидтің түпнұсқа еңбегінде, ол жай сандардың кез келген тізімін жазу мүмкіндігі болмағандықтан, ол жиі қолданатын әдіске жүгінді, яғни жалпыланатын мысал әдісіне. Атап айтқанда, ол үш жай санды ғана таңдап алып, жоғарыда сипатталған жалпы әдіс арқылы әрқашан қосымша жай санды табуға болатынын дәлелдейді. Евклид оқырмандарының бастапқыда қанша жай сан таңдалғанына қарамастан, осыған ұқсас дәлелдің жұмыс істейтініне көз жеткізетінін болжайды. Евклид бұл нәтижені қарама-қайшылық арқылы дәлелдеген деген қате пікір жиі кездеседі, яғни бастапқыда қарастырылған шекті жиынның барлық жай сандарды қамтиды деген болжаммен басталады, бірақ шындығында бұл жағдай бойынша дәлелдеу, тікелей дәлелдеу әдісі. Философ Торкель Францен логика туралы кітабында былай дейді: "Евклидтің шексіз көп жай сан бар екендігін дәлелдеуі тікес емес дәлел емес [ ]. Бұл аргумент кейде оны "q1, qn – барлық жай сандар" деген болжаммен алмастыру арқылы тікес дәлел ретінде ұсынылады. Алайда, бұл болжам дәлелдеуде қолданылмағандықтан, мұндай ауыстырудың мәні жоқ".

Ердостың дәлелі

Пауль Эрдош арифметиканың негізгі теоремасына сүйенетін дәлел келтірді. Кез келген оң бүтін санды квадратсыз сан r және квадрат сан s^(2) көбейтіндісі түрінде бірегей түрде жіктеуге болады. Мысалы, N оң бүтін сан болсын, ал k – N-ге тең немесе одан кіші жай сандардың саны болсын. Бұл жай сандарды p1, …, pk деп атайық. Кез келген оң бүтін сан a, егер ол N-ге тең немесе одан кіші болса, мына түрде жазылуы мүмкін:

әр ei 0 немесе 1-ге тең болатын жағдайда. a-ның квадратсыз бөлігін құрудың 2^(k) тәсілі бар. Ал s^(2) N-нен артық болмайды, сондықтан осы түрде ең көп сандар жазылуы мүмкін. Басқаша айтқанда,

немесе, қайта реттесек, k, N-ге тең немесе одан кіші жай сандардың саны, N-нің квадратық түбірінен үлкен немесе оған тең. N кездейсоқ болғандықтан, N-ді тиісінше таңдау арқылы k-ны қалағанша үлкен етіп алуға болады.

Құрылыс арқылы дәлелдеу

Филип Сайдак мынадай конструкциялық дәлел келтірді, ол редукцио ад абсурдум немесе Евклид леммасын (егер жай сан p, ab-ны бөлетін болса, онда ол a-ны немесе b-ны бөлуі керек) пайдаланбайды. 1-ден үлкен кез келген табиғи санның кемінде бір жай көбейткіші бар, ал екі тікелей келесі сан, n және (n+1) ортақ көбейткіштерге ие емес болғандықтан, n(n+1) көбейтіндісінде n санынан көбірек әртүрлі жай көбейткіштер болады. Сондықтан, проник сандар тізбегі: 1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2, 3, 7}, 42×43 = 1806 {2, 3, 7, 43}, 1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · · жай сандардың шексіз өсіп келе жатқан жиындарының тізбесін ұсынады.

Нақты нәтижелер

Бұл бөлімдегі теоремалар Евклид теоремасын және басқа да теоремаларды бірдей дәлелдейді.

Дирихле теоремасы арифметикалық прогрессиялар туралы

Дирихле теоремасы бойынша, екі оң және өзара жай сандар a және d үшін, a + nd түріндегі шексіз көп жай сандар бар, мұнда n – оң бүтін сан. Басқаша айтқанда, d модулі бойынша a-ға конгруэнтті шексіз көп жай сандар бар.