ప్రధాన సంఖ్య

**ప్రధాన సంఖ్య** (ఆంగ్లం:prime Number) అనగా ఒకటి, అదే సంఖ్య మాత్రమే కారణాంకాలుగా గల సంఖ్య. అనగా ప్రధాన సంఖ్యకు రెండు కారణాంకాలు మాత్రమే ఉంటాయి. ప్రధాన సంఖ్య కాని సంఖ్యను సంయుక్త సంఖ్య అంటారు. ఒకటి ప్రధాన సంఖ్య కాదు, సంయుక్త సంఖ్య కాదు. ఎందువలనంటే దానికి ఒకే కారణాంకము కలదు, ఒక సంఖ్య **ప్రధాన సంఖ్య** అవునా, కాదా అని కనుక్కోవడానికి ఇప్పటి వరకు సులువయిన పధ్ధతిని ఎవరూ కనుక్కొనలేదు. ప్రధాన సంఖ్యలను అవిభాజ్య సంఖ్యలు అని కూడా అంటారు.

మొదటి 25 ప్రధాన సంఖ్యలు: 
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.

[thumb|300px|[ఇరటోస్తనీస్ జల్లెడ పద్ధతి ఒక సంఖ్యలోపు గల మొత్తం ప్రధాన సంఖ్యలన్నింటినీ కనుగొనడానికి ఒక ప్రాచీన పద్ధతి, సులభమైన పద్ధతి. దీని తరువాత వచ్చిన అట్కిన్ జల్లెడ పద్ధతి దీని కన్నా వేగమైనది, క్లిష్టతరమైనది. ఇరటోస్తనీసు జల్లెడ క్రీపూ 3వశతాబ్దానికి చెందిన ఇరటోస్తనీస్ అనే ప్రాచీన గ్రీకు గణిత శాస్త్రవేత్త చే రూపొందించబడింది]]

## చరిత్ర
ఇప్పటికీ లభ్యమౌతున్న కొన్ని ప్రాచీన ఈజిప్టు గ్రంథాలను బట్టి ఆ కాలంలోనే ఈజిప్టు జాతీయులు ప్రధాన సంఖ్యల గురించి తెలిసి ఉండేవారనడానికి ఆధారాలు ఉన్నాయి.
యవనులకి (గ్రీకు దేశస్థులకి) ప్రధాన సంఖ్యలు (prime numbers) గురించి కొంత తెలుసు. ప్రధాన సంఖ్యలు అంటే ఏమిటి? ఏదైనా n అనే ఒక సంఖ్య ప్రధాన సంఖ్య అవాలంటే దానికి రెండే రెండు కారణాంకాలు (factors) ఉండాలి: అవి 1, n అయి ఉండాలి. అప్పుడు ఆ సంఖ్యని ప్రధాన సంఖ్య అంటారు. ఉదాహరణకి 2, 3, 5, 7, 11, 13, 17 మొదలైనవి ప్రధాన సంఖ్యలు. (ఈ నిర్వచనం ప్రకారం 1 ప్రధాన సంఖ్యల జాబితాలో ఇమడదు. ఇప్పటికీ 1 ని ప్రధాన సంఖ్యగా పరిగణించిన సందర్భాలు కొన్ని పాత పుస్తకాలలో కనిపిస్తూ ఉంటాయి.)

## ఇరటోస్థనీస్ జల్లెడ ([[ఎరటోస్తనీస్ జల్లెడ|ఇరటోస్తనీస్ జల్లెడ]])

ప్రాచీన కాలంలో, ఈజిప్టు లోని అలెగ్జాండ్రియా నగరంలో, జగత్ విఖ్యాతి చెందిన బృహత్ గ్రంథాలయం ఒకటి ఉండేది. ఇరటోస్తనీస్ (Eratosthenes, క్రీ. పూ. 276-194) అనే పెద్దమనిషి ఈ గ్రంథాలయానికి అధిపతిగా ఉండేవాడు. క్రీస్తు శకం ఆరంభం కాని ముందు రోజుల్లో, ప్రపంచంలో, వేళ్లమీద లెక్కించదగ్గ మహా మేధావులలో ఈయనని ఒకరుగా లెక్కించడం పరిపాటిగా ఉండేది. ఆ రోజులలోనే భూమి గుండ్రంగా ఉందని లెక్క వేసి చెప్పటమే కాకుండా, భూమి యొక్క వ్యాసార్ధం ఎంత ఉంటుందో అంచనా వేసి చెప్పేడీయన. ఈ మేధావి ప్రధాన సంఖ్యల మీద కూడా పరిశోధనలు చేసి “ఇరటోస్తనీస్ జల్లెడ” అనే ఊహాత్మకమైన పరికరాన్ని ఒకదానిని మనకి వదిలిపెట్టి మరీ వెళ్లిపోయాడు. ఈ జల్లెడలో సంఖ్యలన్నిటిని వేసి “జల్లిస్తే” ప్రధాన సంఖ్యలన్నీ జల్లెడలో ఉండిపోతాయి, మిగిలినవి అన్నీ కిందకి దిగిపోతాయి.

