Euclid's theorem
યુક્લિડનો પ્રમેય એ સંખ્યા સિદ્ધાંતમાં એક મૂળભૂત નિવેદન છે જે ભારપૂર્વક જણાવે છે કે અનંત સંખ્યાબંધ મુખ્ય સંખ્યાઓ છે. તે સૌપ્રથમ યુક્લિડે તેમની કૃતિ એલિમેન્ટ્સમાં સાબિત કરી હતી. આ પ્રમેયના ઘણા પુરાવા છે. યુક્લિડના પુરાવા યુક્લિડે તેમના કાર્ય એલિમેન્ટ્સ (પુસ્તક IX, પ્રપોઝિશન 20) માં પ્રકાશિત પુરાવા રજૂ કર્યા હતા, જે અહીં ભાષાંતર કરવામાં આવ્યું છે. મુખ્ય સંખ્યાઓ 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 એ બે સંખ્યાઓના તફાવતને પણ વિભાજિત કરવો જોઈએ, જે (P + 1) −P અથવા માત્ર 1 છે. કોઈ મુખ્ય સંખ્યા 1 ને વિભાજિત કરતી નથી, તેથી p એ યાદીમાં હોઈ શકતું નથી. આનો અર્થ એ છે કે યાદીમાં સામેલ સંખ્યાઓની બહાર ઓછામાં ઓછી એક વધુ મુખ્ય સંખ્યા અસ્તિત્વમાં છે. આ સાબિત કરે છે કે મુખ્ય સંખ્યાઓની દરેક મર્યાદિત સૂચિ માટે એક મુખ્ય સંખ્યા હોય છે જે સૂચિમાં નથી. મૂળ કૃતિમાં, યુક્લિડ પાસે અવિભાજ્ય સંખ્યાઓની મનસ્વી સૂચિ લખવાની કોઈ રીત ન હોવાથી, તેમણે એક પદ્ધતિનો ઉપયોગ કર્યો હતો જે તેમણે વારંવાર લાગુ કરી હતી, એટલે કે, સામાન્યીકૃત ઉદાહરણની પદ્ધતિ. એટલે કે, તે માત્ર ત્રણ પ્રાઈમ પસંદ કરે છે અને ઉપર દર્શાવેલ સામાન્ય પદ્ધતિનો ઉપયોગ કરીને સાબિત કરે છે કે તે હંમેશા વધારાનો પ્રાઈમ શોધી શકે છે. યુક્લિડ સંભવતઃ ધારે છે કે તેના વાચકોને ખાતરી છે કે સમાન સાબિતી કામ કરશે, ભલે ગમે તેટલી મૂળ સંખ્યાઓ પસંદ કરવામાં આવે. યુક્લિડે ઘણીવાર ભૂલથી આ પરિણામને વિરોધાભાસ દ્વારા સાબિત કર્યું હોવાનું નોંધવામાં આવે છે, જેની શરૂઆત એવી ધારણાથી થાય છે કે શરૂઆતમાં માનવામાં આવતા મર્યાદિત સમૂહમાં તમામ મુખ્ય સંખ્યાઓ હોય છે, જો કે તે વાસ્તવમાં કિસ્સાઓ દ્વારા સાબિતી છે, એક સીધી સાબિતી પદ્ધતિ છે. ફિલસૂફ ટોર્કેલ ફ્રાન્ઝેન તર્કશાસ્ત્ર પરના એક પુસ્તકમાં જણાવે છે કે, "યુક્લિડનો પુરાવો કે અનંત સંખ્યાબંધ અવિભાજ્ય સંખ્યાઓ છે તે પરોક્ષ પુરાવો નથી [.] આ દલીલને કેટલીકવાર 'ધારો કે બધા અવિભાજ્ય સંખ્યાઓ છે' એવી ધારણા સાથે બદલીને પરોક્ષ પુરાવો તરીકે ઘડવામાં આવે છે. જો કે, આ ધારણાનો ઉપયોગ સાબિતીમાં પણ થતો નથી, તેથી સુધારણા અર્થહીન છે. ભિન્નતા યુક્લિડના પુરાવા પર ઘણી ભિન્નતાઓ અસ્તિત્વમાં છે, જેમાં નીચેનાનો સમાવેશ થાય છેઃ ફેક્ટોરિયલ એન! હકારાત્મક પૂર્ણાંક n નો 2 થી n સુધીના દરેક પૂર્ણાંક દ્વારા વિભાજીત થાય છે, કારણ કે તે તે બધાનો ગુણાકાર છે. તેથી, 2 થી n સુધીના કોઈપણ પૂર્ણાંકો દ્વારા વિભાજ્ય નથી, સમાવિષ્ટ (તે દરેક દ્વારા વિભાજિત થાય ત્યારે 1 નો બાકીનો ભાગ આપે છે). તેથી તે કાં તો અવિભાજ્ય છે અથવા n કરતા મોટા અવિભાજ્ય દ્વારા વિભાજીત થાય છે. બંને કિસ્સાઓમાં, દરેક હકારાત્મક પૂર્ણાંક n માટે, n કરતા ઓછામાં ઓછો એક અવિભાજ્ય મોટો હોય છે. નિષ્કર્ષ એ છે કે અવિભાજ્ય સંખ્યાઓ અનંત છે. યુલરનો પુરાવો સ્વિસ ગણિતશાસ્ત્રી લિયોનહાર્ડ યુલરનો બીજો પુરાવો, અંકગણિતના મૂળભૂત પ્રમેય પર આધાર રાખે છેઃ કે દરેક પૂર્ણાંકમાં એક અનન્ય મુખ્ય ગુણાંક હોય છે. યુલરએ જે લખ્યું (આ આધુનિક સંકેત સાથે નહીં અને, આધુનિક ધોરણોથી વિપરીત, સરવાળા અને ઉત્પાદનોમાં દલીલોને પૂર્ણાંકોના કોઈપણ મર્યાદિત સમૂહો સુધી મર્યાદિત નહીં) તે નિવેદનની સમકક્ષ છે કે આપણી પાસે જ્યાં પ્રથમ મુખ્ય સંખ્યાઓના સમૂહને સૂચવે છે, અને તે હકારાત્મક પૂર્ણાંકોનો સમૂહ છે જેના તમામ મુખ્ય પરિબળો તેમાં છે. ઉપાંત્ય સરવાળામાં અવિભાજ્ય સંખ્યાઓનું દરેક ગુણાકાર બરાબર એક જ વાર દેખાય છે, અને તેથી છેલ્લી સમાનતા અંકગણિતના મૂળભૂત પ્રમેય દ્વારા સાચી છે. આ પરિણામના તેમના પ્રથમ ઉપસંહારમાં યુલર "નિરપેક્ષ અનંત" સમાન પ્રતીક દ્વારા સૂચવે છે અને લખે છે કે નિવેદનમાં અનંત સરવાળો "મૂલ્ય" ની બરાબર છે, જેના માટે અનંત ઉત્પાદન પણ આમ સમાન છે (આધુનિક પરિભાષામાં આ કહેવાની સમકક્ષ છે કે હાર્મોનિક શ્રેણીનો આંશિક સરવાળો એસિમ્પ્ટોટિક રીતે અલગ પડે છે). પછી તેમના બીજા ઉપસંહારમાં યુલર નોંધે છે કે ગુણાકાર મર્યાદિત મૂલ્ય 2 માં એકરૂપ થાય છે, અને પરિણામે ચોરસ કરતાં વધુ અવિભાજ્ય સંખ્યાઓ હોય છે. આ યુક્લિડના પ્રમેયને સાબિત કરે છે. એ જ પેપરમાં (પ્રમેય 19) યુલરએ હકીકતમાં ઉપરોક્ત સમાનતાનો ઉપયોગ વધુ મજબૂત પ્રમેયને સાબિત કરવા માટે કર્યો હતો જે તેમની પહેલાં અજાણ હતો, એટલે કે શ્રેણી અલગ છે, જ્યાં તમામ મુખ્ય સંખ્યાઓનો સમૂહ સૂચવે છે (યુલર લખે છે કે અનંત સરવાળો, જે આધુનિક પરિભાષામાં કહેવાની સમકક્ષ છે કે આ શ્રેણીનો આંશિક સરવાળો એસિમ્પ્ટોટિક રીતે વર્તે છે). એર્ડોસનો પુરાવો પોલ એર્ડોસે એક પુરાવો આપ્યો જે અંકગણિતના મૂળભૂત પ્રમેય પર પણ આધાર રાખે છે. દરેક સકારાત્મક પૂર્ણાંકમાં વર્ગ-મુક્ત સંખ્યા અને વર્ગ સંખ્યામાં એક અનન્ય ગુણાંક હોય છે. ઉદાહરણ તરીકે,. ધારો કે તે એક સકારાત્મક પૂર્ણાંક છે, અને તે અવિભાજ્ય સંખ્યાઓની સંખ્યા તેનાથી ઓછી અથવા તેની બરાબર હોવી જોઈએ. તે પ્રાઇમને કૉલ કરો. કોઈપણ હકારાત્મક પૂર્ણાંક કે જે તેનાથી ઓછો અથવા તેની બરાબર હોય તે પછી તે સ્વરૂપમાં લખી શકાય છે જ્યાં દરેક ક્યાં તો અથવા હોય. ચોરસ-મુક્ત ભાગ બનાવવાની રીતો છે. અને કદાચ હોવો પણ જોઇએ. આમ, મોટાભાગની સંખ્યાઓ આ સ્વરૂપમાં લખી શકાય છે. બીજા શબ્દોમાં કહીએ તો, અથવા, ફરીથી ગોઠવણી, કરતા ઓછી અથવા તેની બરાબર અવિભાજ્ય સંખ્યા, તેના કરતા વધારે અથવા તેની બરાબર હોય છે. કારણ કે તે મનસ્વી હતું, યોગ્ય રીતે પસંદ કરીને ઇચ્છિત જેટલું મોટું હોઈ શકે છે. ફર્સ્ટેનબર્ગનો પુરાવો 1950ના દાયકામાં, હિલેલ ફર્સ્ટેનબર્ગે પોઇન્ટ-સેટ ટોપોલોજીનો ઉપયોગ કરીને વિરોધાભાસ દ્વારા પુરાવો રજૂ કર્યો હતો. પૂર્ણાંકો Z પર ટોપોલોજીને વ્યાખ્યાયિત કરો, જેને સમાન અંતરે પૂર્ણાંક ટોપોલોજી કહેવામાં આવે છે, જ્યારે અને માત્ર ત્યારે જ જ્યારે તે ખાલી સમૂહ હોય, અથવા તે અંકગણિત ક્રમ S (a, b) નું જોડાણ હોય, જ્યાં પછી ગુણધર્મમાંથી વિરોધાભાસ અનુસરે છે કે પૂર્ણાંકોનો મર્યાદિત સમૂહ ખુલ્લો હોઈ શકતો નથી અને આધાર S (a, b) ને સુયોજિત કરે છે તે ગુણધર્મ બંને ખુલ્લા અને બંધ હોય છે, કારણ કે તેનું પૂરક મર્યાદિત હોવાથી તેને બંધ કરી શકાતું નથી, પરંતુ તે બંધ છે કારણ કે તે બંધ સમૂહોનું મર્યાદિત જોડાણ છે. સમાવેશ-બાકાત સિદ્ધાંતનો ઉપયોગ કરીને તાજેતરના પુરાવા પુરાવા જુઆન પાબ્લો પિનાસ્કોએ નીચેનો પુરાવો લખ્યો છે. ધારો કે p1,., pN એ સૌથી નાનો N અવિભાજ્ય છે. પછી સમાવેશ-બાકાત સિદ્ધાંત દ્વારા, x કરતા ઓછા અથવા તેના બરાબરના હકારાત્મક પૂર્ણાંકોની સંખ્યા કે જે તે અવિભાજ્ય સંખ્યાઓમાંથી એક દ્વારા વિભાજીત થાય છે તે x દ્વારા વિભાજીત થાય છે અને x ને x → φ તરીકે લખી શકાય છે. તેથી, p1,., pN કરતાં વધુ અવિભાજ્ય હોવા જોઈએ. લિજેન્ડ્રેના સૂત્રનો ઉપયોગ કરીને પુરાવો 2010માં, જુનહો પીટર વ્હાંગે વિરોધાભાસ દ્વારા નીચેનો પુરાવો પ્રકાશિત કર્યો હતો. ધારો કે k એ કોઈપણ હકારાત્મક પૂર્ણાંક છે. પછી લિજેન્ડ્રેના સૂત્ર અનુસાર (કેટલીકવાર ડી પોલિગ્નેકને આભારી) જ્યાં પરંતુ જો માત્ર મર્યાદિત રીતે ઘણા અવિભાજ્ય અસ્તિત્વ ધરાવે છે, તો પછી (અપૂર્ણાંકનો અંશ એકલો ઝડપથી વધશે જ્યારે સ્ટર્લિંગના અંદાજ દ્વારા છેદ એકલો ઘાતાંકીય કરતાં વધુ ઝડપથી વધે છે), એ હકીકતને વિરોધાભાસી છે કે દરેક k માટે અંશ છેદ કરતા મોટો અથવા બરાબર છે. બાંધકામ દ્વારા પુરાવો ફિલિપ સૈદાકએ બાંધકામ દ્વારા નીચેનો પુરાવો આપ્યો હતો, જેમાં રિડક્ટિયો એડ અબ્સર્ડમ અથવા યુક્લિડના લેમ્માનો ઉપયોગ થતો નથી (કે જો કોઈ અવિભાજ્ય p એ. બી. ને વિભાજિત કરે તો તે એ. અથવા બી. ને વિભાજિત કરવું આવશ્યક છે). કારણ કે દરેક પ્રાકૃતિક સંખ્યા (> 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 = 326342 {2,3,7,43,13,13,139}, · · અવિભાજ્ય સંખ્યાઓના અમર્યાદિત વધતા સમૂહોનો ક્રમ પ્રદાન કરે છે. સંકોચનક્ષમતા પદ્ધતિનો ઉપયોગ કરીને પુરાવો ધારો કે ત્યાં માત્ર k પ્રાઈમ (p1,., pk) હતા. અંકગણિતના મૂળભૂત પ્રમેય દ્વારા, કોઈપણ હકારાત્મક પૂર્ણાંક n ને તે રીતે રજૂ કરી શકાય છે જ્યાં બિન-નકારાત્મક પૂર્ણાંક ઘાતાંકો એટલે કે અવિભાજ્યની મર્યાદિત કદની સૂચિ સાથે મળીને સંખ્યાનું પુનર્ગઠન કરવા માટે પૂરતા છે. બધા i માટે, તે બધા i માટે અનુસરે છે (જ્યાં આધાર-2 લઘુગણક સૂચવે છે). આ નીચેના કદના n માટે એન્કોડિંગ આપે છે (મોટા O નોટેશનનો ઉપયોગ કરીને): બિટ્સ. દ્વિસંગીમાં સીધા n નું પ્રતિનિધિત્વ કરતાં આ વધુ કાર્યક્ષમ એન્કોડિંગ છે, જે બિટ્સ લે છે. લોસલેસ ડેટા કમ્પ્રેશનમાં સ્થાપિત પરિણામ જણાવે છે કે કોઈ પણ વ્યક્તિ સામાન્ય રીતે માહિતીના એન બિટ્સને એન બિટ્સ કરતા ઓછામાં સંકુચિત કરી શકતું નથી. જ્યારે n પૂરતું મોટું હોય ત્યારે ઉપરોક્ત રજૂઆત આનું ઉલ્લંઘન કરે છે. તેથી, મૌલિક સંખ્યાઓની સંખ્યા મર્યાદિત હોવી જોઈએ નહીં. મજબૂત પરિણામો આ વિભાગમાં પ્રમેયો એક સાથે યુક્લિડના પ્રમેય અને અન્ય પરિણામોને સૂચવે છે. અંકગણિત પ્રગતિ પર ડિરીક્લેટનો પ્રમેય ડિરીક્લેટનો પ્રમેય જણાવે છે કે કોઈપણ બે સકારાત્મક સહમૌલિક પૂર્ણાંકો a અને d માટે, a + nd સ્વરૂપના અનંત સંખ્યાબંધ અવિભાજ્ય સંખ્યાઓ છે, જ્યાં n પણ એક સકારાત્મક પૂર્ણાંક છે. બીજા શબ્દોમાં કહીએ તો, ત્યાં અનંત સંખ્યાબંધ અવિભાજ્ય સંખ્યાઓ છે જે મોડ્યુલો ડી માટે સર્વસમ છે. મુખ્ય સંખ્યા પ્રમેય ચાલો મુખ્ય-ગણતરી કાર્ય હોઈએ જે કોઈપણ વાસ્તવિક સંખ્યા માટે, તેનાથી ઓછી અથવા તેની બરાબર અવિભાજ્ય સંખ્યા આપે છે. પ્રાઇમ નંબર થીયરમ પછી જણાવે છે કે તે એક સારો અંદાજ છે, આ અર્થમાં કે બે વિધેયોના ભાગની મર્યાદા અને બાઉન્ડ વગર વધે છે તે 1 છેઃ એસિમ્પ્ટોટિક નોટેશનનો ઉપયોગ કરીને આ પરિણામને આ રીતે પુનરાવર્તિત કરી શકાય છે આ યુક્લિડનો પ્રમેય આપે છે, કારણ કે બર્ટ્રાન્ડ-ચેબિશેવ થીયરમ સંખ્યા સિદ્ધાંતમાં, બર્ટ્રાન્ડની પૂર્વધારણા એ એક પ્રમેય છે જે જણાવે છે કે કોઈપણ પૂર્ણાંક માટે, હંમેશા ઓછામાં ઓછી એક પ્રાઇમ નંબર અસ્તિત્વમાં હોય છે, જેમ કે બર્ટ્રાન્ડ-ચેબિશેવ થીયરમને પણ તેની સાથે સંબંધ તરીકે વર્ણવી શકાય છે, જ્યાં પ્રાઇમ-કાઉન્ટિંગ ફંક્શન છે (પ્રાઇમની સંખ્યા બાઉન્ડ કરતાં ઓછી અથવા સમાન હોય છે): આ બધા માટે 1845 માં જોસેફ બર્ટ્રાન્ડ (1822-1900) દ્વારા પ્રથમ અનુમાન કરવામાં આવ્યું હતું. બર્ટ્રાન્ડે પોતે અંતરાલમાં તમામ સંખ્યાઓ માટેના તેમના નિવેદનની ચકાસણી કરી હતી તેમના અનુમાનને 1852માં ચેબીશેવ (1821-1894) દ્વારા સંપૂર્ણપણે સાબિત કરવામાં આવ્યું હતું અને તેથી આ પૂર્વધારણાને બર્ટ્રાન્ડ-ચેબીશેવ પ્રમેય અથવા ચેબીશેવની પ્રમેય પણ કહેવામાં આવે છે. નોંધો અને સંદર્ભો બાહ્ય કડીઓ યુક્લિડ્સ એલિમેન્ટ્સ, બુક IX, પ્રોપ. 20 (યુક્લિડનો પુરાવો, ક્લાર્ક યુનિવર્સિટી ખાતે ડેવિડ જોયસની વેબસાઇટ પર) મુખ્ય સંખ્યાઓ વિશે સિદ્ધાંતો ધરાવતા લેખો