અવિભાજ્ય સંખ્યા

Cuisenaire સળિયા વડે પ્રદર્શન કે સંખ્યા ૭ અવિભાજ્ય છે, કારણ કે તે માત્ર ૧ અને ૭ વડે વિભાજ્ય છે.

અવિભાજ્ય સંખ્યા (prime number) એક એવી પ્રાકૃતિક સંખ્યા છે, જે ૧ કરતાં મોટી છે અને જેને પોતાના અને ૧ના સિવાય અન્ય કોઈ અવયવ નથી. ૧ કરતા મોટી દરેક પ્રાકૃતિક સંખ્યા, જો અવિભાજ્ય ન હોય, તો તે વિભાજ્ય સંખ્યા કહેવાય છે. ઉદાહરણ તરીકે, 5 એ અવિભાજ્ય છે, કારણ કે તેના ધન પૂર્ણાંક અવયવ માત્ર 1 અને 5 છે, જ્યારે 6 વિભાજ્ય છે, કારણ કે તેના અવયવો 1 અને 6 ઉપરાંત 2 અને 3 છે. અંકગણિતનો મૂળભૂત પ્રમેય, અવિભાજ્ય સંખ્યાઓનું અંકગણિતમાં મહત્ત્વ સાબિત કરે છે: ૧ કરતાં મોટા કોઈ પણ પૂર્ણાંકને અવિભાજ્ય અવયવોના ગુણાકાર તરીકે અનન્ય રીતે દર્શાવી શકાય (જો કે ગુણાકારમાં તેમનો ક્રમ બદલાઈ શકે). આ પ્રમેયની વિશિષ્ટતાને માટે જરૂરી છે કે ૧ને અવિભાજ્ય ગણવામાં ન આવે, કારણ કે ૧ને કોઈ પણ અવયવીકરણમાં ગમે તેટલી વખત (arbitrarily many times) લઇ શકાય, દા. ત., 3, 1 · 3, 1 · 1 · 3, વગેરે, જે બધા ૩ના માન્ય અવયવીકરણ છે.

અવિભાજ્ય હોવા કે ન હોવાના ગુણધર્મને અવિભાજ્યતા કહે છે. આપેલ સંખ્યા nની અવિભાજ્યતા ચકાસવાની એક ધીમી પણ સહેલી રીત trial division છે. તે રીતમાં ચકાસવાનું હોય છે કે n એ 2 અને ${\sqrt {n}}$. મોટી સંખ્યાઓની અવિભાજ્યતા ચકાસવા માટે 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] ૧થી મોટી એવી પ્રાકૃતિક સંખ્યાઓ કે જે અવિભાજ્ય ન હોય, તેને વિભાજ્ય સંખ્યા કહે છે.

સંખ્યા 12 અવિભાજ્ય નથી, કારણ કે ૧૨ વસ્તુઓને ૩ સમાન કદ (size)ના 4 સ્તંભ(કોલમ)માં (અન્ય રીતો સિવાય) ગોઠવી શકાય. 11 વસ્તુઓને સમાન કદ (size)ના સ્તંભ (કોલમ)માં ગોઠવવા જતા કોઈ વસ્તુ પડી રહે છે (શેષ). તેથી સંખ્યા 11 અવિભાજ્ય છે.

૧ થી ૬ની સંખ્યાઓમાં, 2, 3, અને 5 અવિભાજ્ય છે, જ્યારે 1, 4, અને 6 અવિભાજ્ય નથી. નીચેના કારણોસર 1ને અવિભાજ્ય ગણવામાં આવતો નથી. 2 અવિભાજ્ય છે, કારણ કે તેના પ્રાકૃતિક અવયવો માત્ર ૧ અને ૨ છે. પછી, 3 પણ અવિભાજ્ય છે: 1 અને 3 ૩ ને નિઃશેષ ભાગી શકે છે, પરંતુ 3 ને 2 વડે ભાગતાં ૧ શેષ વધે છે. તેથી ૩ અવિભાજ્ય છે. પરંતુ 4 વિભાજ્ય છે, કારણ કે (1 અને 4 ઉપરાંત) ૨ પણ 4ને નિઃશેષ ભાગી શકે છે.

