સભ્ય:Ravijoshi/અવિભાજ્ય સંખ્યા

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 દશાંશ અંકો છે.

Euclid એ ઈ.સ. પૂર્વે ૩૦૦માં દર્શાવ્યા મુજબ (યુક્લીડનું પ્રમેય) અવિભાજ્ય સંખ્યાઓ અનંત છે. કોઈ જાણીતા, સાદા સૂત્ર વડે અવિભાજ્ય સંખ્યાઓને વિભાજ્ય સંખ્યાઓથી અલગ પાડી શકાતી નથી. જો કે અવિભાજ્ય સંખ્યાઓનું વિતરણ, એટલે કે આંકડાશાસ્ત્રીય વર્તણુક (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 (sequence A000040 in the OEIS).

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

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

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

ઈતિહાસ

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

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

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

ગ્રીકો પછીના સમયમાં, 17મી સદી સુધી અવિભાજ્ય સંખ્યાઓનો ઝાઝો અભ્યાસ થયો નહિ. ૧૬૪૦માં Pierre de Fermat એ (સાબિતી વિના) Fermat's little theorem (ફર્મીના નાના પ્રમેય)નું વિધાન આપ્યું હતું (જે પાછળથી Leibniz અને Euler એ સાબિત કર્યુ.). ફર્મીએ (fermet) એ પણ (અટકળથી) વિધાન સાબિતી વિના આપ્યું કે 2²ⁿ + 1 સ્વરૂપની બધી સંખ્યાઓ અવિભાજ્ય જ હોય (તેમને Fermat numbers કહે છે.) અને n = 4 (or 216 + 1) સુધી આને ચકાસ્યું. જો કે તરત તે પછીની Fermat number 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ની Fermat સંખ્યાઓ પર આધારિત સાબિતી, Furstenbergની સામાન્ય સંસ્થિતિવિદ્યા આધારિત સાબિતી, અને Kummerનું સુંદર સાબિતી.

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

Euclid's proof (Book IX, Proposition 20) considers any finite set S of primes. The key idea is to consider the product of all these numbers plus one:

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

Like any other natural number, N is divisible by at least one prime number (it is possible that N itself is prime).

None of the primes by which N is divisible can be members of the finite set S of primes with which we started, because dividing N by any one of these leaves a remainder of 1. Therefore, the primes by which N is divisible are additional primes beyond the ones we started with. Thus any finite set of primes can be extended to a larger finite set of primes.

It is often erroneously reported that Euclid begins with the assumption that the set initially considered contains all prime numbers, leading to a contradiction, or that it contains precisely the n smallest primes rather than any arbitrary finite set of primes. Today, the product of the smallest n primes plus 1 is conventionally called the nth Euclid number.

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 

Prime number generators and calculators

• Prime Number Checker identifies the smallest prime factor of a number.
• Fast Online primality test with factorization makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
• Huge database of prime numbers
• Prime Numbers up to 1 trillion