Polynomial greatest common divisor
બીજગણિતમાં, બે બહુપદીઓનો સૌથી મોટો સામાન્ય ભાજક (વારંવાર GCD તરીકે સંક્ષિપ્ત કરવામાં આવે છે) એ બહુપદી છે, જે સૌથી વધુ શક્ય ડિગ્રી ધરાવે છે, જે બંને મૂળ બહુપદીઓનું પરિબળ છે. આ ખ્યાલ બે પૂર્ણાંકોના સૌથી મોટા સામાન્ય ભાજક સમાન છે. ક્ષેત્ર પર અવિભાજ્ય બહુપદીઓના મહત્વપૂર્ણ કિસ્સામાં બહુપદી GCD ની ગણતરી કરી શકાય છે, જેમ કે પૂર્ણાંક GCD માટે, લાંબા વિભાજનનો ઉપયોગ કરીને યુક્લિડિયન અલ્ગોરિધમ દ્વારા. બહુપદી GCD ને માત્ર ઇન્વર્ટિબલ અચળાંક દ્વારા ગુણાકાર સુધી વ્યાખ્યાયિત કરવામાં આવે છે. પૂર્ણાંક જી. સી. ડી. અને બહુપદી જી. સી. ડી. વચ્ચેની સમાનતા યુક્લિડિયન અલ્ગોરિધમ અને યુક્લિડિયન વિભાગમાંથી અનુમાન કરી શકાય તેવા તમામ ગુણધર્મોને એકરૂપ બહુપદીઓ સુધી વિસ્તૃત કરવાની મંજૂરી આપે છે. વધુમાં, બહુપદી GCDમાં ચોક્કસ ગુણધર્મો છે જે તેને બીજગણિતના વિવિધ ક્ષેત્રોમાં મૂળભૂત કલ્પના બનાવે છે. સામાન્ય રીતે, બે બહુપદીઓના જી. સી. ડી. ના મૂળ એ બે બહુપદીઓના સામાન્ય મૂળ છે, અને આ તેમની ગણતરી કર્યા વિના મૂળ વિશે માહિતી પૂરી પાડે છે. ઉદાહરણ તરીકે, બહુપદીના બહુવિધ મૂળ બહુપદીના GCD અને તેના વ્યુત્પન્નના મૂળ છે, અને વધુ GCD ગણતરીઓ બહુપદીના વર્ગ-મુક્ત ગુણાકારની ગણતરી કરવાની મંજૂરી આપે છે, જે બહુપદી પૂરી પાડે છે, જેના મૂળ મૂળ બહુપદીના આપેલ ગુણાકારના મૂળ છે. સૌથી મોટો સામાન્ય વિભાજક વ્યાખ્યાયિત કરી શકાય છે અને અસ્તિત્વમાં છે, વધુ સામાન્ય રીતે, ક્ષેત્ર અથવા પૂર્ણાંકોની વીંટી પરની બહુપરીમાણીય બહુપદીઓ માટે, અને એક અનન્ય ગુણાકાર ક્ષેત્ર પર પણ. ગુણાંકની રિંગમાં GCD અલ્ગોરિધમ હોય તે જલદી તેમની ગણતરી કરવા માટે અલ્ગોરિધમ્સ અસ્તિત્વમાં છે. આ અલ્ગોરિધમ્સ યુક્લિડિયન અલ્ગોરિધમના એક પ્રકારમાં સમસ્યાને ઘટાડવા માટે ચલની સંખ્યા પર પુનરાવર્તન દ્વારા આગળ વધે છે. તેઓ કોમ્પ્યુટર બીજગણિતમાં એક મૂળભૂત સાધન છે, કારણ કે કોમ્પ્યુટર બીજગણિત પ્રણાલીઓ અપૂર્ણાંકોને સરળ બનાવવા માટે તેનો વ્યવસ્થિત રીતે ઉપયોગ કરે છે. તેનાથી વિપરીત, બહુપદી GCD નો મોટાભાગનો આધુનિક સિદ્ધાંત કોમ્પ્યુટર બીજગણિત પ્રણાલીઓની કાર્યક્ષમતાની જરૂરિયાતને સંતોષવા માટે વિકસાવવામાં આવ્યો છે. સામાન્ય વ્યાખ્યા ચાલો અને અભિન્ન ડોમેનમાં ગુણાંક સાથે બહુપદીઓ હોઈએ, સામાન્ય રીતે ક્ષેત્ર અથવા પૂર્ણાંકો. અને નો સૌથી મોટો સામાન્ય ભાજક એ બહુપદી છે જે અને ને વિભાજિત કરે છે, અને એવું કે દરેક સામાન્ય ભાજક અને તે પણ વિભાજિત કરે છે. બહુપદીઓની દરેક જોડી (બંને શૂન્ય નહીં) પાસે GCD હોય છે જો અને માત્ર ત્યારે જ જો તે એક અનન્ય ફેક્ટરાઇઝેશન ડોમેન હોય. જો ક્ષેત્ર હોય અને બંને શૂન્ય ન હોય, તો બહુપદી એ સૌથી મોટો સામાન્ય ભાજક છે જો અને માત્ર ત્યારે જ જો તે બંનેને વિભાજિત કરે અને આ ગુણધર્મ ધરાવતી બહુપદીઓમાં તેની ડિગ્રી સૌથી વધુ હોય. જો, GCD 0 છે. જો કે, કેટલાક લેખકો માને છે કે તે આ કિસ્સામાં વ્યાખ્યાયિત નથી. અને નો સૌથી મોટો સામાન્ય વિભાજક સામાન્ય રીતે "" તરીકે સૂચવવામાં આવે છે. સૌથી મોટો સામાન્ય ભાજક અનન્ય નથીઃ જો અને નો GCD હોય, તો બહુપદી અન્ય GCD છે જો અને માત્ર ત્યારે જ જો તેમાં અને નો ઇન્વર્ટિબલ એલિમેન્ટ હોય. બીજા શબ્દોમાં કહીએ તો, જી. સી. ડી. ઇન્વર્ટિબલ અચળાંક દ્વારા ગુણાકાર સુધી અનન્ય છે. પૂર્ણાંકોના કિસ્સામાં, આ અનિશ્ચિતતાને જી. સી. ડી. તરીકે પસંદ કરીને નક્કી કરવામાં આવી છે, જે અનન્ય છે જે હકારાત્મક છે (ત્યાં અન્ય એક છે, જે તેની વિરુદ્ધ છે). આ પરંપરા સાથે, બે પૂર્ણાંકોની GCD પણ સૌથી મોટી (સામાન્ય ક્રમ માટે) સામાન્ય વિભાજક છે. જો કે, ઇન્ટિગ્રલ ડોમેન પર બહુપદીઓ માટે કોઈ કુદરતી કુલ ક્રમ નથી, તેથી અહીં તે જ રીતે આગળ વધી શકાતું નથી. ક્ષેત્ર પરની અવિભાજ્ય બહુપદીઓ માટે, કોઈએ વધુમાં GCD ને મોનિક હોવાની જરૂર પડી શકે છે (એટલે કે તેના ઉચ્ચતમ ડિગ્રીના ગુણાંક તરીકે 1 હોવું જોઈએ), પરંતુ વધુ સામાન્ય કિસ્સાઓમાં કોઈ સામાન્ય પરંપરા નથી. તેથી, સમાનતાઓ જેમ કે અથવા સંકેતનાં સામાન્ય દુરુપયોગ છે જેને "is a GCD of and" and "અને" is a GCD of and and "તરીકે વાંચવું જોઈએ અને તેમાં GCD નો સમાન સમૂહ હોવો જોઈએ. ખાસ કરીને, તેનો અર્થ એ છે કે ઇન્વર્ટિબલ સ્થિરાંકો એકમાત્ર સામાન્ય વિભાજક છે. આ કિસ્સામાં, પૂર્ણાંક કેસ સાથે સામ્યતા દ્વારા, એક કહે છે કે અને છે. ગુણધર્મો ઉપર જણાવ્યા મુજબ, બે બહુપદીઓનું GCD અસ્તિત્વ ધરાવે છે જો ગુણાંક ક્યાં તો ક્ષેત્ર, પૂર્ણાંકોની વીંટી અથવા વધુ સામાન્ય રીતે એક અનન્ય ગુણાંક ડોમેન સાથે સંબંધિત હોય. જો અને નો કોઈ સામાન્ય વિભાજક હોય, તો પછી તેમના GCD ને વિભાજિત કરે છે. કોઈપણ બહુપદી માટે. આ ગુણધર્મ યુક્લિડિયન અલ્ગોરિધમનો પુરાવો છે. ગુણાંકની વીંટીના કોઈપણ ઉલટાવી શકાય તેવા તત્વ માટે,. તેથી કોઈપણ સ્કેલર માટે જેમ કે ઇન્વર્ટિબલ છે. જો એમ હોય તો. જો એમ હોય તો. બે અવિભાજ્ય બહુપદીઓ માટે અને એક ક્ષેત્ર પર, બહુપદીઓ અસ્તિત્વ ધરાવે છે અને, જેમ કે અને (બેઝઆઉટની ઓળખ) ના આવા દરેક રેખીય સંયોજનને વિભાજિત કરે છે. ત્રણ કે તેથી વધુ બહુપદીઓના સૌથી મોટા સામાન્ય ભાજકને બે બહુપદીઓની જેમ જ વ્યાખ્યાયિત કરી શકાય છે. તેને ઓળખ દ્વારા બે બહુપદીઓના GCD માંથી પુનરાવર્તિત રીતે ગણતરી કરી શકાય છેઃ અને હાથની ગણતરી દ્વારા GCD બે બહુપદીઓના સૌથી મોટા સામાન્ય ભાજકને શોધવાની ઘણી રીતો છે. તેમાંથી બે છેઃ બહુપદીઓનું ફેક્ટરાઇઝેશન, જેમાં દરેક અભિવ્યક્તિના પરિબળો શોધાય છે, પછી પરિબળોના દરેક સમૂહમાંથી બધા દ્વારા રાખવામાં આવેલા સામાન્ય પરિબળોનો સમૂહ પસંદ કરે છે. આ પદ્ધતિ ફક્ત સરળ કિસ્સાઓમાં જ ઉપયોગી થઈ શકે છે, કારણ કે સામાન્ય રીતે સૌથી મોટા સામાન્ય વિભાજકની ગણતરી કરતાં ફેક્ટરીંગ વધુ મુશ્કેલ હોય છે. યુક્લિડિયન અલ્ગોરિધમ, જેનો ઉપયોગ બે સંખ્યાઓ માટે સમાન રીતે બે બહુપદીઓના GCD શોધવા માટે થઈ શકે છે. ફેક્ટરીંગ ફેક્ટરીંગનો ઉપયોગ કરીને બે બહુપદીઓનું GCD શોધવા માટે, ફક્ત બે બહુપદીઓને સંપૂર્ણપણે પરિબળ બનાવો. પછી, તમામ સામાન્ય પરિબળોનું ઉત્પાદન લો. આ તબક્કે, આપણી પાસે એક મોનિક બહુપદી હોવી જરૂરી નથી, તેથી આખરે તેને એક મોનિક બહુપદી બનાવવા માટે અચળાંક દ્વારા ગુણાકાર કરો. આ બે બહુપદીઓનું GCD હશે કારણ કે તેમાં તમામ સામાન્ય ભાજકોનો સમાવેશ થાય છે અને તે મોનિક છે. ઉદાહરણ એકઃ અને ની GCD શોધો. આમ, તેમની જીસીડી છે. યુક્લિડિયન અલ્ગોરિધમ ફેક્ટરિંગ બહુપદીઓ મુશ્કેલ હોઈ શકે છે, ખાસ કરીને જો બહુપદીઓ મોટી માત્રામાં હોય. યુક્લિડિયન અલ્ગોરિધમ એ એક પદ્ધતિ છે જે બહુપદીઓની કોઈપણ જોડી માટે કામ કરે છે. તે યુક્લિડિયન વિભાગનો વારંવાર ઉપયોગ કરે છે. બે સંખ્યાઓ પર આ અલ્ગોરિધમનો ઉપયોગ કરતી વખતે, દરેક તબક્કે સંખ્યાઓનું કદ ઘટે છે. બહુપદીઓ સાથે, દરેક તબક્કે બહુપદીઓની માત્રા ઘટે છે. જો જરૂરી હોય તો મોનિક બનાવવામાં આવેલ છેલ્લું બિન-શૂન્ય શેષ, બે બહુપદીઓનું GCD છે. વધુ સ્પષ્ટ રીતે, બે બહુપદીઓની જીસીડી શોધવા માટે અને, કોઈ ધારી શકે છે (અન્યથા, જીસીડી છે), અને યુક્લિડિયન વિભાગ બે બહુપદીઓ પ્રદાન કરે છે, ભાગાકાર અને, બાકીની એવી રીતે કે એ બહુપદી બંનેને વિભાજિત કરે છે અને જો અને માત્ર ત્યારે જ જો તે બંનેને વિભાજિત કરે અને. આમ સેટિંગ કરવાથી નવી બહુપદીઓ વગેરે મેળવવા માટે યુક્લિડિયન વિભાજનનું પુનરાવર્તન કરી શકાય છે. દરેક તબક્કે આપણી પાસે છે તેથી ક્રમ આખરે તે બિંદુ સુધી પહોંચશે કે જેના પર વ્યક્તિને GCD મળ્યું છેઃ ઉદાહરણ તરીકેઃ GCD શોધવી અનેઃ કારણ કે તે છેલ્લું બિન-શૂન્ય શેષ છે, તે મૂળ બહુપદીઓનું GCD છે, અને મોનીક GCD છે. આ ઉદાહરણમાં, બીજા પગલા પહેલા 12 ને ફેક્ટરીંગ કરીને છેદ રજૂ કરવાનું ટાળવું મુશ્કેલ નથી. આ હંમેશા સ્યુડો-રિમેઇન્ડર સિક્વન્સનો ઉપયોગ કરીને કરી શકાય છે, પરંતુ, કાળજી વિના, આ ગણતરી દરમિયાન ખૂબ મોટા પૂર્ણાંકો રજૂ કરી શકે છે. તેથી, કોમ્પ્યુટર ગણતરી માટે, અન્ય અલ્ગોરિધમ્સનો ઉપયોગ કરવામાં આવે છે, જે નીચે વર્ણવેલ છે. આ પદ્ધતિ ત્યારે જ કામ કરે છે જ્યારે ગણતરી દરમિયાન થતા ગુણાંકની શૂન્યની સમાનતાનું પરીક્ષણ કરી શકાય. તેથી, વ્યવહારમાં, ગુણાંક પૂર્ણાંકો, તર્કસંગત સંખ્યાઓ, મર્યાદિત ક્ષેત્રના ઘટકો હોવા જોઈએ, અથવા અગાઉના ક્ષેત્રોમાંથી કોઈ એકના મર્યાદિત રીતે ઉત્પન્ન થયેલ ક્ષેત્ર વિસ્તરણના હોવા જોઈએ. જો ગુણાંક ફ્લોટિંગ-પોઇન્ટ નંબરો હોય જે વાસ્તવિક સંખ્યાઓનું પ્રતિનિધિત્વ કરે છે જે માત્ર આશરે જ જાણીતા હોય, તો વ્યક્તિએ સારી રીતે વ્યાખ્યાયિત ગણતરી પરિણામ મેળવવા માટે GCD ની ડિગ્રી જાણવી આવશ્યક છે (તે આંકડાકીય રીતે સ્થિર પરિણામ છે; આ કિસ્સાઓમાં અન્ય તકનીકોનો ઉપયોગ કરી શકાય છે, જે સામાન્ય રીતે એકવચન મૂલ્ય વિઘટન પર આધારિત હોય છે. ક્ષેત્રમાં ગુણાંક સાથે અવિભાજ્ય બહુપદીઓ ક્ષેત્ર પર અવિભાજ્ય બહુપદીઓનો કેસ ઘણા કારણોસર ખાસ કરીને મહત્વપૂર્ણ છે. પ્રથમ, તે સૌથી પ્રાથમિક કેસ છે અને તેથી બીજગણિતના મોટાભાગના પ્રથમ અભ્યાસક્રમોમાં દેખાય છે. બીજું, તે પૂર્ણાંકોના કેસ સાથે ખૂબ સમાન છે, અને આ સામ્યતા યુક્લિડિયન ડોમેનની કલ્પનાનો સ્રોત છે. ત્રીજું કારણ એ છે કે મલ્ટિવેરિયેટ કેસ માટે અને અનન્ય ફેક્ટરાઇઝેશન ડોમેનમાં ગુણાંક માટે સિદ્ધાંત અને અલ્ગોરિધમ્સ આ ચોક્કસ કેસ પર મજબૂત રીતે આધારિત છે. છેલ્લું પરંતુ ઓછામાં ઓછું નહીં, બહુપદી GCD અલ્ગોરિધમ્સ અને વ્યુત્પન્ન અલ્ગોરિધમ્સ બહુપદીના મૂળ પર ઉપયોગી માહિતી મેળવવાની મંજૂરી આપે છે, તેમની ગણતરી કર્યા વિના. બહુપદીઓનું યુક્લિડિયન વિભાજન, જેનો ઉપયોગ જી. સી. ડી. ની ગણતરી માટે યુક્લિડના અલ્ગોરિધમમાં થાય છે, તે પૂર્ણાંકોના યુક્લિડિયન વિભાજન જેવું જ છે. તેનું અસ્તિત્વ નીચેના પ્રમેય પર આધારિત છેઃ એક ક્ષેત્ર પર વ્યાખ્યાયિત બે એકરૂપ બહુપદીઓ a અને b ષ્ણાંક 0 આપવામાં આવે તો, ત્યાં બે બહુપદીઓ q (ભાગાકાર) અને r (શેષ) અસ્તિત્વમાં છે જે સંતોષ આપે છે અને જ્યાં "ડિગ્રી (.)" ડિગ્રી સૂચવે છે અને શૂન્ય બહુપદીની ડિગ્રીને નકારાત્મક તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. વધુમાં, q અને r ને આ સંબંધો દ્વારા અનન્ય રીતે વ્યાખ્યાયિત કરવામાં આવે છે. પૂર્ણાંકોના યુક્લિડિયન વિભાજનથી તફાવત એ છે કે, પૂર્ણાંકો માટે, ડિગ્રીને નિરપેક્ષ મૂલ્ય દ્વારા બદલવામાં આવે છે, અને વિશિષ્ટતા મેળવવા માટે વ્યક્તિએ ધારવું પડશે કે r બિન-નકારાત્મક છે. જે રિંગ્સ માટે આવા પ્રમેય અસ્તિત્વમાં છે તેને યુક્લિડિયન ડોમેન્સ કહેવામાં આવે છે. પૂર્ણાંકોની જેમ, બહુપદીઓના યુક્લિડિયન વિભાજનની ગણતરી લાંબા વિભાજન અલ્ગોરિધમ દ્વારા કરી શકાય છે. આ અલ્ગોરિધમ સામાન્ય રીતે કાગળ અને પેન્સિલની ગણતરી માટે રજૂ કરવામાં આવે છે, પરંતુ જ્યારે તેને ઔપચારિક સ્વરૂપ આપવામાં આવે ત્યારે તે કોમ્પ્યુટર પર સારી રીતે કામ કરે છે (નોંધ કરો કે ચલોનાં નામ લાંબા વિભાજનની પેન્સિલ અને કાગળની ગણતરીમાં કાગળની શીટના પ્રદેશોને બરાબર અનુરૂપ હોય છે). નીચેની ગણતરીમાં "ડીગ" એ તેની દલીલની ડિગ્રી (પરંપરા સાથે) માટે વપરાય છે, અને "એલસી" એ અગ્રણી ગુણાંક માટે વપરાય છે, જે ચલની ઉચ્ચતમ ડિગ્રીનો ગુણાંક છે. આ અલ્ગોરિધમની માન્યતાનો પુરાવો એ હકીકત પર આધાર રાખે છે કે સમગ્ર "વાઇલ" લૂપ દરમિયાન, આપણી પાસે એક બિન-નકારાત્મક પૂર્ણાંક છે જે દરેક પુનરાવર્તન પર ઘટે છે. આમ આ અલ્ગોરિધમની માન્યતાનો પુરાવો પણ યુક્લિડિયન વિભાજનની માન્યતાને સાબિત કરે છે. યુક્લિડનું અલ્ગોરિધમ પૂર્ણાંકો માટે, યુક્લિડિયન વિભાગ આપણને જીસીડીની ગણતરી માટે યુક્લિડના અલ્ગોરિધમને વ્યાખ્યાયિત કરવાની મંજૂરી આપે છે. બે બહુપદી a અને b થી શરૂ કરીને, યુક્લિડના અલ્ગોરિધમમાં b = 0 સુધી પુનરાવર્તિત રીતે જોડીને બદલવાનો સમાવેશ થાય છે (જ્યાં "" અગાઉના વિભાગના અલ્ગોરિધમ દ્વારા ગણતરી કરાયેલ યુક્લિડિયન વિભાગના બાકીના ભાગને સૂચવે છે). જીસીડી એ છેલ્લું બિન-શૂન્ય શેષ છે. યુક્લિડના અલ્ગોરિધમને પુનરાવર્તિત પ્રોગ્રામિંગ શૈલીમાં ઔપચારિક બનાવી શકાય છેઃ અનિવાર્ય પ્રોગ્રામિંગ શૈલીમાં, તે જ અલ્ગોરિધમ બને છે, જે દરેક મધ્યવર્તી શેષને નામ આપે છેઃ ડિગ્રીનો ક્રમ સખત રીતે ઘટી રહ્યો છે. આમ, વધુમાં વધુ, પગલાંઓ પછી, એક શૂન્ય શેષ મળે છે, કહો. જેમ અને સમાન વિભાજકો હોય તેમ, સામાન્ય વિભાજકોનો સમૂહ યુક્લિડના અલ્ગોરિધમ દ્વારા બદલાતો નથી અને આમ તમામ જોડીઓમાં સામાન્ય વિભાજકોનો સમાન સમૂહ હોય છે. અને ના સામાન્ય વિભાજક આમ અને 0 ના સામાન્ય વિભાજક છે. આમ અને ની GCD છે. આ માત્ર એ જ સાબિત કરતું નથી કે યુક્લિડનું અલ્ગોરિધમ જીસીડીની ગણતરી કરે છે પણ તે પણ સાબિત કરે છે કે જીસીડી અસ્તિત્વમાં છે. બેઝઆઉટની ઓળખ અને વિસ્તૃત જીસીડી અલ્ગોરિધમ બેઝઆઉટની ઓળખ એ જીસીડી સંબંધિત પ્રમેય છે, જે શરૂઆતમાં પૂર્ણાંકો માટે સાબિત થાય છે, જે દરેક મુખ્ય આદર્શ ડોમેન માટે માન્ય છે. ક્ષેત્ર પરની અવિભાજ્ય બહુપદીઓના કિસ્સામાં, તે નીચે મુજબ વર્ણવી શકાય છે. બહુપદીઓના કિસ્સામાં આ પરિણામનો રસ એ છે કે બહુપદીઓની ગણતરી કરવા માટે એક કાર્યક્ષમ અલ્ગોરિધમ છે અને, આ અલ્ગોરિધમ લૂપના દરેક પુનરાવર્તન પર કરવામાં આવેલી કેટલીક વધુ ગણતરીઓ દ્વારા યુક્લિડના અલ્ગોરિધમથી અલગ પડે છે. તેથી તેને વિસ્તૃત જીસીડી અલ્ગોરિધમ કહેવામાં આવે છે. યુક્લિડના અલ્ગોરિધમ સાથેનો બીજો તફાવત એ છે કે તે માત્ર બાકીનાને બદલે યુક્લિડિયન વિભાગના ભાગાકારનો પણ ઉપયોગ કરે છે, જેને "ક્વો" તરીકે સૂચવવામાં આવે છે. આ અલ્ગોરિધમ નીચે પ્રમાણે કામ કરે છે. અલ્ગોરિધમ તેના આઉટપુટ સ્પષ્ટીકરણને સંતોષે છે તેનો પુરાવો એ હકીકત પર આધાર રાખે છે કે, દરેક માટે આપણી પાસે પછીની સમાનતા સૂચવે છે. આ અલ્ગોરિધમનો એક રસપ્રદ લક્ષણ એ છે કે, જ્યારે બેઝઆઉટની ઓળખના ગુણાંકની જરૂર પડે છે, ત્યારે વ્યક્તિને તેમના GCD દ્વારા ઇનપુટ બહુપદીઓનો ભાગ મફતમાં મળે છે. બીજગણિત વિસ્તરણોનું અંકગણિત વિસ્તૃત GCD અલ્ગોરિધમનો એક મહત્વપૂર્ણ ઉપયોગ એ છે કે તે બીજગણિત ક્ષેત્ર વિસ્તરણમાં વિભાજનની ગણતરી કરવાની મંજૂરી આપે છે. એક ક્ષેત્રનું બીજગણિત વિસ્તરણ, જે એક તત્વ દ્વારા ઉત્પન્ન થાય છે, જેની ન્યૂનતમ બહુપદી ડિગ્રી ધરાવે છે. ના ઘટકો સામાન્ય રીતે તેના કરતા ઓછી ડિગ્રીની અવિભાજ્ય બહુપદીઓ દ્વારા રજૂ થાય છે. તેમાં ઉમેરો એ ફક્ત બહુપદીઓનો ઉમેરો છેઃ તેમાં ગુણાકાર એ બહુપદીઓનો ગુણાકાર છે જે પછી વિભાજન છેઃ બિન-શૂન્ય તત્વનો વ્યસ્ત ભાગ એ બેઝઆઉટની ઓળખમાં ગુણાંક છે, જેની ગણતરી વિસ્તૃત GCD અલ્ગોરિધમ દ્વારા કરી શકાય છે. (GCD એ 1 છે કારણ કે ન્યૂનતમ બહુપદી ઈરીડ્યુસિબલ છે). વિસ્તૃત જીસીડી અલ્ગોરિધમનોના સ્પષ્ટીકરણમાં ડિગ્રી અસમાનતા દર્શાવે છે કે ડીગ () <ડીગ () મેળવવા માટે વધુ વિભાજનની જરૂર નથી. અવિભાજ્ય બહુપદીઓના કિસ્સામાં, સૌથી મોટા સામાન્ય વિભાજક અને પરિણામી વચ્ચે મજબૂત સંબંધ હોય છે. વધુ સ્પષ્ટ રીતે કહીએ તો, બે બહુપદીઓ P, Q નું પરિણામ એ P અને Q ના ગુણાંકનું બહુપદી કાર્ય છે જેનું મૂલ્ય શૂન્ય હોય છે જો અને માત્ર ત્યારે જ જો P અને Q નું GCD અચળ ન હોય. ઉપ-પરિણામ સિદ્ધાંત એ આ ગુણધર્મનું સામાન્યીકરણ છે જે બે બહુપદીઓના GCD ને સામાન્ય રીતે લાક્ષણિકતા આપવાની મંજૂરી આપે છે, અને પરિણામી એ 0-મી ઉપ-પરિણામ બહુપદી છે. બે બહુપદીઓ P અને Q ની i-th ઉપઉત્પાદક બહુપદી Si (P, Q) એ મહત્તમ i ડિગ્રીની બહુપદી છે, જેના ગુણાંક P અને Q ના ગુણાંકના બહુપદી કાર્યો છે, અને i-th મુખ્ય ઉપઉત્પાદક ગુણાંક si (P, Q) એ Si (P, Q) ની ડિગ્રી i નો ગુણાંક છે. તેમની પાસે એવી મિલકત છે કે P અને Q ની GCD ડિગ્રી d ધરાવે છે જો અને માત્ર જો. આ કિસ્સામાં, Sd (P, Q) એ P અને Q નો GCD છે અને પેટા પરિણામ બહુપદીઓના દરેક ગુણાંકને P અને Q ના સિલ્વેસ્ટર મેટ્રિક્સના પેટા મેટ્રિક્સના નિર્ધારક તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. આ સૂચવે છે કે ઉપ-પરિણામો સારી રીતે "વિશેષતા" ધરાવે છે. વધુ સ્પષ્ટ રીતે કહીએ તો, ઉપ-પરિણામોને કોઈપણ પરિવર્તનીય રીંગ R પર બહુપદીઓ માટે વ્યાખ્યાયિત કરવામાં આવે છે, અને તેમાં નીચેનો ગુણધર્મ હોય છે. ધારો કે φ એ R નું રિંગ હોમોમોર્ફિઝમ અન્ય પરિવર્તનીય રિંગ S માં છે. તે અન્ય હોમોમોર્ફિઝમ સુધી વિસ્તરે છે, જે R અને S પર બહુપદી રિંગ્સ વચ્ચે પણ સૂચવવામાં આવે છે. પછી, જો P અને Q એ R માં ગુણાંક ધરાવતી અવિભાજ્ય બહુપદીઓ હોય અને પછી ઉપ-પરિણામી બહુપદીઓ અને φ (P) અને φ (Q) ના મુખ્ય ઉપ-પરિણામી ગુણાંક એ P અને Q ની φ ની છબી છે. ઉપ-પરિણામોમાં બે મહત્વપૂર્ણ ગુણધર્મો હોય છે જે તેમને પૂર્ણાંક ગુણાંક સાથે બે બહુપદીઓના GCD ના કમ્પ્યુટર્સ પર ગણતરી માટે મૂળભૂત બનાવે છે. પ્રથમ, નિર્ધારકો દ્વારા તેમની વ્યાખ્યા હદામાર્ડ અસમાનતા દ્વારા, GCD ના ગુણાંકના કદને મર્યાદિત કરવાની મંજૂરી આપે છે. બીજું, આ બાઉન્ડ અને સારી વિશેષતાના ગુણધર્મો મોડ્યુલર ગણતરી અને ચાઇનીઝ રિમેન્ડર થીયરમ (નીચે જુઓ) દ્વારા પૂર્ણાંક ગુણાંક સાથે બે બહુપદીઓના GCD ની ગણતરી કરવાની મંજૂરી આપે છે. તકનીકી વ્યાખ્યા K ક્ષેત્રમાં ગુણાંક ધરાવતી બે અવિભાજ્ય બહુપદીઓ હોઈએ. ચાલો આપણે i કરતા ઓછી ડિગ્રીની બહુપદીઓના પરિમાણ i ની K વેક્ટર જગ્યા દ્વારા સૂચવીએ. બિન-નકારાત્મક પૂર્ણાંક i માટે, જેમ કે i ≤ m અને i ≤ n, ચાલો રેખીય નકશો એવી રીતે બનાવીએ કે P અને Q નો પરિણામી સિલ્વેસ્ટર મેટ્રિક્સનો નિર્ધારક હોય, જે X ની ઘાતોના પાયા પરનો (વર્ગ) મેટ્રિક્સ છે. તેવી જ રીતે, i-ઉપઉત્પાદક બહુપદીને મેટ્રિક્સના પેટા મેટ્રિક્સના નિર્ધારકોની દ્રષ્ટિએ વ્યાખ્યાયિત કરવામાં આવે છે ચાલો આપણે આ મેટ્રિક્સને વધુ ચોક્કસપણે વર્ણવીએ; ચાલો i <0 અથવા i> m માટે π = 0, અને i <0 અથવા i> n માટે qi = 0. સિલ્વેસ્ટર મેટ્રિક્સ એ (m + n) × (m + n)-મેટ્રિક્સ છે કે જે i-th પંક્તિ અને j-th સ્તંભનો ગુણાંક j ≤ n માટે p + j − i અને j> n માટે qj − i છેઃ મેટ્રિક્સ Ti એ (m + n − i) × (m + n − 2i)-મેટ્રિક્સ છે જે S દ્વારા મેળવવામાં આવે છે. મુખ્ય ઉપ-પરિણામ ગુણાંક સી એ એમ + એન − 2i ની ટીઆઈની પ્રથમ હરોળનો નિર્ધારક છે. ધારો કે Vi એ (m + n − 2i) × (m + n − i) મેટ્રિક્સ છે જે નીચે પ્રમાણે વ્યાખ્યાયિત થયેલ છે. પહેલા આપણે (m + n − 2i − 1) × (m + n − 2i − 1) ઓળખ મેટ્રિક્સની જમણી બાજુએ (i + 1) શૂન્ય સ્તંભો ઉમેરીએ છીએ. પછી આપણે પરિણામી મેટ્રિક્સના તળિયે (m + n − i − 1) શૂન્ય પછી xi, xi − 1,., x, 1 ધરાવતી પંક્તિ દ્વારા સરહદ બનાવીએ છીએઃ આ સંકેત સાથે, i-th ઉપ-પરિણામ બહુપદી એ મેટ્રિક્સ ઉત્પાદન viti નો નિર્ધારક છે. તેનો ડિગ્રી j નો ગુણાંક એ તેના m + n − 2i − 1 પ્રથમ હરોળ અને (m + n − i − j)-th હરોળમાં બનેલા Ti ના વર્ગ પેટા મેટ્રિક્સનો નિર્ધારક છે. સાબિતીનું સ્કેચ તે સ્પષ્ટ નથી કે, વ્યાખ્યાયિત કર્યા મુજબ, ઉપ-પરિણામો ઇચ્છિત ગુણધર્મો ધરાવે છે. તેમ છતાં, જો રેખીય બીજગણિત અને બહુપદીઓના ગુણધર્મોને એકસાથે મૂકવામાં આવે તો સાબિતી એકદમ સરળ છે. વ્યાખ્યાયિત કર્યા મુજબ, મેટ્રિક્સ Ti ના સ્તંભો તેની છબી સાથે જોડાયેલા કેટલાક બહુપદીઓના ગુણાંકના વાહક છે. જો GCD ની ડિગ્રી i કરતા વધારે હોય, તો બેઝઆઉટની ઓળખ દર્શાવે છે કે i ની છબીમાં દરેક બિન-શૂન્ય બહુપદી i કરતા મોટી ડિગ્રી ધરાવે છે. આ સૂચવે છે કે Si = 0. જો, બીજી બાજુ, GCD ની ડિગ્રી i હોય, તો બેઝઆઉટની ઓળખ ફરીથી એ સાબિત કરવાની મંજૂરી આપે છે કે GCD ના ગુણાંક કે જે m + n−i કરતા ઓછી ડિગ્રી ધરાવે છે તે ની છબીમાં છે. આ ગુણાંકની વેક્ટર જગ્યા m + n − 2i પરિમાણ ધરાવે છે અને જોડી મુજબ વિવિધ ડિગ્રીની બહુપદીઓનો આધાર ધરાવે છે, જે i કરતા નાની નથી. આ સૂચવે છે કે એમ + એન − 2i ની પેટા મેટ્રિક્સ ટીઆઈના સ્તંભ સ્તર સ્વરૂપની પ્રથમ પંક્તિઓ ઓળખ મેટ્રિક્સ છે અને આમ તે સી 0 નથી. આમ, ની છબીમાં Si એ બહુપદી છે, જે GCD નો ગુણાંક છે અને તેની ડિગ્રી સમાન છે. આમ તે સૌથી મોટો સામાન્ય વિભાજક છે. જીસીડી અને રુટ ફાઇન્ડિંગ સ્ક્વેર-ફ્રી ફેક્ટરાઇઝેશન મોટાભાગના રુટ-ફાઇન્ડિંગ એલ્ગોરિધમ્સ બહુવિધ મૂળ ધરાવતા બહુપદીઓ સાથે ખરાબ રીતે વર્તે છે. તેથી રુટ-ફાઇન્ડિંગ અલ્ગોરિધમનો કૉલ કરતા પહેલા તેમને શોધવા અને દૂર કરવા ઉપયોગી છે. જીસીડી ગણતરી બહુવિધ મૂળના અસ્તિત્વને શોધવાની મંજૂરી આપે છે, કારણ કે બહુપદીના બહુવિધ મૂળ બહુપદીના જીસીડી અને તેના વ્યુત્પન્નના મૂળ છે. બહુપદીના GCD અને તેના વ્યુત્પન્નની ગણતરી કર્યા પછી, વધુ GCD ગણતરીઓ બહુપદીનું સંપૂર્ણ વર્ગ-મુક્ત ગુણાકાર પ્રદાન કરે છે, જે એક ગુણાકાર છે, જ્યાં દરેક i માટે, બહુપદી ફાઈ ક્યાં તો 1 હોય છે જો f પાસે ગુણાકાર i નું કોઈ મૂળ ન હોય અથવા તે વર્ગ-મુક્ત બહુપદી છે (જે બહુવિધ મૂળ વિનાની બહુપદી છે) જેના મૂળ બરાબર f ના ગુણાકાર i ના મૂળ છે (યુનનું અલ્ગોરિધમ જુઓ). આમ સ્ક્વેર-ફ્રી ફેક્ટરાઇઝેશન બહુવિધ મૂળ ધરાવતી બહુપદીના રુટ-ફાઇન્ડિંગને ઓછી ડિગ્રીની કેટલીક સ્ક્વેર-ફ્રી બહુપદીઓના રુટ-ફાઇન્ડિંગમાં ઘટાડે છે. સ્ક્વેર-ફ્રી ફેક્ટરાઇઝેશન એ મોટાભાગના બહુપદી ફેક્ટરાઇઝેશન અલ્ગોરિધમ્સમાં પણ પ્રથમ પગલું છે. સ્ટર્મ ક્રમ વાસ્તવિક ગુણાંક સાથે બહુપદીનો સ્ટર્મ ક્રમ એ બહુપદી અને તેના વ્યુત્પન્ન પર લાગુ યુક્લિડના અલ્ગોરિધમનો એક પ્રકાર દ્વારા પૂરા પાડવામાં આવેલ અવશેષોનો ક્રમ છે. સ્ટર્મ ક્રમ મેળવવા માટે, યુક્લિડના અલ્ગોરિધમની સૂચનાને ફક્ત V (a) દ્વારા બદલી શકાય છે, જ્યારે એક બિંદુ a પર મૂલ્યાંકન કરવામાં આવે ત્યારે તે ક્રમમાં સંકેતોના ફેરફારોની સંખ્યા હોય છે. સ્ટર્મનો પ્રમેય ભારપૂર્વક જણાવે છે કે V (a) − V (b) એ અંતરાલ [a, b] માં બહુપદીના વાસ્તવિક મૂળની સંખ્યા છે. આમ સ્ટર્મ ક્રમ આપેલ અંતરાલમાં વાસ્તવિક મૂળની સંખ્યાની ગણતરી કરવાની મંજૂરી આપે છે. જ્યાં સુધી દરેક પેટા અંતરાલમાં મહત્તમ એક મૂળ ન હોય ત્યાં સુધી અંતરાલને પેટા વિભાજિત કરીને, આ એક અલ્ગોરિધમ પ્રદાન કરે છે જે મનસ્વી રીતે નાની લંબાઈના અંતરાલોમાં વાસ્તવિક મૂળને શોધી કાઢે છે. રિંગ અને તેના અપૂર્ણાંકોના ક્ષેત્ર પર GCD આ વિભાગમાં, આપણે એક અનન્ય ફેક્ટરાઇઝેશન ડોમેન R પર બહુપદીઓને ધ્યાનમાં લઈએ છીએ, સામાન્ય રીતે પૂર્ણાંકોની રિંગ, અને તેના અપૂર્ણાંકોના ક્ષેત્ર F પર, સામાન્ય રીતે તર્કસંગત સંખ્યાઓનું ક્ષેત્ર, અને આપણે આ રિંગ્સ પર ચલોના સમૂહમાં બહુપદીઓની રિંગ્સ R [X] અને F [X] ને સૂચવીએ છીએ. આદિમ ભાગ-સામગ્રી ગુણાકાર બહુપદી p ωR [X] ની સામગ્રી, જેને "cont (p)" તરીકે સૂચવવામાં આવે છે, તે તેના ગુણાંકની GCD છે. બહુપદી q ωF [X] લખી શકાય છે જ્યાં p ωR [X] અને c ωR: તે c માટે q (ઉદાહરણ તરીકે તેમના ગુણાકાર) અને p = cq ના ગુણાંકના તમામ છેદોનો ગુણાંક લેવા માટે પૂરતું છે. q ની સામગ્રીને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ બંને કિસ્સાઓમાં, સામગ્રીને R ના એકમ દ્વારા ગુણાકાર સુધી વ્યાખ્યાયિત કરવામાં આવે છે. R [X] અથવા F [X] માં બહુપદીના આદિમ ભાગને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. આમ R [X] અથવા F [X] માં દરેક બહુપદીને ફેક્ટરાઇઝ કરી શકાય છે અને આ ફેક્ટરાઇઝેશન R ના એકમ દ્વારા સામગ્રીના ગુણાકાર સુધી અને આ એકમના વ્યસ્ત ભાગ દ્વારા આદિમ ભાગ સુધી અનન્ય છે. ગૌસનું લેમ્મા સૂચવે છે કે બે આદિમ બહુપદીઓનું ગુણાકાર આદિમ છે. તે તેને અનુસરે છે અને R અને F પર GCD વચ્ચેનો સંબંધ અગાઉના વિભાગના સંબંધો R [X] અને F [X] માં GCD વચ્ચે મજબૂત સંબંધ સૂચવે છે. અસ્પષ્ટતાઓને ટાળવા માટે, સંકેતલિપી "જી. સી. ડી". ને અનુક્રમિત કરવામાં આવશે, નીચેનામાં, રિંગ દ્વારા જેમાં જી. સી. ડી. ની ગણતરી કરવામાં આવે છે. જો q1 અને q2 એ F [X] ને અનુસરે છે, તો પછી જો p1 અને p2 એ R [X] ને અનુસરે છે, તો પછી અને આમ બહુપદી GCD ની ગણતરી અનિવાર્યપણે F [X] અને R [X] પર સમાન સમસ્યા છે. તર્કસંગત સંખ્યાઓ પર અવિભાજ્ય બહુપદીઓ માટે, કોઈ એવું વિચારી શકે છે કે યુક્લિડનું અલ્ગોરિધમ GCD ની ગણતરી માટે એક અનુકૂળ પદ્ધતિ છે. જો કે, તેમાં પૂર્ણાંકોની મોટી સંખ્યામાં અપૂર્ણાંકોને સરળ બનાવવાનો સમાવેશ થાય છે, અને પરિણામી અલ્ગોરિધમ કાર્યક્ષમ નથી. આ કારણોસર, પૂર્ણાંકો પર માત્ર બહુપદીઓ સાથે કામ કરવા માટે યુક્લિડના અલ્ગોરિધમમાં ફેરફાર કરવા માટે પદ્ધતિઓ તૈયાર કરવામાં આવી છે. તેમાં યુક્લિડિયન વિભાગને બદલવાનો સમાવેશ થાય છે, જે અપૂર્ણાંકોને કહેવાતા સ્યુડો-ડિવિઝન દ્વારા રજૂ કરે છે, અને યુક્લિડના અલ્ગોરિધમનો બાકીના ક્રમને કહેવાતા સ્યુડો-રિમેન્ડર સિક્વન્સ દ્વારા બદલે છે (નીચે જુઓ). બહુવિધ બહુપદીઓ માટે GCD અસ્તિત્વમાં છે તેનો પુરાવો અગાઉના વિભાગમાં આપણે જોયું છે કે R [X] માં બહુપદીઓનું GCD, R અને F [X] માં GCD માંથી કાઢવામાં આવી શકે છે. સાબિતી પર નજીકથી નજર નાખવી એ દર્શાવે છે કે આ આપણને R [X] માં GCD ના અસ્તિત્વને સાબિત કરવાની મંજૂરી આપે છે, જો તેઓ R અને F [X] માં અસ્તિત્વ ધરાવે છે. ખાસ કરીને, જો જીસીડી આરમાં અસ્તિત્વ ધરાવે છે, અને જો એક્સને એક ચલમાં ઘટાડવામાં આવે છે, તો આ સાબિત કરે છે કે જીસીડી આર [એક્સ] માં અસ્તિત્વ ધરાવે છે (યુક્લિડનું અલ્ગોરિધમ એફ [એક્સ] માં જીસીડીનું અસ્તિત્વ સાબિત કરે છે). n ચલમાં બહુપદીને (n−1) ચલમાં બહુપદીઓની વીંટી પર અવિભાજ્ય બહુપદી તરીકે ગણી શકાય. આમ ચલની સંખ્યા પર પુનરાવર્તન દર્શાવે છે કે જો GCD અસ્તિત્વ ધરાવે છે અને R માં ગણતરી કરી શકાય છે, તો તે અસ્તિત્વ ધરાવે છે અને R પરની દરેક બહુપરીમાણીય બહુપદી વીંટીમાં ગણતરી કરી શકાય છે. ખાસ કરીને, જો R એ પૂર્ણાંકોની વીંટી અથવા ક્ષેત્ર હોય, તો GCDs R [x1,., xn] માં અસ્તિત્વ ધરાવે છે, અને જે પહેલાનું છે તે તેમને ગણતરી કરવા માટે એક અલ્ગોરિધમ પ્રદાન કરે છે. અનન્ય ફેક્ટરાઇઝેશન ડોમેન પર બહુપદી રિંગ પણ એક અનન્ય ફેક્ટરાઇઝેશન ડોમેન છે તેનો પુરાવો સમાન છે, પરંતુ તે કોઈ અલ્ગોરિધમ પ્રદાન કરતું નથી, કારણ કે ક્ષેત્ર પર અવિભાજ્ય બહુપદીઓને પરિબળ બનાવવા માટે કોઈ સામાન્ય અલ્ગોરિધમ નથી (એવા ક્ષેત્રોના ઉદાહરણો છે કે જેના માટે અવિભાજ્ય બહુપદીઓ માટે કોઈ ફેક્ટરાઇઝેશન અલ્ગોરિધમ અસ્તિત્વમાં નથી). સ્યુડો-રિમેઇન્ડર સિક્વન્સ આ વિભાગમાં, આપણે એક ઇન્ટિગ્રલ ડોમેન Z (સામાન્ય રીતે પૂર્ણાંકોની રીંગ Z) અને તેના અપૂર્ણાંક ક્ષેત્ર Q (સામાન્ય રીતે તર્કસંગત સંખ્યાઓનું ક્ષેત્ર Q) ને ધ્યાનમાં લઈએ છીએ. એકવિધ બહુપદી વીંટી Z [X] માં બે બહુપદી A અને B આપવામાં આવે તો, B દ્વારા A નો યુક્લિડિયન વિભાગ (Q પર) ભાગાકાર અને શેષ પ્રદાન કરે છે જે Z [X] સાથે સંબંધિત ન પણ હોય. કારણ કે, જો કોઈ યુક્લિડના અલ્ગોરિધમને નીચેની બહુપદીઓ પર લાગુ કરે છે અને યુક્લિડના અલ્ગોરિધમનો ક્રમિક અવશેષો એ છે કે, એક જુએ છે કે, ઇનપુટ બહુપદીઓના ગુણાંકના નાના ડિગ્રી અને નાના કદ હોવા છતાં, વ્યક્તિએ મોટા કદના પૂર્ણાંક અપૂર્ણાંકોને હેરફેર અને સરળ બનાવવું પડશે. સ્યુડો-ડિવિઝન યુક્લિડના અલ્ગોરિધમના એક પ્રકારને મંજૂરી આપવા માટે રજૂ કરવામાં આવ્યું છે, જેના માટે તમામ અવશેષો Z [X] ના છે. જો અને અને a, b દ્વારા A ના સ્યુડો-ડિવિઝનનું સ્યુડો-રિમેઇન્ડર, જે પ્રિમ (A, B) દ્વારા સૂચવવામાં આવે છે, તે B નો અગ્રણી ગુણાંક (Xb નો ગુણાંક) છે. Z [X] માં બે બહુપદીઓના સ્યુડો-ડિવિઝનનું સ્યુડો-રિમેઇન્ડર હંમેશા Z [X] સાથે સંબંધિત હોય છે. સ્યુડો-રિમેઇન્ડર ક્રમ એ યુક્લિડના અલ્ગોરિધમની સૂચનાને બદલીને મેળવેલા (સ્યુડો) અવશેષો આરઆઇનો ક્રમ છે, જ્યાં α એ ઝેડનું એક તત્વ છે જે અંશના દરેક ગુણાંકને બરાબર વિભાજિત કરે છે. α ની વિવિધ પસંદગીઓ વિવિધ સ્યુડો-રિમેઇન્ડર સિક્વન્સ આપે છે, જે આગામી પેટા વિભાગોમાં વર્ણવવામાં આવ્યા છે. જો બહુપદીઓને ઉલટાવી શકાય તેવા અચળાંકો (Q માં) દ્વારા ગુણાકાર કરવામાં આવે તો બે બહુપદીઓના સામાન્ય ભાજકો બદલાતા નથી, તેથી સ્યુડો-રિમેઇન્ડર ક્રમમાં છેલ્લો બિન-શૂન્ય શબ્દ ઇનપુટ બહુપદીનો GCD (Q [X] માં) છે. તેથી, સ્યુડો-રિમેઇન્ડર સિક્વન્સ ક્યૂમાં અપૂર્ણાંકો રજૂ કર્યા વિના ક્યૂ [એક્સ] માં જીસીડીની ગણતરી કરવાની મંજૂરી આપે છે. કેટલાક સંદર્ભોમાં, સ્યુડો-રિમેઇન્ડરના અગ્રણી ગુણાંકની નિશાનીને નિયંત્રિત કરવી જરૂરી છે. આ સામાન્ય રીતે પરિણામ અને ઉપ-પરિણામોની ગણતરી કરતી વખતે અથવા સ્ટર્મના પ્રમેયનો ઉપયોગ કરતી વખતે થાય છે. આ નિયંત્રણ ક્યાં તો સ્યુડો-રિમેઇન્ડરની વ્યાખ્યામાં તેના નિરપેક્ષ મૂલ્ય દ્વારા બદલીને અથવા તેના ચિહ્નને નિયંત્રિત કરીને કરી શકાય છે (જો બાકીના તમામ ગુણાંકને વિભાજિત કરે છે, તો તે જ સાચું છે). તુચ્છ સ્યુડો-રિમેઇન્ડર ક્રમ સૌથી સરળ (વ્યાખ્યાયિત કરવા માટે) શેષ ક્રમમાં હંમેશા લેવાનો સમાવેશ થાય છે. વ્યવહારમાં, તે રસપ્રદ નથી, કારણ કે ગુણાંકનું કદ ઇનપુટ બહુપદીઓની માત્રા સાથે ઝડપથી વધે છે. આ અગાઉના વિભાગના ઉદાહરણ પર સ્પષ્ટ દેખાય છે, જેના માટે ક્રમિક સ્યુડો-રિમેઇન્ડર્સ છે ક્રમિક અવશેષોના ગુણાંકની સંખ્યા અલ્ગોરિધમનો દરેક પુનરાવર્તન પર બમણાથી વધુ હોય છે. આ તુચ્છ સ્યુડો-રિમેઇન્ડર સિક્વન્સની લાક્ષણિક વર્તણૂક છે. આદિમ સ્યુડો-રિમેઇન્ડર ક્રમ આદિમ સ્યુડો-રિમેઇન્ડર ક્રમમાં અંશની સામગ્રીને α માટે લેવાનો સમાવેશ થાય છે. આમ તમામ r એ આદિમ બહુપદીઓ છે. આદિમ સ્યુડો-રિમેઇન્ડર ક્રમ એ સ્યુડો-રિમેઇન્ડર ક્રમ છે, જે સૌથી નાના ગુણાંક પેદા કરે છે. જો કે તેને ઝેડમાં સંખ્યાબંધ જીસીડીની ગણતરી કરવાની જરૂર છે, અને તેથી વ્યવહારમાં ઉપયોગમાં લેવા માટે તે પૂરતા પ્રમાણમાં કાર્યક્ષમ નથી, ખાસ કરીને જ્યારે ઝેડ પોતે બહુપદી રિંગ છે. અગાઉના વિભાગોની જેમ જ ઇનપુટ સાથે, તેમની સામગ્રી દ્વારા વિભાજન પછી ક્રમિક અવશેષો છે ગુણાંકનું નાનું કદ એ હકીકતને છુપાવે છે કે સંખ્યાબંધ પૂર્ણાંકો GCD અને GCD દ્વારા વિભાગોની ગણતરી કરવામાં આવી છે. સબ-રિઝલ્ટન્ટ સ્યુડો-રિમેઇન્ડર ક્રમ એ સબ-રિઝલ્ટન્ટ ક્રમની ગણતરી સ્યુડો-રિમેઇન્ડર્સ સાથે પણ કરી શકાય છે. આ પ્રક્રિયામાં α ને એવી રીતે પસંદ કરવામાં આવે છે કે દરેક r એક ઉપ-પરિણામી બહુપદી હોય. આશ્ચર્યજનક રીતે, α ની ગણતરી ખૂબ જ સરળ છે (નીચે જુઓ). બીજી બાજુ, અલ્ગોરિધમનો ચોકસાઈનો પુરાવો મુશ્કેલ છે, કારણ કે તેમાં સતત બે અવશેષોની ડિગ્રીના તફાવત માટેની તમામ શક્યતાઓને ધ્યાનમાં લેવી જોઈએ. ઉપ-પરિણામ ક્રમમાં ગુણાંક ભાગ્યે જ આદિમ સ્યુડો-રિમેઇન્ડર ક્રમ કરતા ઘણા મોટા હોય છે. ઝેડમાં જીસીડી ગણતરીઓની જરૂર નથી, તેથી સ્યુડો-રિમેઇન્ડર્સ સાથેનો ઉપ-પરિણામ ક્રમ સૌથી કાર્યક્ષમ ગણતરી આપે છે. અગાઉના વિભાગોમાં સમાન ઇનપુટ સાથે, ક્રમિક અવશેષો છે ગુણાંક વાજબી કદ ધરાવે છે. તેઓ કોઈપણ GCD ગણતરી વિના મેળવવામાં આવે છે, માત્ર ચોક્કસ વિભાગો. આ આ અલ્ગોરિધમને આદિમ સ્યુડો-રિમેન્ડર સિક્વન્સ કરતાં વધુ કાર્યક્ષમ બનાવે છે. સ્યુડો-રિમેઇન્ડર્સ સાથે સબ-રિઝલ્ટન્ટ સિક્વન્સની ગણતરી કરતી અલ્ગોરિધમ નીચે આપવામાં આવી છે. આ અલ્ગોરિધમમાં, ઇનપુટ એ Z [X] માં બહુપદીઓની જોડી છે. આ Z [X] માં ક્રમિક સ્યુડો અવશેષો છે, ચલો i અને બિન-નકારાત્મક પૂર્ણાંકો છે, અને ગ્રીક અક્ષરો Z માં તત્વોને સૂચવે છે. વિધેયો ડીગ () અને રેમ () બહુપદીની ડિગ્રી અને યુક્લિડિયન વિભાગના બાકીના ભાગને સૂચવે છે. અલ્ગોરિધમમાં, આ શેષ હંમેશા Z [X] માં હોય છે. છેવટે સૂચવેલા વિભાગો હંમેશા ચોક્કસ હોય છે અને તેમનું પરિણામ Z [X] અથવા Z માં હોય છે. નોંધઃ "lc" એ અગ્રણી ગુણાંક માટે વપરાય છે, જે ચલની ઉચ્ચતમ ડિગ્રીનો ગુણાંક છે. આ અલ્ગોરિધમ માત્ર સૌથી મોટા સામાન્ય ભાજક (છેલ્લા બિન-શૂન્ય) ની જ નહીં, પરંતુ તમામ ઉપ-પરિણામી બહુપદીઓની પણ ગણતરી કરે છેઃ બાકીની-th ઉપ-પરિણામી બહુપદી છે. જો,-th ઉપ-પરિણામ બહુપદી છે. અન્ય તમામ ઉપ-પરિણામી બહુપદીઓ શૂન્ય છે. સ્યુડો-રિમેન્ડર્સ સાથે સ્ટર્મ સિક્વન્સ સ્ટર્મ સિક્વન્સ જેવા જ ગુણધર્મો ધરાવતા સિક્વન્સ બનાવવા માટે સ્યુડો-રિમેન્ડર્સનો ઉપયોગ કરી શકે છે. આ માટે ક્રમિક સ્યુડો-રિમેઇન્ડર્સના સંકેતોને નિયંત્રિત કરવાની જરૂર છે, જેથી સ્ટર્મ ક્રમમાં સમાન સંકેતો હોય. આ સુધારેલા સ્યુડો-રિમેઇન્ડરને નીચે પ્રમાણે વ્યાખ્યાયિત કરીને કરી શકાય છે. જો અને અને a, b દ્વારા A ના સ્યુડો-ડિવિઝનનું સુધારેલ સ્યુડો-રિમેઇન્ડર પ્રિમ2 (A, B) એ છે જ્યાં |lc (B) | એ B ના અગ્રણી ગુણાંક (Xb નો ગુણાંક) નું નિરપેક્ષ મૂલ્ય છે. પૂર્ણાંક ગુણાંક સાથે ઇનપુટ બહુપદીઓ માટે, આ પૂર્ણાંક ગુણાંક સાથે બહુપદીઓ ધરાવતા સ્ટર્મ ક્રમની પુનઃપ્રાપ્તિની મંજૂરી આપે છે. સબ-રિઝલ્ટન્ટ સ્યુડો-રિમેઇન્ડર ક્રમ એ જ રીતે સુધારી શકાય છે, આ કિસ્સામાં અવશેષોના ચિહ્નો તર્કસંગત પર ગણતરી કરાયેલા ચિહ્નો સાથે મેળ ખાય છે. નોંધ લો કે ઉપર આપેલા સબ-રિઝલ્ટન્ટ સ્યુડો-રિમેઇન્ડર ક્રમની ગણતરી કરવા માટેનું અલ્ગોરિધમ ખોટી સબ-રિઝલ્ટન્ટ બહુપદીઓની ગણતરી કરશે જો કોઈ તેના બદલે ઉપયોગ કરે છે. મોડ્યુલર GCD અલ્ગોરિધમ જો f અને g એ F [x] માં અમુક મર્યાદિત રીતે ઉત્પન્ન થયેલ ક્ષેત્ર F માટે બહુપદીઓ હોય, તો યુક્લિડિયન અલ્ગોરિધમ એ તેમના GCD ની ગણતરી કરવાની સૌથી કુદરતી રીત છે. જો કે, આધુનિક કોમ્પ્યુટર બીજગણિત પ્રણાલીઓ તેનો ઉપયોગ ત્યારે જ કરે છે જ્યારે મધ્યવર્તી અભિવ્યક્તિ ફૂલતી હોય તેવી ઘટનાને કારણે F મર્યાદિત હોય. જો કે યુક્લિડિયન અલ્ગોરિધમ દરમિયાન ડિગ્રી ઘટતી રહે છે, જો એફ મર્યાદિત ન હોય તો ગણતરી દરમિયાન બહુપદીઓનું બીટ કદ (ક્યારેક નાટકીય રીતે) વધી શકે છે કારણ કે એફમાં પુનરાવર્તિત અંકગણિત કામગીરી મોટા સમીકરણો તરફ દોરી જાય છે. ઉદાહરણ તરીકે, બે પરિમાણીય સંખ્યાઓનો ઉમેરો કે જેના છેદ b દ્વારા બંધાયેલ હોય તે પરિમાણીય સંખ્યા તરફ દોરી જાય છે જેનો છેદ b2 દ્વારા બંધાયેલ હોય છે, તેથી સૌથી ખરાબ કિસ્સામાં, બીટનું કદ માત્ર એક ઓપરેશન સાથે લગભગ બમણું થઈ શકે છે. ગણતરીને ઝડપી બનાવવા માટે, એક રીંગ D લો જેના માટે f અને g એ D [x] માં છે, અને એક આદર્શ I લો જેથી D/I એક મર્યાદિત રીંગ હોય. પછી યુક્લિડિયન અલ્ગોરિધમ સાથે આ મર્યાદિત રીંગ પર GCD ની ગણતરી કરો. પુનર્નિર્માણ તકનીકોનો ઉપયોગ (ચીની શેષ પ્રમેય, તર્કસંગત પુનર્નિર્માણ, વગેરે) f અને g ની GCD ને તેના ઇમેજ મોડ્યુલોમાંથી સંખ્યાબંધ આદર્શો I થી પુનઃપ્રાપ્ત કરી શકાય છે. કોઈ સાબિત કરી શકે છે કે આ કામ કરે છે જો કોઈ વ્યક્તિ બિન-ન્યૂનતમ ડિગ્રી સાથે મોડ્યુલર છબીઓને કાઢી નાખે છે, અને આદર્શો I મોડ્યુલો ટાળે છે જે અગ્રણી ગુણાંક અદૃશ્ય થઈ જાય છે. ધારો કે, અને. જો આપણે લઈએ તો તે એક મર્યાદિત રીંગ છે (ક્ષેત્ર નથી કારણ કે તે મહત્તમ નથી). યુક્લિડિયન અલ્ગોરિધમ ઇનની છબીઓ પર લાગુ થાય છે અને 1 પરત કરે છે. આ સૂચવે છે કે અંદરની GCD પણ 1 હોવી જોઈએ. નોંધ લો કે આ ઉદાહરણ સરળતાથી કોઈપણ પદ્ધતિ દ્વારા નિયંત્રિત કરી શકાય છે કારણ કે અભિવ્યક્તિ માટે ડિગ્રી ખૂબ નાની હતી, પરંતુ તે સમજાવે છે કે જો બે બહુપદીઓમાં GCD 1 હોય, તો મોડ્યુલર અલ્ગોરિધમ એક જ આદર્શ પછી સમાપ્ત થવાની સંભાવના છે. બહુપદી વિષયોની યાદી પણ જુઓ બહુવિધ વિભાજન અલ્ગોરિધમ સંદર્ભ બહુપદી કમ્પ્યુટર બીજગણિત