Էվկլիդեսի Թեորեմ

Ուշադրություն, այս էջը կամ բաժինը այլ լեզվով հոդվածի վատ թարգմանություն է։

Էվկլիդեսի թեորեմ, թվերի տեսության հիմնարար պնդում, պարզ թվերի անսահման շատ լինելու մասին։ Այն առաջին անգամ ապացուցվել է Էվկլիդեսի կողմից իր «Տարրեր» աշխատությունում։ Թեորեմի մի քանի ապացույցներ կան.

Էվկլիդեսն առաջարկեց ապացույց, որը հրապարակվել է իր «Տարրեր» աշխատության մեջ (Գիրք IX, Առաջարկ 20), որը վերափոխված է այստեղ։

Դիտարկենք պարզ թվերի ցանկացած վերջավոր ցուցակ p₁, p₂, ..., p_n.։ Կցուցադրվի, որ կա առնվազն մեկ լրացուցիչ պարզ թիվ, որը չկա այս ցանկում։ Թող P լինի ցուցակի բոլոր պարզ թվերի արտադրյալը. P = p₁p₂...p_n. Թող q = P + 1. Այնուհետև q-ն կամ պարզ է, կամ ոչ.

• Եթե q-ն պարզ է, ապա կա առնվազն ևս մեկ պարզ, որը ցուցակում չկա, այն է՝ ինքնին q:
• Եթե q-ն պարզ չէ, ապա պարզ որոշ p գործակիցը բաժանվում է q-ին։ Եթե այս p գործակիցը լիներ մեր ցուցակում, ապա այն կբաժանվեր P-ին (քանի որ P-ն ցուցակի յուրաքանչյուր թվի արտադրյալն է), բայց p-ն նաև բաժանվում է P + 1 = q, ինչպես արդեն նշվեց։ Եթե p-ն բաժանվում է P-ին և նաև q-ն, ապա p-ն նույնպես պետք է բաժանվի տարբերությանը երկու թվերից, որը (P + 1) − P կամ պարզապես 1։ Քանի որ ոչ մի պարզ թիվ չի բաժանվում 1-ին, p չի կարող լինել ցուցակում։ Սա նշանակում է, որ ցուցակում նշվածներից դուրս առնվազն ևս մեկ պարզ թիվ կա։ Սա ապացուցում է, որ պարզ թվերի յուրաքանչյուր վերջավոր ցուցակի համար կա մի պարզ թիվ, որը չկա ցուցակում։ Բնօրինակ աշխատության մեջ, քանի որ Էվկլիդեսը չուներ պարզ թվերի կամայական ցուցակ գրելու միջոց, նա օգտագործեց մի մեթոդ, որը նա հաճախ էր կիրառում, այսինքն՝ ընդհանրացվող օրինակի մեթոդը։ Մասնավորապես, նա ընտրում է ընդամենը երեք պարզ թվեր և օգտագործելով վերը նկարագրված ընդհանուր մեթոդը, ապացուցում է, որ միշտ կարող է գտնել լրացուցիչ պարզ թիվ։ Էվկլիդեսը ենթադրում է, որ իր ընթերցողները համոզված են, որ նմանատիպ ապացույցը կգործի, անկախ նրանից, թե քանի պարզ թիվ են սկզբնապես ընտրված։

Հաճախ սխալմամբ հաղորդվում է, որ Էվկլիդեսը ապացուցել է այս արդյունքը հակասությամբ, որը սկսվում է այն ենթադրությունից, որ ի սկզբանե դիտարկված վերջավոր բազմությունը պարունակում է բոլոր պարզ թվերը, թեև դա իրականում ուղղակի ապացուցման մեթոդ ՝: Փիլիսոփա Տորկել Ֆրանցենը տրամաբանության մասին գրքում նշում է. «Էվկլիդեսի ապացույցի մեջ կան անսահման շատ պարզ թվեր, անուղղակի ապացույց չէ։ Փաստարկը երբեմն ձևակերպվում է որպես անուղղակի ապացույց՝ այն փոխարինելով «Ենթադրենք q1» ենթադրությամբ։, ... qn-ը բոլոր պարզերն են։ Այնուամենայնիվ, քանի որ այս ենթադրությունը նույնիսկ չի օգտագործվում ապացուցման մեջ, վերաձևակերպումն անիմաստ է։

Վարիացիաներ

Էվկլիդեսի ապացույցի մի քանի ձևակերպումներ կան.