4 = 2 · 2.

5 ફરીથી વિભાજ્ય છે: 2, 3, કે 4 કોઈ પણ 5ને ભાગી શકતું નથી. પછી, ૬ એ ૨ અને ૩ વડે વિભાજ્ય છે, કારણ કે 6 = 2 · 3. 

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ને નિઃશેષ ભાગી શકે. તેથી, અવિભાજ્યતાની શરત નીચે મુજબ પણ લખી શકાય: કોઈ પણ સંખ્યા અવિભાજ્ય છે, જો તે ૧થી મોટી હોય, અને જો

2, 3, ..., n − 1

પૈકી કોઈ પણ nને નિઃશેષ ભાગી ન શકે. એ કહેવાની અન્ય એક રીત પણ છે: કોઈ સંખ્યા n > 1 ને (૧થી મોટા) કોઈ પણ બે પૂર્ણાંકો a અને bના ગુણાકાર સ્વરૂપે ન લખી શકાય, તો તે અવિભાજ્ય છે: 

n = a · b.

બીજા શબ્દોમાં, જો n વસ્તુઓને એક કરતા વધુ વસ્તુઓ સમાવતાં નાના સમાન કદ (size)ના સમૂહમાં વિભાજીત ન કરી શકાય, તો n અવિભાજ્ય છે.

બધી અવિભાજ્ય સંખ્યાઓના ગણને ઘણી વખત P વડે દર્શાવાય છે.

પ્રથમ 168 અવિભાજ્ય સંખ્યાઓ (એટલે કે ૧૦૦૦થી નાની બધી અવિભાજ્ય સંખ્યાઓ) નીચે મુજબ છે:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 (OEISમાં A000040 શ્રેણી).

અંકગણિતનું મૂળભૂત પ્રમેય

અંકગણિત (number theory) અને ગણિતમાં અવિભાજ્ય સંખ્યાઓનું મહત્ત્વ અંકગણિતના મૂળભૂત પ્રમેય (fundamental theorem of arithmetic)ને કારણે ખુબ વધારે છે. પ્રમેય એમ છે કે "૧થી મોટી દરેક પ્રાકૃતિક સંખ્યાને એક અથવા વધુ અવિભાજ્ય સંખ્યાઓના ગુણાકાર સ્વરૂપે (અવિભાજ્ય અવયવોના ક્રમને બાદ કરતા) અનન્ય રીતે લખી શકાય." આથી, અવિભાજ્ય સંખ્યાઓને પ્રાકૃતિક સંખ્યાઓના "મૂળભૂત રચનાત્મક એકમ" (basic building blocks) ગણી શકાય. ઉદાહરણ તરીકે:

23244	= 2 · 2 · 3 · 13 · 149
= 22 · 3 · 13 · 149. (22 ૨નો વર્ગ અથવા બીજી ઘાત દર્શાવે છે.)

આ ઉદાહરણની જેમ, એક જ અવિભાજ્ય અવયવ પુનરાવર્તન પામી શકે. સંખ્યા nનું, એક અવયવીકરણ

n = p₁ · p₂ · ... · p_t

(સાન્ત સંખ્યાના) અવિભાજ્ય અવયવો p₁, p₂, ... થી p_t માં કરવામાં આવે, તો તેને nનું અવિભાજ્ય અવયવીકરણ કહે છે. અંકગણિતના મૂળભૂત પ્રમેયને અન્ય રીતે એમ પણ જણાવી શકાય કે કોઈપણ અવિભાજ્ય અવયવીકરણ અવયવોના ક્રમ સિવાય એક સમાન હોય છે. તેથી, મોટી સંખ્યાઓના અવયવીકરણ માટે ઘણા અવિભાજ્ય અવયવીકરણના algorithms ઉપલબ્ધ છે, પણ તે બધા એક સમાન જ પરિણામ આપે છે.