ఈ ఇరటోస్తనీస్ జల్లెడ ఎలా పనిచేస్తుందో ఇప్పుడు చూద్దాం. ముందు సహజ సంఖ్యలన్నిటినీ, ఈ దిగువ చూపిన విధంగా (1 ని మినహాయించి) బారులు తీర్చి రాసుకోవాలి.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, …….
41,.....

నిర్వచనం ప్రకారం 2 ఎల్లప్పుడూ ప్రధాన సంఖ్యే. దీని చుట్టూ ఒక సున్న చుడదాం. ఇప్పుడు 2 తరువాత నిర్విరామంగా వచ్చే ప్రతి రెండవ సంఖ్యనీ (అంటే, 4, 6, 8, 10….వగైరాలు) కొట్టివెయ్యండి. (చెరిపెయ్య వద్దు; ఒక గీటు గీసి కొట్టివెయ్యండి.) ఇప్పుడు పైన చూపిన వరుసలో కొట్టివెయ్యకుండా మిగిలిన సంఖ్యలు ఈ దిగువ చూపిన విధంగా ఉంటాయి.

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ….

ఇప్పుడు ఈ కొత్త వరసలో 2 తరువాత కొట్టివేయబడకుండా వచ్చే మొదటి సంఖ్య, అనగా 3, చుట్టూ ఒక సున్న చుడదాం. ఈ దశలో ఇది లంగరు. ఇప్పుడు 3 తరువాత నిర్విరామంగా వచ్చే ప్రతీ మూడవ సంఖ్యనీ (అంటే, 6, 9, 12,15, …. వగైరాలని) కొట్టివెయ్యండి. గతంలో ఒక సారి కొట్టేసిన సంఖ్యలని మళ్లా కొట్టేయవలసి వచ్చినా మరేమీ పరవా లేదు. ఇప్పుడు పైన చూపిన వరుసలో మిగిలిన సంఖ్యలు ఈ దిగువ చూపిన విధంగా ఉంటాయి.

2, 3, 5, 7, 11, 13, 17, 19, 23, 25,

ఇప్పుడు 5 లంగరుగా 5 చేత నిశ్శేషంగా భాగించబడే సంఖ్యలని కొట్టేయండి. ఇలా కొట్టేసుకుంటూ పోతే, కొంతసేపు పోయిన తరువాత జల్లెడలో ప్రధాన సంఖ్యలు మిగులుతాయి. టూకీగా ఇరటోస్తనీస్ చెప్పిన ఉపాయం ఇది. పైన చూపిన వరుసలో చివరనున్న 25 ప్రధాన సంఖ్య కాదు. కాని 5 ని లంగరుగా చేసి మరొక సారి జల్లిస్తే 25 కిందకి దిగజారిపోతుంది. ఈ జల్లెడ రూపు రేఖలు బొమ్మలో చూపిన విధంగా ఉంటాయి.

## లక్షణాలు

క్రీ. పూ 300 సంవత్సరంలో యూక్లిడ్ (Euclid) రేఖాగణిత సూత్రావళి (Elements of Geometry లేదా క్లుప్తంగా Elements) అనే పేరుతో జగద్విఖ్యాతమైన పుస్తకం ప్రచురించేనాటికే ప్రధాన సంఖ్యలకు చెందిన సిద్ధాంతాలెన్నో ప్రమాణాత్మకంగా ప్రాచుర్యం పొంది ఉన్నాయి. ఉదాహరణకి ప్రధాన సంఖ్యలు అనంతంగా ఉన్నాయని యూక్లిడ్ తన సూత్రావళి తొమ్మిదవ అధ్యాయంలో రుజువు చేసి చూపించేడు. అంటే ప్రధాన సంఖ్యల జాబితాని తయారు చేద్దామని సంసిద్ధమైతే అది తెమిలే పని కాదు; హనుమంతుడి తోకలా ఆ జాబితా పెరుగుతూనే ఉంటుంది.

యూక్లిడ్ తన పుస్తకంలో మరొక విషయం ఋజువు చేసేడు. ఏ సంఖ్యనైనా సరే కొన్ని ప్రధాన సంఖ్యల లబ్ధంగా, ఒక ఏకైక (unique) పద్ధతిలో - వరుస క్రమంలో మార్పులని మినహాయించి - రాయవచ్చని ఆయన రుజువు చేసేడు. దీనినే అంకగణిత ప్రాథమిక సిద్ధాంతం (The Fundamental Theorem of Arithmetic) అంటారు. ఉదాహరణకి:

2 = 2 x 1
8 = 2 x 2 x 2
21 = 3 x 7