n-ի ֆակտորիալ n! դրական ամբողջ թվի համար n-ը բաժանվում է 2-ից մինչև n-ի յուրաքանչյուր ամբողջ թվի, քանի որ այն բոլորի արտադրյալն է։ Հետևաբար, n! + 1-ը չի բաժանվում 2-ից մինչև n ամբողջ թվերից որևէ մեկի վրա, ներառյալ (յուրաքանչյուրի վրա բաժանելու դեպքում տալիս է 1 մնացորդ)։ Ուստի n! + 1-ը պարզ է կամ բաժանվում է n-ից մեծ պարզ թվի։ Երկու դեպքում էլ, յուրաքանչյուր n դրական ամբողջ թվի համար կա առնվազն մեկ պարզ, որը մեծ է n-ից։ Եզրակացություն, պարզ թվերն անսահման են։

Մեկ այլ ապացույց՝ շվեյցարացի մաթեմատիկոս Լեոնհարդ Էյլերի կողմից, հիմնված է թվաբանության հիմնարար թեորեմի վրա. յուրաքանչյուր ամբողջ թիվ ունի եզակի պարզ ֆակտորիալ։ Այն, ինչ գրել է Էյլերը (ոչ այս ժամանակակից նշումով և, ի տարբերություն ժամանակակից ստանդարտների, գումարների և արտադրյալների փաստարկները չսահմանափակելով ամբողջ թվերի որևէ վերջավոր բազմությամբ) համարժեք է այն հայտարարությանը, որ մենք ունենք։

${\displaystyle \prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{\frac {1}{n}},}$ 

որտեղ ${\displaystyle P_{k}}$  նշանակում է k առաջին պարզ թվերի բազմություն և ${\displaystyle N_{k}}$  այն դրական ամբողջ թվերի բազմությունն է, որոնց հիմնական գործակիցները բոլորը ${\displaystyle P_{k}.}$ են։

Դա ցույց տալու համար արտադրյալի յուրաքանչյուր գործակիցը ընդլայնվում է որպես երկրաչափական շարք և բաշխում է արտադրյալը գումարի վրա (սա Էյլերի բանաձևի հատուկ դեպքն է Ռիմանի զետա ֆունկցիայի համար)։

${\displaystyle {\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1}{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i}}}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^{n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{aligned}}}$ 

Նախավերջին գումարում պարզ թվերի յուրաքանչյուր արտադրյալ նշվում է ուղիղ մեկ անգամ, և հետևաբար վերջին հավասարությունը ճշմարիտ է թվաբանության հիմնարար թեորեմով։ Այս արդյունքը իր առաջին հետևանքում Էյլերը նշում է նման նշանով ${\displaystyle \infty }$  « բացարձակ անսահմանություն » և գրում, հայտարարության մեջ անսահման գումարը հավասար է ${\displaystyle \log \infty }$ , որին, հետևաբար, հավասար է նաև անսահման արտադրյալը (ժամանակակից տերմինաբանության մեջ դա համարժեք է նրան, որ մասնակի գումարը մինչև 𝑥  ներդաշնակ շարքը շեղվում է ասիմպտոտիկ նման 𝑥) Այնուհետև իր երկրորդ եզրակացության մեջ Էյլերը նշում է, որ

${\displaystyle \prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}}$ 

համընկնում է 2-ի վերջավոր արժեքին, և որ հետևաբար կան ավելի շատ պարզ թվեր, քան քառակուսիներ։ Սա ապացուցում է Էվկլիդեսի թեորեմը։

 

Նույն աշխատության մեջ (Թեորեմ 19) Էյլերը փաստորեն օգտագործեց վերը նշված հավասարությունը՝ ապացուցելու թեորեմը, որն իրենից առաջ անհայտ էր, այն է, որ շարքը.

${\displaystyle \sum _{p\in P}{\frac {1}{p}}}$ 

դիֆերենտ է, որտեղ P-ն նշանակում է բոլոր պարզ թվերի բազմություն (Էյլերը գրում է, որ անսահման գումարը ${\displaystyle =\log \log \infty }$ , որը ժամանակակից տերմինաբանությամբ համարժեք է ասելու, որ մասնակի գումարը մինչև 𝑥 շարքն ասիմպտոտիկ է ${\displaystyle \log \log x}$ ).

