From Wikipedia, the free encyclopedia
અવિભાજ્ય સંખ્યા (prime number) એક એવી પ્રાકૃતિક સંખ્યા છે, જે ૧ કરતાં મોટી છે અને જેને પોતાના અને ૧ના સિવાય અન્ય કોઈ અવયવ નથી. ૧ કરતા મોટી દરેક પ્રાકૃતિક સંખ્યા, જો અવિભાજ્ય ન હોય, તો તે વિભાજ્ય સંખ્યા કહેવાય છે. ઉદાહરણ તરીકે, 5 એ અવિભાજ્ય છે, કારણ કે તેના ધન પૂર્ણાંક અવયવ માત્ર 1 અને 5 છે, જ્યારે 6 વિભાજ્ય છે, કારણ કે તેના અવયવો 1 અને 6 ઉપરાંત 2 અને 3 છે. અંકગણિતનો મૂળભૂત પ્રમેય, અવિભાજ્ય સંખ્યાઓનું અંકગણિતમાં મહત્ત્વ સાબિત કરે છે: ૧ કરતાં મોટા કોઈ પણ પૂર્ણાંકને અવિભાજ્ય અવયવોના ગુણાકાર તરીકે અનન્ય રીતે દર્શાવી શકાય (જો કે ગુણાકારમાં તેમનો ક્રમ બદલાઈ શકે). આ પ્રમેયની વિશિષ્ટતાને માટે જરૂરી છે કે ૧ને અવિભાજ્ય ગણવામાં ન આવે, કારણ કે ૧ને કોઈ પણ અવયવીકરણમાં ગમે તેટલી વખત (arbitrarily many times) લઇ શકાય, દા. ત., 3, 1 · 3, 1 · 1 · 3, વગેરે, જે બધા ૩ના માન્ય અવયવીકરણ છે.
અવિભાજ્ય હોવા કે ન હોવાના ગુણધર્મને અવિભાજ્યતા કહે છે. આપેલ સંખ્યા nની અવિભાજ્યતા ચકાસવાની એક ધીમી પણ સહેલી રીત trial division છે. તે રીતમાં ચકાસવાનું હોય છે કે n એ 2 અને . મોટી સંખ્યાઓની અવિભાજ્યતા ચકાસવા માટે trial division કરતા ઘણા વધુ કાર્યક્ષમ Algorithms બનાવવામાં આવ્યા છે. જેમાં Miller–Rabin primality test, જે ઝડપી છે પણ તેમાં ભૂલની થોડી સંભાવના રહે છે, અને AKS primality test, જે polynomial time માં હંમેશા સાચો જવાબ આપે છે, પણ વ્યવહારમાં (practically) બહુ ધીમો છે. ખાસ સ્વરૂપની સંખ્યાઓ ,જેમ કે Mersenne numbers, માટે ઝડપી રીતો (પ્રાપ્ય / available) છે. જાન્યુઆરી ૨૦૧૬માં સૌથી મોટી અવિભાજ્ય સંખ્યામાં 22,338,618 દશાંશ અંકો છે. યુક્લિડે ઈ.સ. પૂર્વે ૩૦૦માં દર્શાવ્યા મુજબ (યુક્લીડનું પ્રમેય) અવિભાજ્ય સંખ્યાઓ અનંત છે. કોઈ જાણીતા, સાદા સૂત્ર વડે અવિભાજ્ય સંખ્યાઓને વિભાજ્ય સંખ્યાઓથી અલગ પાડી શકાતી નથી. જો કે અવિભાજ્ય સંખ્યાઓનું વિતરણ, એટલે કે આંકડાશાસ્ત્રીય વર્તણુક (statistical behaviour) ગણી શકાય છે. તે દિશામાંનું પ્રથમ પરિણામ 19મી સદીના અંતમાં સાબિત કરાયેલ prime number theorem છે, જે કહે છે કે, યાદૃચ્છીક રીતે (randomly) પસંદ કરેલ સંખ્યા n અવિભાજય હોય તેની સંભાવના તેના અંકોની સંખ્યાના વ્યસ્ત પ્રમાણમાં, અથવા nના લઘુગુણક ના સમપ્રમાણમાં હોય છે.
અવિભાજ્ય સંખ્યાઓ વિશેના ઘણા પ્રશ્નો અનુત્તર છે, જેમ કે Goldbach's conjecture (એટલે કે ૨થી મોટી દરેક યુગ્મ પૂર્ણાંક સંખ્યાને બે અવિભાજ્ય સંખ્યાઓના સરવાળા તરીકે દર્શાવી શકાય), અને the twin prime conjecture (એટલે કે જેમનો તફાવત ૨ હોય તેવી અવિભાજ્ય સંખ્યાઓની અનંત જોડી (pair) મળે). આવા પ્રશ્નો એ અંકગણિતની વિવિધ શાખાઓ, જે સંખ્યાઓના analytic અથવા બૈજીક (algebraic) ગુણધર્મો પર કેન્દ્રિત હોય, તેના વિકાસમાં ફાળો આપ્યો છે. અવિભાજ્ય સંખ્યાઓનો information technologyમાં ઘણા કાર્યોમાં ઉપયોગ થાય છે, જેમ કે public-key cryptography, જે મોટી સંખ્યાઓના અવિભાજ્ય અવયવ પાડવામાં પડતી મુશ્કેલીના ગુણધર્મોનો ઉપયોગ કરે છે. અવિભાજ્ય સંખ્યાઓ ને કારણે અન્ય ગાણિતિક ક્ષેત્રો (domains) જેમકે બીજગણિત માં ઘણા સામાન્યીકરણ (generalization) ઉદ્ભવે છે, જેમ કે prime elements અને prime ideals.
જે પ્રાકૃતિક સંખ્યા (એટલે કે 1, 2, 3, 4, 5, 6 વગેરે) ને માત્ર બે જ ધન અવયવ (ભાજક, divisors), ૧ અને સંખ્યા પોતે, હોય, તેને અવિભાજ્ય સંખ્યા કહે છે. [સંદર્ભ 1] ૧થી મોટી એવી પ્રાકૃતિક સંખ્યાઓ કે જે અવિભાજ્ય ન હોય, તેને વિભાજ્ય સંખ્યા કહે છે.
૧ થી ૬ની સંખ્યાઓમાં, 2, 3, અને 5 અવિભાજ્ય છે, જ્યારે 1, 4, અને 6 અવિભાજ્ય નથી. નીચેના કારણોસર 1ને અવિભાજ્ય ગણવામાં આવતો નથી. 2 અવિભાજ્ય છે, કારણ કે તેના પ્રાકૃતિક અવયવો માત્ર ૧ અને ૨ છે. પછી, 3 પણ અવિભાજ્ય છે: 1 અને 3 ૩ ને નિઃશેષ ભાગી શકે છે, પરંતુ 3 ને 2 વડે ભાગતાં ૧ શેષ વધે છે. તેથી ૩ અવિભાજ્ય છે. પરંતુ 4 વિભાજ્ય છે, કારણ કે (1 અને 4 ઉપરાંત) ૨ પણ 4ને નિઃશેષ ભાગી શકે છે.
5 ફરીથી વિભાજ્ય છે: 2, 3, કે 4 કોઈ પણ 5ને ભાગી શકતું નથી. પછી, ૬ એ ૨ અને ૩ વડે વિભાજ્ય છે, કારણ કે 6 = 2 · 3.
તેથી, 6 અવિભાજ્ય સંખ્યા નથી. અહી જમણી તરફની છબી દર્શાવે છે કે ૧૨ અવિભાજ્ય નથી: 12 = 3 · 4. 2થી મોટી કોઈ પણ યુગ્મ સંખ્યા અવિભાજ્ય નથી, કારણ કે વ્યાખ્યા મુજબ, તેવી કોઈ પણ સંખ્યા nને ઓછામાં ઓછા ૩ ભિન્ન અવયવો, નામે 1, 2, અને n હોય. તેથી સાબિત થાય કે n અવિભાજ્ય સંખ્યા નથી. તેથી જ, odd prime (અયુગ્મ અવિભાજ્ય સંખ્યા) એટલે ૨થી મોટી કોઈ પણ અવિભાજ્ય સંખ્યા. તેવી જ રીતે, સામાન્ય દશાંશ પદ્ધતિમાં લખતી વખતે, 5થી મોટી દરેક અવિભાજ્ય સંખ્યાનો એકમનો અંક 1, 3, 7, કે 9 જ હોય છે, કારણ કે યુગ્મ સંખ્યાઓ ૨ના અવયવી (ગુણિત, multiple) છે અને 0 કે 5 જેનો એકમનો અંક હોય તેવી સંખ્યાઓ 5ની ગુણિત હોય છે.
જો n એક પ્રાકૃતિક સંખ્યા હોય, તો 1 અને n, nને નિઃશેષ ભાગી શકે. તેથી, અવિભાજ્યતાની શરત નીચે મુજબ પણ લખી શકાય: કોઈ પણ સંખ્યા અવિભાજ્ય છે, જો તે ૧થી મોટી હોય, અને જો
પૈકી કોઈ પણ nને નિઃશેષ ભાગી ન શકે. એ કહેવાની અન્ય એક રીત પણ છે: કોઈ સંખ્યા n > 1 ને (૧થી મોટા) કોઈ પણ બે પૂર્ણાંકો a અને bના ગુણાકાર સ્વરૂપે ન લખી શકાય, તો તે અવિભાજ્ય છે:
બીજા શબ્દોમાં, જો n વસ્તુઓને એક કરતા વધુ વસ્તુઓ સમાવતાં નાના સમાન કદ (size)ના સમૂહમાં વિભાજીત ન કરી શકાય, તો n અવિભાજ્ય છે.
બધી અવિભાજ્ય સંખ્યાઓના ગણને ઘણી વખત P વડે દર્શાવાય છે.
પ્રથમ 168 અવિભાજ્ય સંખ્યાઓ (એટલે કે ૧૦૦૦થી નાની બધી અવિભાજ્ય સંખ્યાઓ) નીચે મુજબ છે:
અંકગણિત (number theory) અને ગણિતમાં અવિભાજ્ય સંખ્યાઓનું મહત્ત્વ અંકગણિતના મૂળભૂત પ્રમેય (fundamental theorem of arithmetic)ને કારણે ખુબ વધારે છે. પ્રમેય એમ છે કે "૧થી મોટી દરેક પ્રાકૃતિક સંખ્યાને એક અથવા વધુ અવિભાજ્ય સંખ્યાઓના ગુણાકાર સ્વરૂપે (અવિભાજ્ય અવયવોના ક્રમને બાદ કરતા) અનન્ય રીતે લખી શકાય."[1] આથી, અવિભાજ્ય સંખ્યાઓને પ્રાકૃતિક સંખ્યાઓના "મૂળભૂત રચનાત્મક એકમ" (basic building blocks) ગણી શકાય. ઉદાહરણ તરીકે:
23244 | = 2 · 2 · 3 · 13 · 149 |
= 22 · 3 · 13 · 149. (22 ૨નો વર્ગ અથવા બીજી ઘાત દર્શાવે છે.) |
આ ઉદાહરણની જેમ, એક જ અવિભાજ્ય અવયવ પુનરાવર્તન પામી શકે. સંખ્યા nનું, એક અવયવીકરણ
(સાન્ત સંખ્યાના) અવિભાજ્ય અવયવો p1, p2, ... થી pt માં કરવામાં આવે, તો તેને nનું અવિભાજ્ય અવયવીકરણ કહે છે. અંકગણિતના મૂળભૂત પ્રમેયને અન્ય રીતે એમ પણ જણાવી શકાય કે કોઈપણ અવિભાજ્ય અવયવીકરણ અવયવોના ક્રમ સિવાય એક સમાન હોય છે. તેથી, મોટી સંખ્યાઓના અવયવીકરણ માટે ઘણા અવિભાજ્ય અવયવીકરણના algorithms ઉપલબ્ધ છે, પણ તે બધા એક સમાન જ પરિણામ આપે છે.
જો p અવિભાજ્ય સંખ્યા હોય અને p પૂર્ણાંકોના ગુણાકાર ab ને ભાગી શકે, તો p a ને ભાગી શકે અથવા p bને ભાગી શકે. આ વિધાન યુક્લીડના ઉપપ્રમેય (Euclid's lemma) તરીકે જાણીતું છે.[2] તેનો ઉપયોગ અવિભાજ્ય અવયવીકરણની અનન્યતાની કેટલીક સાબિતીઓમાં થાય છે.
મોટા ભાગના ગ્રીકો ૧ને એક સંખ્યા પણ ગણતા નહિ,[3] તેથી તેમને ૧ અવિભાજ્ય છે કે કેમ તે પ્રશ્ન થયો નહિ. યુરોપમાં મધ્યયુગ અને પુનર્જાગૃતિ (Renaissance) સમયે ઘણાં યુરોપિયન ગણિતજ્ઞો ૧ને પ્રથમ અવિભાજ્ય સંખ્યા ગણતાં થયાં.[4] મધ્ય ૧૮મી શતાબ્દીમાં ક્રિશ્ચન ગોલ્ડબેક એ લિયૉનાર્ડ યુલર સાથેના તેના પ્રસિદ્ધ પત્ર-વ્યવહારમાં ૧ને પ્રથમ અવિભાજ્ય સંખ્યા ગણાવી હતી; જોકે, યુલર પોતે ૧ને અવિભાજ્ય સંખ્યા ગણતો ન હતો.[5] ૧૯મી સદીમાં પણ ઘણા ગણિતજ્ઞો ૧ને અવિભાજ્ય ગણતાં. જેમ કે, Derrick Norman Lehmerની 1,00,06,721 સુધીની અવિભાજ્ય સંખ્યાઓની યાદી, જે છેક ૧૯૫૬માં પુનઃમુદ્રણ પામી હતી, [6] તેમાં ૧ને સૌપ્રથમ અવિભાજ્ય સંખ્યા ગણાવાઈ હતી.[7] Henri Lebesgue છેલ્લો વ્યાવસાયિક (professional) ગણિતજ્ઞ હતો જે ૧ને અવિભાજ્ય ગણતો.[8] ૨૦મી સદીની શરૂઆતથી ગણિતજ્ઞોમાં સર્વસંમતિ સધાઈ કે ૧ અવિભાજ્ય સંખ્યા નથી, પણ તે "unit"(એકમ) નામના સ્વતંત્ર વર્ગ (કોટિ)માં છે.[4]
ઘણું ગાણિતિક કાર્ય ૧ને અવિભાજ્ય ગણીએ તો પણ સાચું જ રહે, પણ (ઉપર્યુક્ત) યુક્લીડનો અંકગણિતનો મૂળભૂત સિદ્ધાંત યથા-તથ ન રહે (તેનું સ્વરૂપ બદલાઈ જાય). ઉદાહરણ તરીકે, સંખ્યા 15નું અવયવીકરણ 3 · 5 અને 1 · 3 · 5 તરીકે કરી શકાય; જો 1ને અવિભાજ્ય ગણવામાં આવી હોત, તો આ બે અવયવીકરણો ૧૫ના બે જુદા અવિભાજ્ય અવયવો ગણાત, જેથી પ્રમેયનું વિધાન બદલવું પડ્યું હોત. તેવી જ રીતે, જો ૧ને અવિભાજ્ય ગણવામાં આવે, તો sieve of Eratosthenes (એરાટોસ્થેનેસની ચાળણી) બરાબર કામ ન કરે: તે ચાળણીની બદલેલી આવૃત્તિ ૧ને અવિભાજ્ય ગણીને તેના બધા જ ગુણિતો (એટલે કે બધી જ સંખ્યાઓ) દૂર કરી નાખે, અને માત્ર સંખ્યા ૧ આઉટપૂટ આપે. વધુમાં, અવિભાજ્ય સંખ્યાઓના ઘણા ગુણધર્મો, જેમ કે સંખ્યાનો તેના યુલર ટોશન્ટ વિધેય અથવા અવયવોના સરવાળાની કિંમત સાથેનો વિશેષ સંબંધ, ૧માં જોવા મળતા નથી.[9]
જે પ્રાકૃતિક સંખ્યા (એટલે કે 1, 2, 3, 4, 5, 6 વગેરે) ને માત્ર બે જ ધન અવયવ (ભાજક, divisors), ૧ અને સંખ્યા પોતે, હોય, તેને અવિભાજ્ય સંખ્યા કહે છે. [સંદર્ભ 1] ૧થી મોટી એવી પ્રાકૃતિક સંખ્યાઓ કે જે અવિભાજ્ય ન હોય, તેને વિભાજ્ય સંખ્યા કહે છે.
પ્રાચીન મિસરવાસીઓ (ઈજીપ્તવાસીઓ)ના હયાત દસ્તાવેજો (રેકોર્ડ્સ)માં કેટલાક સંકેતો (hints) છે કે તેમને અવિભાજ્ય સંખ્યાઓ વિષે થોડું જ્ઞાન હતું: ઉદાહરણ તરીકે, the Rhind papyrusમાંના ઇજીપ્તી અપૂર્ણાંકોનું સ્વરૂપ અવિભાજ્ય અને વિભાજ્ય સંખ્યાઓ માટે બહુ જૂદા-જૂદા છે. પરંતુ, અવિભાજ્ય સંખ્યાઓના અલગથી અભ્યાસની જૂનામાં જૂની હયાત નોંધો પ્રાચીન ગ્રીકોની છે. ૩૦૦ ઈ.સ. પૂર્વેની આસપાસ લખાયેલ ગ્રંથ "યુક્લીડના તત્વો"માં અવિભાજ્ય સંખ્યાઓને લગતાં, અવિભાજ્ય સંખ્યાઓની અનંતતા અને અંકગણિતનું મૂળભૂત પ્રમેય સહીતના, કેટલાક અગત્યના પ્રમેયો છે. યુક્લીડે Mersenne ની અવિભાજ્ય સંખ્યા માંથી perfect સંખ્યા કેમ રચી કાઢવી, તે પણ જણાવ્યું છે. Eratosthenesની ચાળણી, જેનો યશ Eratosthenesને ફાળે જાય છે, તે અવિભાજ્ય સંખ્યાઓ શોધવાની એક સરળ રીત છે, જો કે આજકાલ સંગણકો (કમ્પ્યુટરો) વડે શોધાતી નવી અવિભાજ્ય સંખ્યાઓ આ રીતે શોધાતી નથી.
ગ્રીકો પછીના સમયમાં, 17મી સદી સુધી અવિભાજ્ય સંખ્યાઓનો ઝાઝો અભ્યાસ થયો નહિ. ૧૬૪૦માં Pierre de Fermat એ (સાબિતી વિના) ફર્મીના નાના પ્રમેયનું વિધાન આપ્યું હતું (જે પાછળથી લિબનીત્ઝ અને યુલર એ સાબિત કર્યુ.). ફર્મીએ એ પણ (અટકળથી) વિધાન સાબિતી વિના આપ્યું કે 22n + 1 સ્વરૂપની બધી સંખ્યાઓ અવિભાજ્ય જ હોય (તેમને ફર્મી સંખ્યાઓ કહે છે.) અને n = 4 (or 216 + 1) સુધી આને ચકાસ્યું. જો કે તરત તે પછીની ફર્મી સંખ્યાઓ 232 + 1 વિભાજ્ય છે (કારણકે એનો એક અવયવ ૬૪૧ છે), જેમ યુલરે પછીથી શોધ્યું, અને હકીકતે તે પછીની કોઈ અવિભાજ્ય ફર્મી સંખ્યા જ્ઞાત નથી (એટલે કે એનાથી મોટી બધી જ ફર્મી સંખ્યાઓ વિભાજ્ય છે). ફ્રેંચ પાદરી Marin Mersenne એ 2p − 1 સ્વરૂપની અવિભાજ્ય સંખ્યાઓનો અભ્યાસ કર્યો, જ્યાં p એક અવિભાજ્ય સંખ્યા છે. તેવી સંખ્યાઓને તેમના માનમાં Mersenne primes (માર્સેનેની અવિભાજ્ય સંખ્યાઓ) કહે છે.
યુલરનું અંક-સિધ્ધાંત (નમ્બર થીયરી) પરનું ઘણું કાર્ય અવિભાજ્ય સંખ્યાઓ વિશેના ઘણા ગુણધર્મો ધરાવે છે. તેણે દર્શાવ્યું કે અનંત શ્રેઢી 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … નો સરવાળો અનંત છે. 1747માં તેણે દર્શાવ્યું કે યુગ્મ perfect numbers હંમેશા 2p−1(2p − 1) સ્વરૂપની હોય છે, જ્યાં બીજો અવયવ એક Mersenne અવિભાજ્ય સંખ્યા છે.
19મી સદીની શરૂઆતમાં, Legendre અને Gauss એ સ્વતંત્ર રીતે સાબિતી વગર અટકળ કરી કે જેમ x અનંતને અનુલક્ષે, તેમ x સુધીની અવિભાજ્ય સંખ્યાઓની સંખ્યા x/ln(x)ને અનુલક્ષે (અનંતસ્પર્શે/ ઉપગીય) છે, જ્યાં ln(x) xનો પ્રાકૃતિક લઘુગુણક છે. Riemannના તેના ૧૮૫૯ના ઝેટા વિધેય પરના સંશોધન-પત્ર માંના વિચારો એ એક પ્રોગ્રામની રૂપરેખા આપી હતી કે જે 'અવિભાજ્ય સંખ્યા પ્રમેય'ની સાબિતી આપી શકે. તે રૂપરેખા Hadamard અને de la Vallée Poussin એ પૂરી કરી હતી, જેમણે સ્વતંત્ર રીતે 'અવિભાજ્ય સંખ્યા પ્રમેય' 1896માં સાબિત કર્યું.
મોટી સંખ્યાઓને પ્રયત્ન ભાગાકારની રીતે અવિભાજ્ય સાબિત કરતી નથી. ઘણા ગણિતશાસ્ત્રીઓએ (મુખ્યત્વે કોઈ ખાસ સ્વરૂપની) મોટી સંખ્યાઓની અવિભાજ્યતા કસોટી પર કાર્ય કર્યું છે. જેમાં ફર્મી સંખ્યાઓ માટેની Pépinની કસોટી (1877), Prothનું પ્રમેય (1878 આસપાસ), Lucas–Lehmer અવિભાજ્યતા કસોટી (1856માં ઉદ્ભૂત),[10] અને સામાન્યીકૃત Lucas અવિભાજ્યતા કસોટી. વધુ આધુનિક અલગોરિધમ APRT-CL, ECPP, અને AKS છે, જે યાદૃચ્છીક સંખ્યાઓ પર કામ કરે છે, પણ ઘણા ધીમા રહે છે.
ઘણા લાંબા સમય સુધી, શુદ્ધ ગણિતશાસ્ત્રની બહાર અવિભાજ્ય સંખ્યાઓના ઉપયોગો અતિશય મર્યાદિત મનાતા હતા.[11] આ માન્યતા 1970ના દાયકામાં બદલાઈ જયારે public-key cryptography ના સિદ્ધાંતો શોધાયા, જેમાં RSA ક્રીપ્ટોપ્રણાલિ અલગોરિધમ જેવા પ્રથમ અલગોરિધમનો પાયો અવિભાજ્ય સંખ્યાઓ બનાવતાં હતાં.
1951થી સૌથી મોટી અવિભાજ્ય સંખ્યાઓ સંગણકો વડે જ શોધાતી આવી છે. બહુ મોટી અવિભાજ્ય સંખ્યાઓની શોધમાં ગણિતના વર્તુળોની બહાર પણ રસ સર્જાયો છે. Great Internet Mersenne Prime Search અને અન્ય મોટી અવિભાજ્ય સંખ્યાઓ શોધવાના વિતરિત ગણતરી (distributed computing) પ્રોજેક્ટ્સ પ્રચલિત બન્યા છે, પરંતુ ગણિતશાસ્ત્રીઓ અવિભાજ્ય સંખ્યાઓના સિદ્ધાંત સાથે સંઘર્ષરત છે.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.