ఏదో ముత్యం మూడు ఉదాహరణలు చూపించేసి అదే సిద్ధాంతం అంటే శాస్త్రం ఒప్పుకోదు. ఉదాహరణకి 1001 ని పైన చూపిన విధంగా రాయడానికి ప్రయత్నించి చూద్దాం:

1001 = 7 x 143 = 11 x 91

ఇక్కడ ఆదిలోనే రెండు హంసపాదులు వచ్చేయి. మొదటి అభ్యంతరం ఏమిటంటే 1001 ని ఏకైకంగా కాకుండా రెండు విధాలుగా రాయడం జరిగింది. రెండో అభ్యంతరం ఏమిటంటే 143 న్నూ 91 న్నూ ప్రధాన సంఖ్యలలా అనిపించినా, నిజానికి అవి ప్రధాన సంఖ్యలు కావు; ఎందుకంటే,

143 = 11 x 13
91 = 7 x 13

వీటిని ఉపయోగించి 1001 కి కారణాంకాలని తిరగ రాస్తే:

1001 = 7 x 11 x 13 = 11 x 7 x 13

కనుక 1001 ని మూడు ఏకైక ప్రధాన సంఖ్యల లబ్ధాలుగా రాయగలిగేం. కనుక మన “ఏకైక’ సిద్ధాంతానికి భంగం రాలేదు. ఈ చిన్న ఉదాహరణ చెప్పే నీతి ఏమిటంటే ప్రధాన సంఖ్యలతో చెంగనాలు వేస్తూన్నప్పుడూ, చెలగాటాలు చేస్తూన్నప్పుడు కొంచెం ఒంటి మీద తెలివితో ప్రవర్తించకపోతే తప్పులు ఒప్పులు లాగా, ఒప్పులు తప్పులు లాగా కనిపించి, పప్పులో కాలేసే ప్రమాదం ఉంటుంది.

ప్రధాన సంఖ్యల ఎడల అప్రమత్తత ఎంత ముఖ్యమో నొక్కి వక్కాణించడానికి మరొక ఉదాహరణ:

ముందుగా, నిర్వచనం ప్రకారం, 2 ప్రధాన సంఖ్య కదా, ఇప్పుడు ఈ దిగువ శ్రేణిని పరిశీలిద్దాం:
 
 1 x 1 + 1 = 2, ప్రధాన సంఖ్య 
 2 x 1 + 1 = 3, ప్రధాన సంఖ్య
 2 x 3 + 1 = 7, ప్రధాన సంఖ్య
 2 x 3 x 5 + 1 = 31, ప్రధాన సంఖ్య
 2 x 3 x 5 x 7 + 1 = 211, ప్రధాన సంఖ్య
 2 x 3 x 5 x 7 x 11 + 1 = 2,311, ప్రధాన సంఖ్య

ఈ ఆరు సందర్భాలలోను గమనించదగ్గ విషయం ఒకటి ఉంది. 1 తరువాత వరుసగా వచ్చే ప్రధాన సంఖ్యలని క్రమానుగతంగా రెండేసి, మూడేసి, నాలుగేసి, … చొప్పున తీసుకుని గుణించగా వచ్చిన లబ్ధాలకు 1 కలుపగా వచ్చిన సంఖ్య మరొక ప్రధాన సంఖ్యగా భాసిల్లింది. ఒక సారి కాదు, రెండు సార్లు కాదు, మూడు సార్లు కాదు, వరుసగా ఆరు సార్లు ఈ నియమానికి ఉల్లంఘన రాలేదు. కనుక ఈ నియమం సర్వకాల సర్వావస్థలలోనూ పనిచేస్తుందనే నమ్మకం కలగక మానదు. ఆ సదుద్దేశంతో మరొక్క మెట్టు ఎక్కి ఈ దిగువ చూపిన సమీకరణం వ్రాసి చూద్దాం.

 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031, ప్రధాన సంఖ్యా!?

అని ఆలోచిస్తే, కొంచెం ఎక్కాలు, గుణింతాల వల్లె వేసుకుని, “అరెరె, 30031 ప్రధాన సంఖ్య ఎలా అవుతుంది, దానికి 59 న్నీ, 509 న్నీ కారణాంకాలు కావా?” అని అడుగుతాం. మన నియమానికి పురిటి లోనే సంధి కొట్టింది!! తస్మాత్ జాగ్రత జాగ్రతః!

## మరి కొన్ని విషయాలు
* కవల ప్రధాన సంఖ్యలు
* ప్రధాన కారణాంకాలు
* ప్రధాన సంఖ్యలలో జంటలు

## వాడుక
సూడో-ప్రధాన సంఖ్యలను/పరస్పర-ప్రధాన సంఖ్యలను RSA ఎన్క్రిప్షన్ (RSA అల్గారిథం) లో వాడుతారు. RSA ఎన్క్రిప్షన్ ను అఛేద్యమైన ఎన్క్రిప్షన్ గా భావిస్తారు.

వర్గం:గణిత శాస్త్రము
వర్గం:ప్రధాన సంఖ్యలు