Պոլ Էրդոսը ապացույց է տվել որը նույնպես հիմնված է թվաբանության հիմնարար թեորեմի վրա։ Յուրաքանչյուր դրական ամբողջ թիվ ունի եզակի ֆակտորիալ առանց r քառակուսու և s²քառակուսի թվերի։ Օրինակ, 75,600 = 2⁴ 3³ 5² 7¹ = 21 ⋅ 60².

Թող N լինի դրական ամբողջ թիվ, և թող K-ն լինի N-ից փոքր կամ հավասար պարզ թվեր։ Այդ պարզ թվերն անվանեք p1, ..., pk: Ցանկացած դրական ամբողջ թիվ, որը փոքր է կամ հավասար է N-ին, այնուհետև կարելի է գրել հետյալ ձևով

${\displaystyle a=\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2},}$ 

որտեղ յուրաքանչյուր ei կամ 0 է կամ 1։ Կան 2^k a-ի քառակուսի ազատ մասի ձևավորման եղանակներ. Եվ s² կարող է լինել առավելագույն N։ Այլ կերպ ասած,

${\displaystyle N\leq 2^{k}{\sqrt {N}}.}$ 

Կամ, վերադասավորելով k, պարզ պարզերի թիվը N-ից փոքր կամ հավասար է, մեծ կամ հավասար է 12log₂ N. Քանի որ N-ը կամայական էր, k-ն կարող է լինել այնքան մեծ, որքան ցանկանում եք՝ համապատասխանաբար ընտրելով N:

1950-ականներին Հիլել Ֆուրստենբերգը ներկայացրեց հակասության ապացույց՝ օգտագործելով կետային տոպոլոգիա։

Սահմանենք Z ամբողջ թվերի վրա տոպոլոգիա, որը կոչվում է հավասարաչափ տարածված ամբողջ թվերի տոպոլոգիա՝ U ⊆ Z ենթաբազմությունը հայտարարելով բաց բազմություն, այն և միայն այն դեպքում, եթե դա դատարկ բազմություն է, ∅, կամ թվաբանական հաջորդականությունների միություն S( a, b) (a ≠ 0-ի համար), որտեղ

${\displaystyle S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.}$ 

Այնուհետև հակասություն է բխում այն հատկությունից, որ ամբողջ թվերի վերջավոր բազմությունը չի կարող բաց լինել, և այն հատկությունը, որով S(a, b) հիմնական բազմությունները և բաց են և փակ, քանի որ

${\displaystyle \mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p\mathrm {\,prime} }S(p,0)}$ 

չի կարող փակվել, քանի որ դրա լրացումը վերջավոր է, բայց փակ է, քանի որ այն փակ բազմությունների վերջավոր նազմություն է։

Ներառում-բացառում սկզբունքի օգտագործմամբ ապացույց

Խուան Պաբլո Պինասկոն գրել է հետևյալ ապացույցը

Թող p₁, ..., p_N լինի ամենափոքր N պարզ թվերը։ Այնուհետև ներառում-բացառման սկզբունքով x-ից փոքր կամ հավասար դրական ամբողջ թվերը, որոնք բաժանվում են այդ պարզ թվերից մեկի վրա.