જો p અવિભાજ્ય સંખ્યા હોય અને p પૂર્ણાંકોના ગુણાકાર ab ને ભાગી શકે, તો p a ને ભાગી શકે અથવા p bને ભાગી શકે. આ વિધાન યુક્લીડના ઉપપ્રમેય (Euclid's lemma) તરીકે જાણીતું છે. તેનો ઉપયોગ અવિભાજ્ય અવયવીકરણની અનન્યતાની કેટલીક સાબિતીઓમાં થાય છે.

૧ની અવિભાજ્યતા

મોટા ભાગના ગ્રીકો ૧ને એક સંખ્યા પણ ગણતા નહિ, તેથી તેમને ૧ અવિભાજ્ય છે કે કેમ તે પ્રશ્ન થયો નહિ. યુરોપમાં મધ્યયુગ અને પુનર્જાગૃતિ (Renaissance) સમયે ઘણાં યુરોપિયન ગણિતજ્ઞો ૧ને પ્રથમ અવિભાજ્ય સંખ્યા ગણતાં થયાં. મધ્ય ૧૮મી શતાબ્દીમાં ક્રિશ્ચન ગોલ્ડબેક એ લિયૉનાર્ડ યુલર સાથેના તેના પ્રસિદ્ધ પત્ર-વ્યવહારમાં ૧ને પ્રથમ અવિભાજ્ય સંખ્યા ગણાવી હતી; જોકે, યુલર પોતે ૧ને અવિભાજ્ય સંખ્યા ગણતો ન હતો. ૧૯મી સદીમાં પણ ઘણા ગણિતજ્ઞો ૧ને અવિભાજ્ય ગણતાં. જેમ કે, Derrick Norman Lehmerની 1,00,06,721 સુધીની અવિભાજ્ય સંખ્યાઓની યાદી, જે છેક ૧૯૫૬માં પુનઃમુદ્રણ પામી હતી,  તેમાં ૧ને સૌપ્રથમ અવિભાજ્ય સંખ્યા ગણાવાઈ હતી. Henri Lebesgue છેલ્લો વ્યાવસાયિક (professional) ગણિતજ્ઞ હતો જે ૧ને અવિભાજ્ય ગણતો. ૨૦મી સદીની શરૂઆતથી ગણિતજ્ઞોમાં સર્વસંમતિ સધાઈ કે ૧ અવિભાજ્ય સંખ્યા નથી, પણ તે "unit"(એકમ) નામના સ્વતંત્ર વર્ગ (કોટિ)માં છે.

ઘણું ગાણિતિક કાર્ય ૧ને અવિભાજ્ય ગણીએ તો પણ સાચું જ રહે, પણ (ઉપર્યુક્ત) યુક્લીડનો અંકગણિતનો મૂળભૂત સિદ્ધાંત યથા-તથ ન રહે (તેનું સ્વરૂપ બદલાઈ જાય). ઉદાહરણ તરીકે, સંખ્યા 15નું અવયવીકરણ 3 · 5 અને  1 · 3 · 5 તરીકે કરી શકાય; જો 1ને અવિભાજ્ય ગણવામાં આવી હોત, તો આ બે અવયવીકરણો ૧૫ના બે જુદા અવિભાજ્ય અવયવો ગણાત, જેથી પ્રમેયનું વિધાન બદલવું પડ્યું હોત. તેવી જ રીતે, જો ૧ને અવિભાજ્ય ગણવામાં આવે, તો  sieve of Eratosthenes (એરાટોસ્થેનેસની ચાળણી) બરાબર કામ ન કરે: તે ચાળણીની બદલેલી આવૃત્તિ ૧ને અવિભાજ્ય ગણીને તેના બધા જ ગુણિતો (એટલે કે બધી જ સંખ્યાઓ) દૂર કરી નાખે, અને માત્ર સંખ્યા ૧ આઉટપૂટ આપે. વધુમાં, અવિભાજ્ય સંખ્યાઓના ઘણા ગુણધર્મો, જેમ કે સંખ્યાનો તેના યુલર ટોશન્ટ વિધેય અથવા અવયવોના સરવાળાની કિંમત સાથેનો વિશેષ સંબંધ, ૧માં જોવા મળતા નથી.

ઈતિહાસ

જે પ્રાકૃતિક સંખ્યા (એટલે કે 1, 2, 3, 4, 5, 6 વગેરે) ને માત્ર બે જ ધન અવયવ (ભાજક, divisors), ૧ અને સંખ્યા પોતે, હોય, તેને અવિભાજ્ય સંખ્યા કહે છે.  [સંદર્ભ 1] ૧થી મોટી એવી પ્રાકૃતિક સંખ્યાઓ કે જે અવિભાજ્ય ન હોય, તેને વિભાજ્ય સંખ્યા કહે છે.

Eratosthenesની ચાળણી આપેલ સંખ્યા સુધીની બધી જ અવિભાજ્ય સંખ્યાઓ શોધવા માટેનો એક સરળ અલગોરિધમ છે. તે અલગોરિધમ, ૩જી સદીમાં, એક પ્રાચીન ગ્રીક ગણિતજ્ઞ, Eratosthenes એ બનાવ્યો હતો.

પ્રાચીન મિસરવાસીઓ (ઈજીપ્તવાસીઓ)ના હયાત દસ્તાવેજો (રેકોર્ડ્સ)માં કેટલાક સંકેતો (hints) છે કે તેમને અવિભાજ્ય સંખ્યાઓ વિષે થોડું જ્ઞાન હતું: ઉદાહરણ તરીકે, the Rhind papyrusમાંના ઇજીપ્તી અપૂર્ણાંકોનું સ્વરૂપ અવિભાજ્ય અને વિભાજ્ય સંખ્યાઓ માટે બહુ જૂદા-જૂદા છે. પરંતુ, અવિભાજ્ય સંખ્યાઓના અલગથી અભ્યાસની જૂનામાં જૂની હયાત નોંધો પ્રાચીન ગ્રીકોની છે. ૩૦૦ ઈ.સ. પૂર્વેની આસપાસ લખાયેલ ગ્રંથ "યુક્લીડના તત્વો"માં અવિભાજ્ય સંખ્યાઓને લગતાં, અવિભાજ્ય સંખ્યાઓની અનંતતા અને અંકગણિતનું મૂળભૂત પ્રમેય સહીતના, કેટલાક અગત્યના પ્રમેયો છે. યુક્લીડે Mersenne ની અવિભાજ્ય સંખ્યા માંથી perfect સંખ્યા કેમ રચી કાઢવી, તે પણ જણાવ્યું છે. Eratosthenesની ચાળણી, જેનો યશ Eratosthenesને ફાળે જાય છે, તે અવિભાજ્ય સંખ્યાઓ શોધવાની એક સરળ રીત છે, જો કે આજકાલ સંગણકો (કમ્પ્યુટરો) વડે શોધાતી નવી અવિભાજ્ય સંખ્યાઓ આ રીતે શોધાતી નથી.

ગ્રીકો પછીના સમયમાં, 17મી સદી સુધી અવિભાજ્ય સંખ્યાઓનો ઝાઝો અભ્યાસ થયો નહિ. ૧૬૪૦માં Pierre de Fermat એ (સાબિતી વિના) ફર્મીના નાના પ્રમેયનું વિધાન આપ્યું હતું (જે પાછળથી લિબનીત્ઝ અને યુલર એ સાબિત કર્યુ.). ફર્મીએ એ પણ (અટકળથી) વિધાન સાબિતી વિના આપ્યું કે 2²ⁿ + 1 સ્વરૂપની બધી સંખ્યાઓ અવિભાજ્ય જ હોય (તેમને ફર્મી સંખ્યાઓ કહે છે.) અને n = 4 (or 216 + 1) સુધી આને ચકાસ્યું. જો કે તરત તે પછીની ફર્મી સંખ્યાઓ 2³² + 1 વિભાજ્ય છે (કારણકે એનો એક અવયવ ૬૪૧ છે), જેમ યુલરે પછીથી શોધ્યું, અને હકીકતે તે પછીની કોઈ અવિભાજ્ય ફર્મી સંખ્યા જ્ઞાત નથી (એટલે કે એનાથી મોટી બધી જ ફર્મી સંખ્યાઓ વિભાજ્ય છે). ફ્રેંચ પાદરી Marin Mersenne એ 2^p − 1 સ્વરૂપની અવિભાજ્ય સંખ્યાઓનો અભ્યાસ કર્યો, જ્યાં p એક અવિભાજ્ય સંખ્યા છે. તેવી સંખ્યાઓને તેમના માનમાં Mersenne primes (માર્સેનેની અવિભાજ્ય સંખ્યાઓ) કહે છે.

યુલરનું અંક-સિધ્ધાંત (નમ્બર થીયરી) પરનું ઘણું કાર્ય અવિભાજ્ય સંખ્યાઓ વિશેના ઘણા ગુણધર્મો ધરાવે છે. તેણે દર્શાવ્યું કે અનંત શ્રેઢી 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … નો સરવાળો અનંત છે. 1747માં તેણે દર્શાવ્યું કે યુગ્મ perfect numbers હંમેશા 2^p−1(2^p − 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માં ઉદ્ભૂત), અને સામાન્યીકૃત Lucas અવિભાજ્યતા કસોટી. વધુ આધુનિક અલગોરિધમ APRT-CL, ECPP, અને AKS છે, જે યાદૃચ્છીક સંખ્યાઓ પર કામ કરે છે, પણ ઘણા ધીમા રહે છે.

ઘણા લાંબા સમય સુધી, શુદ્ધ ગણિતશાસ્ત્રની બહાર અવિભાજ્ય સંખ્યાઓના ઉપયોગો અતિશય મર્યાદિત મનાતા હતા. આ માન્યતા 1970ના દાયકામાં બદલાઈ જયારે public-key cryptography ના સિદ્ધાંતો શોધાયા, જેમાં RSA ક્રીપ્ટોપ્રણાલિ અલગોરિધમ જેવા પ્રથમ અલગોરિધમનો પાયો અવિભાજ્ય સંખ્યાઓ બનાવતાં હતાં.

1951થી સૌથી મોટી અવિભાજ્ય સંખ્યાઓ સંગણકો વડે જ શોધાતી આવી છે. બહુ મોટી અવિભાજ્ય સંખ્યાઓની શોધમાં ગણિતના વર્તુળોની બહાર પણ રસ સર્જાયો છે. Great Internet Mersenne Prime Search અને અન્ય મોટી અવિભાજ્ય સંખ્યાઓ શોધવાના વિતરિત ગણતરી (distributed computing) પ્રોજેક્ટ્સ પ્રચલિત બન્યા છે, પરંતુ ગણિતશાસ્ત્રીઓ અવિભાજ્ય સંખ્યાઓના સિદ્ધાંત સાથે સંઘર્ષરત છે.

અવિભાજ્ય સંખ્યાઓની સંખ્યા

અવિભાજ્ય સંખ્યાઓ અનંત છે. એ કહેવાની બીજી રીત એ છે કે આ અવિભાજ્ય સંખ્યાઓની શ્રેણી:

2, 3, 5, 7, 11, 13, ...

ને અંત નથી. આ વિધાન પ્રાચીન ગ્રીક ગણિતશાસ્ત્રી યુક્લીડના માનમાં યુક્લીડનું પ્રમેય કહેવાય છે, કારણ કે આની પ્રથમ જાણીતી સાબિતી તેણે આપી હતી. અવિભાજ્ય સંખ્યાઓની અનંતતાની બીજી ઘણી સાબિતીઓ પ્રાપ્ય છે, જેમાં યુલરની વિશ્લેષણાત્મક સાબિતી, Goldbachની ફર્મી સંખ્યાઓ પર આધારિત સાબિતી, Furstenbergની સામાન્ય સંસ્થિતિવિદ્યા આધારિત સાબિતી, અને Kummerનું સુંદર પ્રમેય.

યુક્લીડની સાબિતી

યુક્લીડની સાબિતી (પુસ્તક નંબર IX, Proposition 20) અવિભાજ્ય સંખ્યાઓના કોઈ પણ સાંત ગણ Sને ધ્યાનમાં લે છે.અ બધી સંખ્યાઓનો ગુણાકાર વત્તા એક ધ્યાનમાં લેવાનો મુખ્ય વિચાર છે:

$N=1+\prod _{p\in S}p.$

બીજી દરેક પ્રાકૃતિક સંખ્યાની જેમ, N ઓછામાં ઓછી એક અવિભાજ્ય સંખ્યાથી વિભાજ્ય છે (એ પણ શક્ય છે કે N પોતે જ અવિભાજ્ય હોય).

N જેના વડે વિભાજ્ય હોય એવી એકે અવિભાજ્ય સંખ્યા અવિભાજ્યોના સાંત ગણ S (જેનાથી આપણે શરૂઆત કરી હતી) એમાં હોઈ શકે નહિ, કારણ કે એમનાથી Nને ભાગતા એક શેષ વધે. તેથી, જે અવિભાજ્ય સંખ્યાઓ વડે N વિભાજ્ય છે, એ આપણે શરૂઆતમાં લીધેલી અવિભાજ્ય સંખ્યાઓ કરતા મોટી છે. તેથી અવિભાજ્ય સંખ્યાઓનો કોઈ પણ સાંત ગણ, અવિભાજ્યોના એક મોટા સાંત ગણમાં વિસ્તારી શકાય.

ઘણી વખત ભૂલથી એવું કહેવાય છે કે યુક્લીડ બધી અવિભાજ્ય સંખ્યાઓના ગણથી શરૂઆત કરી હતી, જે એક વિસંગતિ/અનિષ્ટાપત્તી (contradiction) તરફ લઇ જાય છે, અથવા એમ કે કોઈ પણ યાદૃચ્છીક અવિભાજ્યોથી શરુ કરવાને બદલે સૌથી નાની n પ્રાકૃતિક સંખ્યાઓથી શરૂઆત કરી હતી. હવે, રૂઢિગત રીતે સૌથી નાની n અવિભાજ્ય સંખ્યાઓનો ગુણાકાર વત્તા એકને nમી યુક્લીડ સંખ્યા કહેવાય છે.

યુલરની વિશ્લેષણાત્મક સાબિતી

યુલરની સાબિતીમાં અવિભાજ્ય સંખ્યાઓના વ્યસ્તના આંશિક સરવાળાનો ઉપયોગ થયો છે,

$S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.$

કોઈ પણ યાદૃચ્છીક વાસ્તવિક સંખ્યા x માટે, એવી કોઈ અવિભાજ્ય સંખ્યા p અસ્તિત્વ ધરાવે કે જેથી આ આંશિક સરવાળો xથી મોટો થાય. આનાથી સાબિત થાય કે અવિભાજ્ય સંખ્યાઓ અનંત છે, કારણ કે જો તેમની સંખ્યા સાંત હોત તો સૌથી મોટી અવિભાજ્ય સંખ્યાએ સરવાળો મહત્તમ બની જાત, અને અબદ્ધ (અનંત) ન બની શકત. વધુ સુક્ષ્મ રીતે, S(p)ના વધવાનો દર, મેર્તેન્સના બીજા પ્રમેય મુજબ, દ્વિ-લઘુગુણકીય છે. સરખામણી માટે, સરવાળો

${\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}$

n અનંતગામી બને તેમ અનંત બનતો નથી (જૂઓ Baselનો કોયડો). આ રીતે, અવિભાજ્ય સંખ્યાઓ પ્રાકૃતિક સંખ્યાઓના વર્ગ કરતા વધુ સંખ્યામાં હોય છે. બ્રુનનું પ્રમેય જણાવે છે કે જોડકી અવિભાજ્ય સંખ્યાઓના વ્યસ્તનો સરવાળો,

$\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},$

