Էվկլիդեսի թեորեմ
Էվկլիդեսի թեորեմ, թվերի տեսության հիմնարար պնդում, պարզ թվերի անսահման շատ լինելու մասին։ Այն առաջին անգամ ապացուցվել է Էվկլիդեսի կողմից իր «Տարրեր» աշխատությունում։ Թեորեմի մի քանի ապացույցներ կան։
Էվկլիդեսի ապացույցը
[խմբագրել | խմբագրել կոդը]Էվկլիդեսն առաջարկել է ապացույց, որը հրապարակվել է իր «Տարրեր» աշխատության մեջ (Գիրք IX, Առաջարկ 20)[1], որը վերափոխված է այստեղ[2]։
Դիտարկենք պարզ թվերի ցանկացած վերջավոր ցուցակ p1, p2, ..., pn.։ Կցուցադրվի, որ կա առնվազն մեկ լրացուցիչ պարզ թիվ, որը չկա այս ցանկում։ Թող P լինի ցուցակի բոլոր պարզ թվերի արտադրյալը. P = p1p2...pn. Թող q = P + 1. Այնուհետև q-ն կամ պարզ է, կամ ոչ.
- Եթե q-ն պարզ է, ապա կա առնվազն ևս մեկ պարզ, որը ցուցակում չկա, այն է՝ ինքնին q:
- Եթե q-ն պարզ չէ, ապա պարզ որոշ p գործակիցը բաժանվում է q-ին։ Եթե այս p գործակիցը լիներ մեր ցուցակում, ապա այն կբաժանվեր P-ին (քանի որ P-ն ցուցակի յուրաքանչյուր թվի արտադրյալն է), բայց p-ն նաև բաժանվում է P + 1 = q, ինչպես արդեն նշվեց։ Եթե p-ն բաժանվում է P-ին և նաև q-ն, ապա p-ն նույնպես պետք է բաժանվի տարբերությանը[3] երկու թվերից, որը (P + 1) − P կամ պարզապես 1։ Քանի որ ոչ մի պարզ թիվ չի բաժանվում 1-ին, p չի կարող լինել ցուցակում։ Սա նշանակում է, որ ցուցակում նշվածներից դուրս առնվազն ևս մեկ պարզ թիվ կա։ Սա ապացուցում է, որ պարզ թվերի յուրաքանչյուր վերջավոր ցուցակի համար կա մի պարզ թիվ, որը չկա ցուցակում[4]։ Բնօրինակ աշխատության մեջ, քանի որ Էվկլիդեսը չուներ պարզ թվերի կամայական ցուցակ գրելու միջոց, նա օգտագործեց մի մեթոդ, որը նա հաճախ էր կիրառում, այսինքն՝ ընդհանրացվող օրինակի մեթոդը։ Մասնավորապես, նա ընտրում է ընդամենը երեք պարզ թվեր և օգտագործելով վերը նկարագրված ընդհանուր մեթոդը, ապացուցում է, որ միշտ կարող է գտնել լրացուցիչ պարզ թիվ։ Էվկլիդեսը ենթադրում է, որ իր ընթերցողները համոզված են, որ նմանատիպ ապացույցը կգործի, անկախ նրանից, թե քանի պարզ թիվ են սկզբնապես ընտրված[5]։
Հաճախ սխալմամբ հաղորդվում է, որ Էվկլիդեսը ապացուցել է այս արդյունքը հակասությամբ, որը սկսվում է այն ենթադրությունից, որ ի սկզբանե դիտարկված վերջավոր բազմությունը պարունակում է բոլոր պարզ թվերը[6], թեև դա իրականում ուղղակի ապացուցման մեթոդ ՝: Փիլիսոփա Տորկել Ֆրանցենը տրամաբանության մասին գրքում նշում է. «Էվկլիդեսի ապացույցի մեջ կան անսահման շատ պարզ թվեր, անուղղակի ապացույց չէ։ Փաստարկը երբեմն ձևակերպվում է որպես անուղղակի ապացույց՝ այն փոխարինելով «Ենթադրենք q1» ենթադրությամբ։, ... qn-ը բոլոր պարզերն են։ Այնուամենայնիվ, քանի որ այս ենթադրությունը նույնիսկ չի օգտագործվում ապացուցման մեջ, վերաձևակերպումն անիմաստ է[7]։
Վարիացիաներ
[խմբագրել | խմբագրել կոդը]Էվկլիդեսի ապացույցի մի քանի ձևակերպումներ կան.
n-ի ֆակտորիալ n! դրական ամբողջ թվի համար n-ը բաժանվում է 2-ից մինչև n-ի յուրաքանչյուր ամբողջ թվի, քանի որ այն բոլորի արտադրյալն է։ Հետևաբար, n! + 1-ը չի բաժանվում 2-ից մինչև n ամբողջ թվերից որևէ մեկի վրա, ներառյալ (յուրաքանչյուրի վրա բաժանելու դեպքում տալիս է 1 մնացորդ)։ Ուստի n! + 1-ը պարզ է կամ բաժանվում է n-ից մեծ պարզ թվի։ Երկու դեպքում էլ, յուրաքանչյուր n դրական ամբողջ թվի համար կա առնվազն մեկ պարզ, որը մեծ է n-ից։ Եզրակացություն, պարզ թվերն անսահման են[8]։
Էյլերի ապացույցը
[խմբագրել | խմբագրել կոդը]Մեկ այլ ապացույց՝ շվեյցարացի մաթեմատիկոս Լեոնհարդ Էյլերի կողմից, հիմնված է թվաբանության հիմնարար թեորեմի վրա. յուրաքանչյուր ամբողջ թիվ ունի եզակի պարզ ֆակտորիալ։ Այն, ինչ գրել է Էյլերը (ոչ այս ժամանակակից նշումով և, ի տարբերություն ժամանակակից ստանդարտների, գումարների և արտադրյալների փաստարկները չսահմանափակելով ամբողջ թվերի որևէ վերջավոր բազմությամբ) համարժեք է այն հայտարարությանը, որ մենք ունենք[9]։
որտեղ նշանակում է k առաջին պարզ թվերի բազմություն և այն դրական ամբողջ թվերի բազմությունն է, որոնց հիմնական գործակիցները բոլորը են։
Դա ցույց տալու համար արտադրյալի յուրաքանչյուր գործակիցը ընդլայնվում է որպես երկրաչափական շարք և բաշխում է արտադրյալը գումարի վրա (սա Էյլերի բանաձևի հատուկ դեպքն է Ռիմանի զետա ֆունկցիայի համար)։
Նախավերջին գումարում պարզ թվերի յուրաքանչյուր արտադրյալ նշվում է ուղիղ մեկ անգամ, և հետևաբար վերջին հավասարությունը ճշմարիտ է թվաբանության հիմնարար թեորեմով։ Այս արդյունքը իր առաջին հետևանքում Էյլերը նշում է նման նշանով « բացարձակ անսահմանություն » և գրում, հայտարարության մեջ անսահման գումարը հավասար է , որին, հետևաբար, հավասար է նաև անսահման արտադրյալը (ժամանակակից տերմինաբանության մեջ դա համարժեք է նրան, որ մասնակի գումարը մինչև 𝑥 ներդաշնակ շարքը շեղվում է ասիմպտոտիկ նման 𝑥) Այնուհետև իր երկրորդ եզրակացության մեջ Էյլերը նշում է, որ
համընկնում է 2-ի վերջավոր արժեքին, և որ հետևաբար կան ավելի շատ պարզ թվեր, քան քառակուսիներ։ Սա ապացուցում է Էվկլիդեսի թեորեմը[10]։
Նույն աշխատության մեջ (Թեորեմ 19) Էյլերը փաստորեն օգտագործեց վերը նշված հավասարությունը՝ ապացուցելու թեորեմը, որն իրենից առաջ անհայտ էր, այն է, որ շարքը.
դիֆերենտ է, որտեղ P-ն նշանակում է բոլոր պարզ թվերի բազմություն (Էյլերը գրում է, որ անսահման գումարը , որը ժամանակակից տերմինաբանությամբ համարժեք է ասելու, որ մասնակի գումարը մինչև 𝑥 շարքն ասիմպտոտիկ է ).
Էրդոսի ապացույցը
[խմբագրել | խմբագրել կոդը]Պոլ Էրդոսը ապացույց է տվել[11] որը նույնպես հիմնված է թվաբանության հիմնարար թեորեմի վրա։ Յուրաքանչյուր դրական ամբողջ թիվ ունի եզակի ֆակտորիալ առանց r քառակուսու և s2քառակուսի թվերի։ Օրինակ, 75,600 = 24 33 52 71 = 21 ⋅ 602.
Թող N լինի դրական ամբողջ թիվ, և թող K-ն լինի N-ից փոքր կամ հավասար պարզ թվեր։ Այդ պարզ թվերն անվանեք p1, ..., pk: Ցանկացած դրական ամբողջ թիվ, որը փոքր է կամ հավասար է N-ին, այնուհետև կարելի է գրել հետյալ ձևով
որտեղ յուրաքանչյուր ei կամ 0 է կամ 1։ Կան 2k a-ի քառակուսի ազատ մասի ձևավորման եղանակներ. Եվ s2 կարող է լինել առավելագույն N։ Այլ կերպ ասած,
Կամ, վերադասավորելով k, պարզ պարզերի թիվը N-ից փոքր կամ հավասար է, մեծ կամ հավասար է 12log2 N. Քանի որ N-ը կամայական էր, k-ն կարող է լինել այնքան մեծ, որքան ցանկանում եք՝ համապատասխանաբար ընտրելով N:
Ֆուրստենբերգի ապացույցը
[խմբագրել | խմբագրել կոդը]1950-ականներին Հիլել Ֆուրստենբերգը ներկայացրեց հակասության ապացույց՝ օգտագործելով կետային տոպոլոգիա[12]։
Սահմանենք Z ամբողջ թվերի վրա տոպոլոգիա, որը կոչվում է հավասարաչափ տարածված ամբողջ թվերի տոպոլոգիա՝ U ⊆ Z ենթաբազմությունը հայտարարելով բաց բազմություն, այն և միայն այն դեպքում, եթե դա դատարկ բազմություն է, ∅, կամ թվաբանական հաջորդականությունների միություն S( a, b) (a ≠ 0-ի համար), որտեղ
Այնուհետև հակասություն է բխում այն հատկությունից, որ ամբողջ թվերի վերջավոր բազմությունը չի կարող բաց լինել, և այն հատկությունը, որով S(a, b) հիմնական բազմությունները և բաց են և փակ, քանի որ
չի կարող փակվել, քանի որ դրա լրացումը վերջավոր է, բայց փակ է, քանի որ այն փակ բազմությունների վերջավոր նազմություն է։
Վերջին ապացույցները
[խմբագրել | խմբագրել կոդը]Ներառում-բացառում սկզբունքի օգտագործմամբ ապացույց
[խմբագրել | խմբագրել կոդը]Խուան Պաբլո Պինասկոն գրել է հետևյալ ապացույցը[13]
Թող p1, ..., pN լինի ամենափոքր N պարզ թվերը։ Այնուհետև ներառում-բացառման սկզբունքով x-ից փոքր կամ հավասար դրական ամբողջ թվերը, որոնք բաժանվում են այդ պարզ թվերից մեկի վրա.
Բաժանելով x-ի և թույլ տալով x → ∞ տալիս է
Սա կարելի է գրել այսպես
Եթե p1, ..., pN այլ թվեր չկան,ապա (1) արտահայտությունը հավասար է և (2)-ի արտահայտությունը հավասար է 1-ի, բայց ակնհայտորեն (3)-ի արտահայտությունը հավասար չէ 1-ի։ Հետևաբար, պետք է ավելի շատ պարզ թվեր լինեն, քան p1, ..., pN։
Լեժանդրի բանաձևով ապացույց
[խմբագրել | խմբագրել կոդը]2010 թվականին Ջունհո Պիտեր Ուանգը հակասականորեն հրապարակեց հետևյալ ապացույցը[14]։ Թող K-ն լինի ցանկացած դրական ամբողջ թիվ։ Այնուհետև Լեժանդրի բանաձևով (երբեմն վերագրվում է դե Պոլինյակին)
որտեղ
Բայց եթե գոյություն ունեն միայն վերջավոր թվով պարզ թվեր, ապա
(կոտորակի համարիչը կմեծանա եզակի էքսպոնենցիալ, մինչդեռ Ստերլինգի մոտավորմամբ հայտարարն աճում է ավելի արագ, քան առանձին էքսպոնենցիալ), հակասելով այն փաստին, որ յուրաքանչյուր k-ի համար համարիչը մեծ է կամ հավասար է հայտարարին։
Շինարարությամբ ապացույց
[խմբագրել | խմբագրել կոդը]Ֆիլիպ Սաիդակը շինարարությամբ տվել է հետևյալ ապացույցը, որը չի օգտագործում[15] կամ Էվկլիդեսի լեմման (որ եթե պարզ 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}, · · ·
ապահովում է պարզ թվերի անսահմանափակ աճող բազմությունների հաջորդականություն։
Անսեղմելիության մեթոդի կիրառմամբ ապացույց
[խմբագրել | խմբագրել կոդը]Ենթադրենք, եղել են միայն k պարզ թվեր (p1, ..., pk)։ Թվաբանության հիմնարար թեորեմի համաձայն՝ ցանկացած դրական ամբողջ n թիվ կարող է ներկայացվել որպես որտեղ ոչ բացասական ամբողջ թվերի ցուցիչները ei-ի հետ միասին պարզ թվերի վերջավոր չափերի ցուցակը բավարար են թիվը վերակառուցելու համար։ Քանի որ բոլոր i-ի համար հետևում է, որ ես բոլորի համար (որտեղ lg նշանակում է 2 հիմքով լոգարիթմ)։ Սա տալիս է հետևյալ չափի n-ի կոդավորումը (օգտագործելով մեծ O նշում).
- բիթ։
Սա շատ ավելի արդյունավետ կոդավորում է, քան n-ն ուղղակիորեն երկուական տարբերակով ներկայացնելը, որը տևում է բիթ։ Տվյալների անկորուստ սեղմման հաստատված արդյունքը նշում է, որ ընդհանուր առմամբ չի կարելի սեղմել տեղեկատվության N բիթերը N-ից պակաս բիթերի։ Վերոնշյալ ներկայացումը խիստ խախտում է, երբ n-ը բավականաչափ մեծ է, քանի որ . Ուստի պարզ թվերը չպետք է վերջավոր լինեն[16]։
Ավելի ուժեղ արդյունքներ
[խմբագրել | խմբագրել կոդը]Այս բաժնի թեորեմները միաժամանակ ենթադրում են Էվկլիդեսի թեորեմը և այլ արդյունքներ։
Դիրիխլեի թեորեմը թվաբանական առաջընթացների մասին
[խմբագրել | խմբագրել կոդը]Դիրիխլեի թեորեմն ասում է, որ a-ի և d-ի ցանկացած երկու դրական ընդհանուր ամբողջ թվերի համար կան a + nd ձևի անսահման շատ պարզ թվեր, որտեղ n-ը նույնպես դրական ամբողջ թիվ է։ Այլ կերպ ասած, կան անսահման շատ պարզեր, որոնք ձգտում են մոդուլ d-ին։
Պարզ թվերի թեորեմ
[խմբագրել | խմբագրել կոդը]Թող π(x) լինի պարզ հաշվելու ֆունկցիան, որը տալիս է պարզ թիվը x-ից փոքր կամ հավասար ցանկացած իրական թվի համար։ Այնուհետև պարզ թվերի թեորեմը նշում է, որ x / log x-ը լավ մոտարկում է π(x-ին), այն իմաստով, որ երկու ֆունկցիաների գործակիցի սահմանը π(x) և x / log x ինչպես x ավելանում է առանց 1 սահմանի։
Այս արդյունքը կարող է վերաձևակերպվել որպես
Այն տալիս է Էվկլիդեսի թեորեմը, քանի որ
Բերտրան-Չեբիշևի թեորեմ
[խմբագրել | խմբագրել կոդը]Թվերի տեսության մեջ Բերտրանի թեորեմը նշում է, որ ցանկացած ամբողջ թվի համար ,միշտ կգտնվի առնվազն մեկ պարզ թիվ, որ
Բերտրան-Չեբիշևի թեորեմը կարող է նաև արտահայտվել որպես հարաբերություն , որտեղ պարզ հաշվելու ֆունկցիան է ( պարզերի թիվը փոքր կամ հավասար է ):
- for all
Այս հայտարարությունը առաջին անգամ արվել է 1845 թվականին Ջոզեֆ Բերտրանի կողմից[17]։ (1822–1900)։ Ինքը՝ Բերտրանը, ստուգեց իր հայտարարությունը [2, 3 × 106].միջակայքում գտնվող բոլոր թվերի համար։ Նրա ենթադրությունն ամբողջությամբ ապացուցվել է Չեբիշևի (1821–1894) կողմից 1852 թ.-ին, ուստի թեորեմը կոչվում է նաև Բերտրան–Չեբիշևի թեորեմ կամ Չեբիշևի թեորեմ[18]։ Այսպիսով, թեորեմըը կոչվում է նաև Բերտրան-Չեբիշևի թեորեմ կամ Չեբիշևի թեորեմ։
Ծանոթագրություններ
[խմբագրել | խմբագրել կոդը]- ↑ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
- ↑ Ore, Oystein (1988) [1948], Number Theory and its History, Dover, էջ 65
- ↑ In general, for any integers a, b, c if and , then . For more information, see Divisibility.
- ↑ The exact formulation of Euclid's assertion is: "The prime numbers are more numerous than any proposed multitude of prime numbers".
- ↑ Katz, Victor J. (1998), A History of Mathematics/ an Introduction (2nd ed.), Addison Wesley Longman, էջ 87
- ↑ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
- ↑ Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment, A K Peters, Ltd, էջ 101
- ↑ Bostock, Linda; Chandler, Suzanne; Rourke, C. (2014 թ․ նոյեմբերի 1). Further Pure Mathematics (անգլերեն). Nelson Thornes. էջ 168. ISBN 9780859501033.
- ↑ Theorems 7 and their Corollaries 1 and 2 in: Leonhard Euler. Variae observationes circa series infinitas. Commentarii academiae scientiarum Petropolitanae 9, 1744, pp. 160–188. [1]. (Original) [2]. (English translation version)
- ↑ In his History of the Theory of Numbers (Vol. 1, p. 413) Dickson refers to this proof, as well as to another one by citing page 235 of another work by Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. [3]. There (§ 279) Euler in fact essentially restates the much stronger Theorem 19 (described below) in the paper of his former proof.
- ↑ Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. էջեր 28–29. ISBN 0-691-09983-9.
- ↑ Furstenberg, Harry (1955). «On the infinitude of primes». American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.
- ↑ Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
- ↑ Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
- ↑ Saidak, Filip (2006 թ․ դեկտեմբեր). «A New Proof of Euclid's Theorem». American Mathematical Monthly. 113 (10): 937–938. doi:10.2307/27642094. JSTOR 27642094.
- ↑ Shen, Alexander (2016), Kolmogorov complexity and algorithmic randomness (PDF), AMS, էջ 245
- ↑ Bertrand, Joseph (1845), [[[:Կաղապար:Google Books]] «Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.»], Journal de l'École Royale Polytechnique (ֆրանսերեն), 18 (Cahier 30): 123–140
{{citation}}
: Check|url=
value (օգնություն). - ↑ Tchebychev, P. (1852), «Mémoire sur les nombres premiers.» (PDF), Journal de mathématiques pures et appliquées, Série 1 (ֆրանսերեն): 366–390. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854
Արտաքին հղումներ
[խմբագրել | խմբագրել կոդը]- Weisstein, Eric W., "Euclid's Theorem", MathWorld.
- Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)