firmate kii chhoti pramey key pramaan

yeh lekh firmate key chhote pramey key vibhinn pramanon koo ack saath ekatra kartaa haye, joe kahata haye kii
pratyek abhaajya sankhya "pee" aur pratyek purnank "aeye" key liye (modular ankganit dekhein).
saralikaran.
neeche diye gaye firmate key chhote pramey key kuchh pramaan dou saralikaranon parr nirbhar karate hain.
pahala yeh haye kii humm maan sakate hain kii yeh seema mein haye. yeh modular ankganit key niyamon kaa ack saral parinam haye; humm buss itna kaha rahey hain kii humm pahale modulo koo cumm curr sakate hain. yeh cumm karane vaale sootra _ 2 modulo key saath susangat haye, jaisa kii koee bhee jaanch curr sakata haye.
doosari baat yeh haye kii yeh saabit karane key liye paryaapt haye kii
seema mein. vaastav mein, yadi pichhale kathan mein aisaa maanaa gayaa haye, tou donon pakshon koo pramey key mool roop seey gunaa karane seey,
doosari or, yadi yaa, pramey tuchchh roop seey dhaaran kartaa haye.
sanyukt pramaan.
haaron kii ginati karke pramaan.
yeh shayed sabse saral gyaat pramaan haye, jisake liye cumm seey cumm ganitiya prishthabhoomi kii aavashyakta hoti haye. yeh ack sanyojan pramaan kaa ack aakarshak udaaharan haye (ack pramaan jisamen dou alag-alag tarikon seey vastuon key sangrah kii ginati shamil haye).
yahaan diyaa gayaa pramaan golamb key pramaan kaa ack roopaantaran haye.
cheejon koo saral rakhane key liye, humm maan lein kii yeh ack sakaratmak purnank haye. vibhinn prateekon key saath varnamala kaa upayog karke prateekon key sabhi sambhaavit taaron parr vichaar karein. iss tarah key taaron kii kull sankhya haye, kyonki pratyek sthiti key liye sambhaavanaaen hain (utpaad kaa niyam dekhein).
udaaharan key liye, yadi aur, tou humm dou prateekon (kahein aur) key saath ack varnamala kaa upayog curr sakate hain, aur lambai 5 key taar hainh
humm neeche tark denge kii yadi humm soochi seey ack ekal prateek seey yukt string koo hataa dete hain (hamaare udaaharan mein, aur), tou shesh string koo samoohon mein vyavasthit kiya jaa sakata haye, pratyek samooh mein bilkul string hoti haye. yeh iss prakaar haye kii dwara vibhaajya haye.
haar.
aaie humm pratyek aisee string key baare mein sochein joe ack haar kaa pratinidhitva karati haye. yaani, humm string key dou siron koo ack saath jodate hain aur dou string koo ack hii haar key roop mein maanate hain yadi humm doosari string praapt karane key liye ack string koo ghuma sakate hain; iss mamle mein humm kahenge kii dou string "dost" hain. hamaare udaaharan mein, nimnalikhit string sabhi mitra hainh
poorna roop seey, nimnalikhit soochi kii pratyek pankti ack ekal haar seey mell khaati haye, aur poori soochi mein sabhi 32 taar shamil hain.
dhyaan dein kii uparokt soochi mein, ack seey adhik prateek vaale pratyek haar koo 5 alag-alag taaron dwara darshaaya gayaa haye, aur kewal ack string dwara darshaae gaye haar kii sankhya 2, i haye.ee. yeh vishisht prateekon kii sankhya haye. iss prakaar soochi bahut spasht roop seey dikhaati haye kii kyon vibhajit kiya jaa sakata haye.
ack diye gaye string mein kitane dost hain, yeh pataa lagaane key liye koee nimnalikhit niyam kaa upayog curr sakata haih
udaaharan key liye, maan leejiye kii humm string seey shuru karate hain, joe chhoti string kii kaee pratiyon seey banaa haye. yadi humm ise ack samay mein ack prateek mein ghumaate hain, tou humm nimnalikhit 3 taar praapt karate hainh
koee anya naheen hain, kyonki yeh bilkul 3 prateekon seey lamba haye aur ise aage doharaane vaale taaron mein naheen todaa jaa sakata haye.
pramaan koo puuraa karein.
uparokt niyam kaa upayog karke, humm nimnanusar, firmate key chhote pramey key pramaan koo kaafee aasaani seey puuraa curr sakate hain. hamaare shuruati taaron koo dou shreniyon mein vibhajit kiya jaa sakata haih
doosari shreni mein taar hotey hain, aur unhein taaron key samoohon mein vyavasthit kiya jaa sakata haye, pratyek haar key liye ack samooh. isaliye, jaisa kii vaadaa kiya gayaa haye, usase vibhaajya honah chaahiye.
gatishil pranaliyon kaa upayog karke pramaan.
yeh pramaan gatishil pranaliyon seey kuchh buniyaadi avadhaaranaon kaa upayog kartaa haye.
humm "t" n "(" x ") key ack parivaar parr vichaar karke shuru karate hain, jahan" n "≤2 ack purnank haye, antaral [0,1] koo sootra dwara swayam maanchitrit karate hue.
jahan {"y"} "y" key aanshik bhaag koo darshaata haye. udaaharan key liye, falan "t" 3 ("x") neeche darshaaya gayaa haih
ack sankhya "x" 0 koo ack falan "f" ("x") kaa ack "nishchit bindu" kahaa jaataa haye yadi "f" ("x" 0) = "x" 0; dusare shabdon mein, yadi "f" "x" 0 koo chhod detaa haye. kissy falan key nishchit binduon koo aasaani seey chitraatmak roop seey paaya jaa sakata haih way kewal una binduon key "x" nirdeshank hain jahan "f" ("x") kaa graph rekha "y" = "x" key graph koo kaatata haye. udaaharan key liye, falan "t" 3 ("x") key nishchit bindu 0,1/2 aur 1 hain; way nimnalikhit aarekh parr kaale vritton dwara chihnit hainh
hamein nimnalikhit dou lemma kii aavashyakta hogi.
lemma 1. kissy bhee "n" ≤2 key liye, falan "t" n "(" x ") mein thheek" n "nishchit bindu hotey hain.
pramaan. uparokt chitran mein 3 nishchit bindu hain, aur kissy bhee "n" ≤2 key liye ack hii prakaar kaa jyaamitiya tark lagu hotaa haye.
lemma 2. kissy bhee sakaratmak purnank "n" aur "m" key liye, aur kissy bhee 0 ≤ x ≤ 1,
dusare shabdon mein, "t" "mn" ("x") "t" "n" ("x") aur "t" "m" ("x") kii sanrachana haye.
pramaan. iss shabd kaa pramaan mushkil naheen haye, lekin hamein antim bindu "x" = 1 key saath thodaa savdhan rahane kii aavashyakta haye. iss bindu key liye shabd spasht roop seey sach haye, kyonki
tou humm maan lete hain kii 0 ≤ "x" <1. iss mamle mein,
tou "t" "m" ("t" "n" ("x")) dwara diyaa jaataa haye
isaliye, hamein vaastav mein joe dikhaane kii aavashyakta haye vaha yeh haye kii
aisaa karane key liye humm dekhate hain kii {"nx"} = "nx" − "k", jahan "k" "nx" kaa purnank bhaag haye; taba
kyonki "mk" ack purnank haye.
abb humm falan "t" a "p" ("x") kaa adhyayan karke, firmate key chhote pramey key pramaan koo thheek seey shuru karate hain. humm maan lenge kii "a" ≤2. lemma 1 seey, humm jaanate hain kii isake "a" p "nishchit bindu hain. lemma 2 seey humm jaanate hain kii
isaliye "t" a "(" x ") kaa koee bhee nishchit bindu swachaalit roop seey" t "a" p "(" x ") kaa ack nishchit bindu hotaa haye.
humm "tii" aeye "pee" ("aiks") key nishchit binduon mein ruchi rakhate hain joe "tii" aeye "(" aiks ") key" nishchit bindu "naheen hain. aaie humm aise binduon key sett koo "s" kahate hain. s" mein "a" "p" − "a" "bindu hain, kyonki lemma 1 dwara phir seey," t "a" ("x") mein thheek "a" nishchit bindu hain. nimnalikhit aarekh "a" = 3 aur "p" = 2 key liye sthiti koo darshaata haye. kaale vritt "s" key bindu hain, jinamen seey 32−3 = 6 hain.
saboot kaa mukhya vichaar abb sett "aiss" koo "tii" aeye "key tahat apani kakshaon mein vibhajit karna haye. iska matlab yeh haye kii humm "s" mein ack bindu "x" 0 chunate hain, aur ankon kaa anukram praapt karane key liye baar-baar "t" a "(x) lagu karate hain.
iss anukram koo "t" a "key tahat" x "0 kii kaksha kahaa jaataa haye. lemma 2 dwara, iss anukram koo iss roop mein phir seey likhaa jaa sakata haye
choonki humm yeh maan rahey hain kii "x" 0 "t" a "p" ("x") kaa ack nishchit bindu haye, "p" charanon key baad humm "t" a "p" ("x" 0) = "x" 0 koo hitt karate hain, aur usa bindu seey anukram khud koo dohrata haye.
haalaanki, anukram "khud koo usase pahale dohrana shuru naheen curr sakata haye. yadi aisaa hotaa haye, tou doharaane vaale khand kii lambai "pee" kaa bhaajak honah chaahiye, isaliye ise 1 honah chaahiye (kyonki "pee" abhaajya haye). lekin yeh hamari dhaarana kaa khandan kartaa haye kii "x" 0 "t" a "kaa ack nishchit bindu naheen haye.
dusare shabdon mein, kaksha mein bilkul "pee" vishisht bindu hotey hain. yeh "s" kii pratyek kaksha key liye dhaaran kartaa haye. isaliye, samooh "s", jisamen "a" "p" − "a" bindu hotey hain, koo kakshaon mein vibhajit kiya jaa sakata haye, jisamen pratyek mein "p" bindu hotey hain, isaliye "a" "p" − "a" "p" seey vibhaajya haye.
(yeh pramaan anivarya roop seey oopar diye gaye haar-ginati pramaan key samaan haye, buss ack alag lens key madhyam seey dekhaa jaataa haih koee bhee antaral [0,1] key baare mein soch sakata haye jaisa kii aadhar "a" mein ankon key anukramon dwara diyaa gayaa haye (0 aur 1 key beach hamara antar purnankon koo samaapt karane key beach parichit antar key anuroop haye.."aur". 9999..."). "t" "a" "n" "iss tarah key anukram koo" "n" "kaee ankon seey sthanantarit karane key liye haye. isake nishchit bindu aise anukram honge joe "aine" koo vibhajit karane kii avadhi key saath chakreeya hain. vishesh roop seey, "tii" aeye "pee" key nishchit binduon koo "pee" kii lambai key haar key roop mein socha jaa sakata haye, jisamen "tii" aeye "aine" key saath "aine" dhabbe dwara aise haar key ghoornan key anuroop haye.
iss pramaan koo 0 aur 1 key beach antar kiye binaa bhee prastut kiya jaa sakata haye, kewal aadhe khule antaral [0,1) kaa upayog karke; taba "t" n "mein kewal" n "−1 nishchit bindu honge, lekin" t "a" "p" − "t" a "abhee bhee" a "" p "−" a "key liye kaam karega, jaisa kii aavashyakta haye.)
bahuayami pramaan.
pramaan 1.
yeh pramaan, euler key kaaran, sabhi purnankon key liye pramey koo saabit karane key liye preran kaa upayog kartaa haye.
aadhar kadam, vaha, tuchchh haye. isake baad, hamein yeh dikhaana hoga kii yadi pramey isake liye sahee haye, tou yeh isake liye bhee sahee haye. iss prerak charan key liye, hamein nimnalikhit shabd kii aavashyakta haye.
lemma. kissy bhee purnank key liye aur kissy bhee abhaajya key liye.
lemma nae vyakti key sapane kaa ack mamla haye. baad mein saboot chhodate hue, humm preran key saath aage badhate hain.
pramaan. k" "p" "shna" k "(modd" p ") maan leejiye, aur (" "k" + 1) "p" parr vichaar keejiye.  hamaare paas joe lemma haye
preran parikalpana kaa upayog karate hue, hamaare paas haye kii "k" p "shna" k "(modd" p "); aur, tuchchh roop seey, 1" p "= 1. iss prakaar
joe "a" = "k" + 1 key liye pramey kaa kathan haye.
lemma koo saabit karane key liye, hamein dwipadi pramey kaa parichay denaa hoga, joe bataata haye kii kissy bhee sakaratmak purnank "aine" key liye,
jahan gunank dwipad gunank hain,
kaarak falan key sandarbh mein varnit, "aine! = 1 × 2 × 3 × <unk> × "n".
lemma kaa pramaan. humm dwipadi gunank parr vichaar karate hain jaba ghatank ack abhaajya "pee" haih
dwipad gunank sabhi purnank hain. ansh mein gunankhand kii paribhasha key anusaar ack kaarak "pee" hotaa haye. jaba 0 <"i" <"p", tou bhaajak mein seey kissy bhee shabd mein "p" kaa ack kaarak shamil naheen hotaa haye ("p" kii prathamikta parr bharosa karate hue), gunank koo ansh seey "p" kaa ack pramukh kaarak rakhane key liye chhod detaa haye, jiska arth haye kii
modulo "pee", yeh prime "pee" key liye dwipad pramey key daahine haath kii or yog key pahale aur antim shabdon koo chhodkar sabhi koo samaapt kartaa haye. Â
pee" kii prathamikta lemma key liye aavashyak haye; anyatha, hamaare paas udaaharan hain jaise
joe 4 seey vibhaajya naheen haye.
pramaan 2.
lemma kaa upayog karate hue, hamaare paas haih
bahu-akshiya vistaar kaa upayog karke pramaan.
pramaan, jisaki khoj pahali baar leibniz (jinhone ise prakaashit naheen kiya) dwara kii gaee thee aur baad mein euler dwara phir seey khoja gayaa thaa, bahu-naamiya pramey kaa ack bahut hii saral anuprayog haye, joe bataata haye
kahaan
aur yog koo gair-nakaratmak purnank soochkaankon key sabhi anukramon parr liya jaataa haye jaise kii sabhi kaa yog haye.
iss prakaar yadi humm 1s (ack) key yog key roop mein vyakt karate hain, tou humm praapt karate hain
spasht roop seey, yadi abhaajya haye, aur yadi kissy key liye barabar naheen haye, tou hamaare paas haye
aur aggar kuchh key liye barabar haye tou
kyonki kuchh aise tatva hain joe kuchh key liye, pramey kaa anusaran karate hain.
(yeh pramaan anivarya roop seey pahale diye gaye haar-ginati pramaan kaa ack motaa-daane vaalaa sanskaran haye; bahu-bahupad gunank ack string koo manmaane dhang seey anagram mein krambaddh karane key tarikon kii sankhya koo ginate hain, jabaki haar tark ack string koo chakreeya anagram mein ghumaane key tarikon kii sankhya koo ginata haye. iska matlab haye kii yahaan gair-tuchchh bahu-akshiya gunank iss tathya key parinamswarup vibhaajya hain kii lambai key pratyek gair-tuchchh haar koo kaee tarikon seey ack string mein unlap kiya jaa sakata haye.
yeh bahupad vistaar bhee, nishchit roop seey, joe anivarya roop seey oopar dwipad pramey-adharit pramaan key tahat haye)
bijli utpaad vistaar kaa upayog karke pramaan.
aupchaarik shakti utpaad vistaar key aadhar parr ack yogaatmak-sanyukt pramaan geedrius alcouscas dwara diyaa gayaa thaa. yeh pramaan naa tou euclidean algorithm kaa upayog kartaa haye aur naa hii dwipad pramey kaa, balki yeh tarksangat gunank key saath aupchaarik shakti shrinkhala kaa upayog kartaa haye.
euler kii pramey key ack vishesh mamle key roop mein pramaan.
james hathidant dwara khoje gaye aur dirichlet dwara phir seey khoje gaye iss pramaan key liye modular ankganit mein kuchh prishthabhoomi kii aavashyakta hoti haye.
maan leejiye kii yeh sakaratmak haye aur isase vibhaajya naheen haye.
vichaar yeh haye kii aggar humm sankhyaon kaa crum likhein
aur pratyek ack modulo koo cumm karein, parinami anukram ack punarvyavastha saabit hotaa haye
isaliye, yadi humm pratyek anukram mein sankhyaon koo ack saath gunaa karate hain, tou parinam samaan modulo honey chaahieh
sharton koo ack saath ikattha karke upaj
anta mein, humm iss sameekaran key donon pakshon seey sankhyaon koo "radd" curr sakate hain, praapt curr sakate hain
uparokt pramaan mein dou charan hain jinhen hamein uchit thaharaane kii aavashyakta haih
humm inn cheejon koo neeche saabit karenge; aaie pahale iss pramaan kaa ack udaaharan dekhein.
ack udaaharan.
yadi aur, tou prashn mein anukram haye
modulo 7 koo cumm karna detaa haye
joe sirf ack punarvyavastha haye
unhein ack saath gunaa karane seey milata haye
vaha haye,
1 × 2 × 3 × 4 × 5 × 6 upaj koo radd karna
joe mamle key liye firmate kii chhoti pramey haye aur.
radd karane kaa kaanoon.
aaie pahale humm samajhaate hain kii kuchh sthitiyon mein, "radd karna" vaidh kyon haye. sateek kathan iss prakaar haye. yadi, aur purnank hain, aur ack abhaajya sankhya seey vibhaajya naheen haye, aur yadi
taba humm praapt karane key liye "radd" curr sakate hain
iss radd karane key niyam kaa upayog, firmate key chhote pramey key uparokt pramaan mein, maanya thaa, kyonki sankhyaaen nishchit roop seey (vaastav mein way "chhote" hain) seey vibhaajya naheen hain.
humm euclid key lemma kaa upayog karke aasaani seey radd karane key kaanoon koo saabit curr sakate hain, joe aam taur parr kahata haye kii yadi ack abhaajya kissy utpaad koo vibhajit kartaa haye (jahaan aur purnank hain), tou usey vibhajit karna chaahiye yaa. vaastav mein, daavaa () kaa seedha saa arth haye kii vibhajit hotaa haye. choonki yeh ack abhaajya haye joe vibhajit naheen kartaa haye, isaliye euclid kaa lemma hamein bataata haye kii ise isake bajaay vibhajit karna chaahiye; arthaat, () dhaaran kartaa haye.
dhyaan dein kii jinn sharton key tahat radd karane kaa kaanoon haye, way kaafee sakht hain, aur yeh bataata haye kii kyon firmate kii chhoti pramey ack abhaajya kii maang karati haye. udaaharan key liye, lekin yeh sach naheen haye. haalaanki, radd karane key kaanoon kaa nimnalikhit saamaanyikaran iss prakaar haih yadi,, aur purnank hain, yadi aur apekshaakrit pradhaan hain, aur yadi
taba humm praapt karane key liye "radd" curr sakate hain
yeh euclid key lemma key saamaanyikaran seey aataa haye.
punarvyavastha sampatti.
anta mein, hamein yeh samajhaana hoga kii anukram kyon haye
jaba modulo "pee" cumm hoe jaataa haye, tou yeh anukram kaa punarvyavastha bunn jaataa haye.
shuru karane key liye, kissy bhee shart key saath naheen..., shoonya modulo key liye sarvangsam hoe sakata haye, kyonki yadi sankhya mein seey ack haye, tou isake saath apekshaakrit abhaajya haye, aur isaliye euclid kaa lemma hamein bataata haye kii isake saath koee kaarak saajha naheen kartaa haye. isaliye, cumm seey cumm humm jaanate hain kii sankhyaaen,..., jaba cumm modulo, sankhyaon key beach paaya jaanaa chaahiye.
isake alawa, sankhyaaen,..., sabhi koo unhein cumm karane key baad "alag" honah chaahiye, kyonki yadi
kahaan aur kahaan seey ack hain, tou radd karane kaa kaanoon hamein bataata haye kii
choonki donon aur donon key beach hain, isaliye way samaan honey chaahiye. isaliye, shartein,...jaba cumm kiya gayaa modulo alag honah chaahiye. 
sankshep mein kahenh jaba humm sankhya koo cumm karate hain,..., modulo, humm anukram key alag-alag sadasyon koo praapt karate hain,...,. choonki inmein seey kuchh hii hain, isaliye ekmatra sambhavana yeh haye kii poorvavarti uttaraardh kaa punarvyavastha haye.
euler kii pramey key liye anuprayog.
iss vidhi kaa upayog euler kii pramey koo saabit karane key liye bhee kiya jaa sakata haye, jisamen thodaa badalaav kiya jaa sakata haye kii seey seey sankhya koo kuchh sankhya seey cumm sankhya dwara pratisthaapit kiya jaataa haye aur kuchh sankhya key saath saha-crum (aavashyak roop seey abhaajya naheen). punarvyavastha sampatti aur radd karane kaa kaanoon (oopar ullikhit saamaanyikrit roop key tahat) donon abhee bhee santusht hain aur unakaa upayog kiya jaa sakata haye.
udaaharan key liye, yadi, tou cumm sankhyaaen aur saha-samay sankhyaaen hain,, aur. iss prakaar hamaare paas haih
isaliye,
samooh siddhant kaa upayog karke pramaan.
maanak pramaan.
iss pramaan key liye samooh siddhant key sabse buniyaadi tatvon kii aavashyakta hoti haye.
vichaar yeh pahachaanana haye kii gunan key sanchaalan (modulo liya gayaa) key saath samooh ack samooh banaata haye. ekmatra samooh swayamsiddh jise satyaapit karane key liye kuchh prayaas kii aavashyakta hoti haye, vaha haye kii pratyek tatva vyutkramaniya haye. ise iss kshan key liye vishvaas parr lete hue, aaie humm maan lein kii yeh seema mein haye, yaani, iska ack tatva haye. maan leejiye kii yeh sabse chhota dhanaatmak purnank haye. phir ghataai gaee sankhyaaen ack upsamooh kaa nirmaan karati hain jiska crum lagrange kii pramey dwara haye aur isaliye, joe haye, key crum koo vibhajit karati hain. tou kuchh sakaratmak purnank key liye aur phir
yeh saabit karane key liye kii pratyek tatva vyutkramaniya haye, humm nimnanusar aage badh sakate hain. sabse pahale, yeh saha-moolya haye. iss prakaar bezout kii pehchaan hamein aashvast karati haye kii purnank aur aise bhee hain. iss samaantaa modulo koo padhkar, humm dekhate hain kii yeh isake liye ack vyutkram haye. isaliye, pratyek tatva vyutkramaniya haye. isaliye, jaisa kii pahale kahaa gayaa haye, ack samooh haye.
udaaharan key liye, jaba pratyek tatva key vyutkram nimnanusar diye jaate hainh
euler kaa pramaan.
yadi humm pichhale pramaan koo lete hain aur lagrange pramey kaa upayog karane key bajaay, humm ise iss vishisht sthiti mein saabit karane kii koshish karate hain, tou hamein euler kaa teesara pramaan milata haye, joe kii vaha haye joe usey adhik praakritik lagaa. maan leejiye kii vaha samooh jisake tatva sankhya mein ghataav vaale modulo hain. yadi, taba aur isaliye vibhajit hotaa haye. anyatha, kuchh haye.
maan leejiye kii vaha samooh jisake tatva sankhya mein ghataav vaale modulo hain. taba alag-alag tatva hotey hain, kyonki anyatha dou alag-alag sankhyaaen hoteen joe asambhav haye, kyonki yeh uska anusaran kartaa haye. doosari or, koee bhee tatva kaa ack tatva naheen hoe sakata haye, kyonki anyatha aisee sankhyaaen hongi joe, aur phir, joe asambhav haye, kyonki.
tou, sett mein tatva hain. yadi yeh "jee" key barabar hoe jaataa haye, tou aur isaliye vibhajit hoe jaataa haye. anyatha, kuchh hain aur humm phir seey shuru curr sakate hain, usa sett key roop mein paribhaashit karate hain jisake tatva sankhya cumm kiye gaye modulo hain. choonki yeh seemit haye, isaliye iss prakriya koo kissy bindu parr rukna chaahiye aur yeh saabit kartaa haye kii yeh vibhajit hoti haye.
udaaharan key liye, yadi aur taba seey
hamaare paas aur} haye. spasht roop seey,}. udaaharan key liye, ack tatva lein. taba seey
hamaare paas haye. spasht roop seey. udaaharan key liye, ack tatva lein. taba seey
hamaare paas haye. aur abb.
dhyaan dein kii sett, aur isi tarah vaastav mein inn key cosset hain.