સાંત છે. બ્રુનના પ્રમેયને લીધે, યુલરની રીત વડે જોડકી અવિભાજ્ય સંખ્યા અટકળ (કન્જ્ક્ચર) કે જોડકી અવિભાજ્ય સંખ્યાઓની સંખ્યા અનંત છે, તે ઉકેલવી શક્ય નથી.

Nની અવયવ હોય એવી અવિભાજ્ય સંખ્યાઓમાંથી કોઈપણ આપણે જેનાથી શરૂઆત કરી એ અવિભાજયોના સાન્ત ગણ Sમાં હોઈ શકે નહિ, કારણકે Nને તેમના વડે ભાગતા હંમેશા 1 શેષ વડે છે. તેથી, જે અવિભાજ્ય સંખ્યાઓ વડે N વિભાજ્ય હોય તે આપણે શરૂઆત કરી હતી તે સિવાયની વધારાની અવિભાજ્ય સંખ્યાઓ છે. તેથી અવિભાજયોના કોઈ પણ સાન્ત ગણને હંમેશા વધારી શકાય.

References

• Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9 
• Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9 
• Crandall, Richard; Pomerance, Carl (2005), Prime Numbers: A Computational Perspective (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-25282-7 
• Derbyshire, John (2003), Prime obsession, Joseph Henry Press, Washington, DC, ISBN 978-0-309-08549-6, MR 1968857 
• Eisenbud, David (1995), Commutative algebra, Graduate Texts in Mathematics, 150, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94268-1, MR 1322960 
• Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1 
• Furstenberg, Harry (1955), "On the infinitude of primes", The American Mathematical Monthly, Mathematical Association of America, 62 (5): 353, doi:10.2307/2307043, JSTOR 2307043 
• Green, Ben; Tao, Terence (2008), "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics, 167 (2): 481–547, arXiv:math.NT/0404188, doi:10.4007/annals.2008.167.481 
• Gowers, Timothy (2002), Mathematics: A Very Short Introduction, Oxford University Press, ISBN 978-0-19-285361-5 
• Guy, Richard K. (1981), Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90593-8 
• Havil, Julian (2003), Gamma: Exploring Euler's Constant, Princeton University Press, ISBN 978-0-691-09983-5 
• Hardy, Godfrey Harold (1908), A Course of Pure Mathematics, Cambridge University Press, ISBN 978-0-521-09227-2 
• Hardy, Godfrey Harold (1940), A Mathematician's Apology, Cambridge University Press, ISBN 978-0-521-42706-7 
• Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016 
• Hill, Peter Jensen, ed. (1995), The Messiaen companion, Portland, Or: Amadeus Press, ISBN 978-0-931340-95-6 
• Hua, L. K. (2009), Additive Theory of Prime Numbers, Translations of Mathematical Monographs, 13, AMS Bookstore, ISBN 978-0-8218-4942-2 
• Lehmer, D. H. (1909), Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington 
• McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68-15225 
• Narkiewicz, Wladyslaw (2000), The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-66289-1 
• Ribenboim, Paulo (2004), The little book of bigger primes, Berlin, New York: Springer-Verlag, ISBN 978-0-387-20169-6 
• Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9 
• Sabbagh, Karl (2003), The Riemann hypothesis, Farrar, Straus and Giroux, New York, ISBN 978-0-374-25007-2, MR 1979664 
• du Sautoy, Marcus (2003), The music of the primes સંગ્રહિત ૨૦૧૫-૦૯-૦૭ ના રોજ વેબેક મશિન, HarperCollins Publishers, ISBN 978-0-06-621070-4, MR 2060134 

અવિભાજ્ય સંખ્યાઓ શોધવા અને ગણતરી કરવા માટેની વેબસાઇટો

• અવિભાજ્ય સંખ્યા તપાસક આપેલ સંખ્યાનો નાનામાં નાનો અવિભાજ્ય અવયવ આપે છે.
• અવયવિકરણ વડે સંખ્યાની ઝડપી ઓનલાઇન અવિભાજ્ય કસોટી એલિપ્ટિક કર્વની મદદથી ગણતરી કરે છે (1000 અંક સુધીની સંખ્યાઓ માટે, જાવા જરૂરી).
• અવિભાજ્ય સંખ્યાઓનો મોટો ડેટાબેઝ
• 1 નિખર્વ સુધીની અવિભાજ્ય સંખ્યાઓ સંગ્રહિત ૨૦૨૧-૦૨-૨૭ ના રોજ વેબેક મશિન