${\displaystyle {\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i$ 

Բաժանելով x-ի և թույլ տալով x → ∞ տալիս է

${\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i$ 

Սա կարելի է գրել այսպես

${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$ 

Եթե p₁, ..., p_N այլ թվեր չկան,ապա (1) արտահայտությունը հավասար է ${\displaystyle \lfloor x\rfloor }$  և (2)-ի արտահայտությունը հավասար է 1-ի, բայց ակնհայտորեն (3)-ի արտահայտությունը հավասար չէ 1-ի։ Հետևաբար, պետք է ավելի շատ պարզ թվեր լինեն, քան  p₁, ..., p_N։

Լեժանդրի բանաձևով ապացույց

2010 թվականին Ջունհո Պիտեր Ուանգը հակասականորեն հրապարակեց հետևյալ ապացույցը։ Թող K-ն լինի ցանկացած դրական ամբողջ թիվ։ Այնուհետև Լեժանդրի բանաձևով (երբեմն վերագրվում է դե Պոլինյակին)

${\displaystyle k!=\prod _{p{\text{ prime}}}p^{f(p,k)}}$ 

որտեղ

${\displaystyle f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .}$ 

${\displaystyle f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.}$ 

Բայց եթե գոյություն ունեն միայն վերջավոր թվով պարզ թվեր, ապա

${\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}$ 

(կոտորակի համարիչը կմեծանա եզակի էքսպոնենցիալ, մինչդեռ Ստերլինգի մոտավորմամբ հայտարարն աճում է ավելի արագ, քան առանձին էքսպոնենցիալ), հակասելով այն փաստին, որ յուրաքանչյուր 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}, · · ·
ապահովում է պարզ թվերի անսահմանափակ աճող բազմությունների հաջորդականություն։

Անսեղմելիության մեթոդի կիրառմամբ ապացույց

Ենթադրենք, եղել են միայն k պարզ թվեր (p₁, ..., p_k)։ Թվաբանության հիմնարար թեորեմի համաձայն՝ ցանկացած դրական ամբողջ n թիվ կարող է ներկայացվել որպես

$${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},}$$

 

${\displaystyle p_{i}\geq 2}$ 

${\displaystyle e_{i}\leq \lg n}$ 

${\displaystyle O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)}$  բիթ։

Սա շատ ավելի արդյունավետ կոդավորում է, քան n-ն ուղղակիորեն երկուական տարբերակով ներկայացնելը, որը տևում է ${\displaystyle N=O(\lg n)}$  բիթ։ Տվյալների անկորուստ սեղմման հաստատված արդյունքը նշում է, որ ընդհանուր առմամբ չի կարելի սեղմել տեղեկատվության N բիթերը N-ից պակաս բիթերի։ Վերոնշյալ ներկայացումը խիստ խախտում է, երբ n-ը բավականաչափ մեծ է, քանի որ ${\displaystyle \lg \lg n=o(\lg n)}$ . Ուստի պարզ թվերը չպետք է վերջավոր լինեն։

Այս բաժնի թեորեմները միաժամանակ ենթադրում են Էվկլիդեսի թեորեմը և այլ արդյունքներ։

Դիրիխլեի թեորեմը թվաբանական առաջընթացների մասին

Դիրիխլեի թեորեմն ասում է, որ a-ի և d-ի ցանկացած երկու դրական ընդհանուր ամբողջ թվերի համար կան a + nd ձևի անսահման շատ պարզ թվեր, որտեղ n-ը նույնպես դրական ամբողջ թիվ է։ Այլ կերպ ասած, կան անսահման շատ պարզեր, որոնք ձգտում են մոդուլ d-ին։

Պարզ թվերի թեորեմ

Թող π(x) լինի պարզ հաշվելու ֆունկցիան, որը տալիս է պարզ թիվը x-ից փոքր կամ հավասար ցանկացած իրական թվի համար։ Այնուհետև պարզ թվերի թեորեմը նշում է, որ x / log x-ը լավ մոտարկում է π(x-ին), այն իմաստով, որ երկու ֆունկցիաների գործակիցի սահմանը π(x) և x / log x ինչպես x ավելանում է առանց 1 սահմանի։

${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.}$ 

Այս արդյունքը կարող է վերաձևակերպվել որպես

${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.}$ 

Այն տալիս է Էվկլիդեսի թեորեմը, քանի որ${\displaystyle \lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .}$ 

Բերտրան-Չեբիշևի թեորեմ

Թվերի տեսության մեջ Բերտրանի թեորեմը նշում է, որ ցանկացած ամբողջ թվի համար ${\displaystyle n>1}$ ,միշտ կգտնվի առնվազն մեկ պարզ թիվ, որ

${\displaystyle n$ 

Բերտրան-Չեբիշևի թեորեմը կարող է նաև արտահայտվել որպես հարաբերություն ${\displaystyle \pi (x)}$ , որտեղ ${\displaystyle \pi (x)}$  պարզ հաշվելու ֆունկցիան է ( պարզերի թիվը փոքր կամ հավասար է ${\displaystyle x\,}$ ):

${\displaystyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1,}$  for all ${\displaystyle x\geq 2.}$ 

Այս հայտարարությունը առաջին անգամ արվել է 1845 թվականին Ջոզեֆ Բերտրանի կողմից։ (1822–1900)։ Ինքը՝ Բերտրանը, ստուգեց իր հայտարարությունը [2, 3 × 10⁶].միջակայքում գտնվող բոլոր թվերի համար։ Նրա ենթադրությունն ամբողջությամբ ապացուցվել է Չեբիշևի (1821–1894) կողմից 1852 թ.-ին, ուստի թեորեմը կոչվում է նաև Բերտրան–Չեբիշևի թեորեմ կամ Չեբիշևի թեորեմ։ Այսպիսով, թեորեմըը կոչվում է նաև Բերտրան-Չեբիշևի թեորեմ կամ Չեբիշևի թեորեմ։