Thue's lemma
મોડ્યુલર અંકગણિતમાં, થ્યુના લેમ્મા આશરે જણાવે છે કે દરેક મોડ્યુલર પૂર્ણાંકને "મોડ્યુલર અપૂર્ણાંક" દ્વારા રજૂ કરી શકાય છે જેમ કે અંશ અને છેદમાં સંપૂર્ણ મૂલ્યો હોય છે જે મોડ્યુલસના વર્ગમૂળ કરતા વધારે ન હોય. વધુ ચોક્કસપણે, સાથે પૂર્ણાંકોની દરેક જોડી માટે, બે હકારાત્મક પૂર્ણાંકો આપવામાં આવે છે અને જેમ કે, ત્યાં બે પૂર્ણાંકો હોય છે અને જેમ કે અને સામાન્ય રીતે, એક વર્ગમૂળ કરતા મોટા સૌથી નાના પૂર્ણાંકને લે છે અને તેની બરાબર હોય છે, પરંતુ સામાન્ય સ્વરૂપ કેટલીકવાર ઉપયોગી હોય છે, અને વિશિષ્ટતા પ્રમેય (નીચે) ને જણાવવાનું સરળ બનાવે છે. સૌપ્રથમ જાણીતો પુરાવો એ છે કે જેમણે કબૂતરના છિદ્રની દલીલનો ઉપયોગ કર્યો હતો. તેનો ઉપયોગ બે વર્ગના સરવાળા પર ફર્માટના પ્રમેયને સાબિત કરવા માટે m ને એક અવિભાજ્ય p તરીકે લઈ શકાય છે જે 1 મોડ્યુલો 4 સાથે એકરૂપ છે અને a ને a2 + 1 = 0 મોડ p ને સંતોષવા માટે લઈ શકાય છે. (વિલ્સનના પ્રમેય દ્વારા "p" માટે આવા "a" ની ખાતરી આપવામાં આવે છે.) વિશિષ્ટતા સામાન્ય રીતે, થ્યુના લેમ્મા દ્વારા જે ઉકેલના અસ્તિત્વ પર ભાર મૂકવામાં આવે છે તે અનન્ય નથી. ઉદાહરણ તરીકે, જ્યારે સામાન્ય રીતે ઘણા ઉકેલો હોય, જો કે તે ખૂબ નાના ન હોય. તેથી, કોઈ વ્યક્તિ માત્ર પરિમેય સંખ્યા માટે વિશિષ્ટતાની આશા રાખી શકે છે, જે જો y અને m સહમૌલિક હોય તો એકરૂપ મોડ્યુલો છે. તેમ છતાં, આ પરિમેય સંખ્યા અનન્ય હોવી જરૂરી નથી; ઉદાહરણ તરીકે, જો, અને, એક પાસે બે ઉકેલો છે. જો કે, જો કોઈ ઉકેલ અસ્તિત્વમાં હોય, તો તે અનન્ય છે. વધુ ચોક્કસપણે, ઉપરોક્ત સંકેતો સાથે, જો અને, સાથે અને પછી આ પરિણામ તર્કસંગત પુનર્નિર્માણ માટેનો આધાર છે, જે તર્કસંગત સંખ્યાઓની ગણતરી માટે મોડ્યુલર અંકગણિતનો ઉપયોગ કરવાની મંજૂરી આપે છે, જેના માટે કોઈ વ્યક્તિ અંકો અને છેદની સીમા જાણે છે. સાબિતી એકદમ સરળ છેઃ દરેક એકરૂપતાને બીજાથી ગુણાકાર કરીને અને બાદ કરીને, એકને મળે છે. પૂર્વધારણાઓ સૂચવે છે કે દરેક પદનું નિરપેક્ષ મૂલ્ય તેના કરતા ઓછું હોય છે, અને આમ તેમના તફાવતનું નિરપેક્ષ મૂલ્ય તેના કરતા ઓછું હોય છે. આ સૂચવે છે કે, તેથી પરિણામ. કોમ્પ્યુટિંગ સોલ્યુશન્સ થ્યુના લેમ્માનો મૂળ પુરાવો કાર્યક્ષમ નથી, તે અર્થમાં કે તે ઉકેલની ગણતરી માટે કોઈ ઝડપી પદ્ધતિ પ્રદાન કરતું નથી. વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ, આપણને એક એવો પુરાવો પ્રદાન કરવાની મંજૂરી આપે છે જે એક કાર્યક્ષમ અલ્ગોરિધમ તરફ દોરી જાય છે જે યુક્લિડિયન અલ્ગોરિધમ જેવી જ કોમ્પ્યુટેશનલ જટિલતા ધરાવે છે. વધુ ચોક્કસપણે, બે પૂર્ણાંકોને જોતાં અને થ્યુના લેમ્મામાં દેખાય છે, વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ પૂર્ણાંકોના ત્રણ ક્રમની ગણતરી કરે છે, અને જેમ કે જ્યાં પૂર્ણાંકો બિન-નકારાત્મક હોય અને સખત રીતે ઘટતા હોય. ઇચ્છિત ઉકેલ એ છે કે, નિશાની સુધી, પ્રથમ જોડી એવી છે. તર્કસંગત કાર્યો દ્વારા ટેલર શ્રેણીનો અંદાજ કાઢવા માટે સમાન સિદ્ધાંત પેડે અંદાજ પણ જુઓ.