Thue's lemma
मॉड्यूलर अंकगणित में, थ्यू का लेम्मा मोटे तौर पर बताता है कि प्रत्येक मॉड्यूलर पूर्णांक को एक "मॉड्यूलर अंश" द्वारा दर्शाया जा सकता है जैसे कि अंश और भाजक के निरपेक्ष मान मॉड्यूलस के वर्गमूल से अधिक न हों। अधिक सटीक रूप से, पूर्णांकों की प्रत्येक जोड़ी के लिए, दो सकारात्मक पूर्णांक दिए गए हैं और इस तरह कि, दो पूर्णांक हैं और ऐसे कि और आमतौर पर, एक वर्गमूल से बड़े सबसे छोटे पूर्णांक को लेता है और उसके बराबर होता है, लेकिन सामान्य रूप कभी-कभी उपयोगी होता है, और विशिष्टता प्रमेय (नीचे) को बताना आसान बनाता है। पहले ज्ञात प्रमाण का श्रेय उस व्यक्ति को दिया जाता है जिसने कबूतर छेद तर्क का उपयोग किया था। इसका उपयोग दो वर्गों के योग पर फर्माट के प्रमेय को साबित करने के लिए किया जा सकता है, जिसमें m को एक अभाज्य p के रूप में लिया जा सकता है जो 1 मॉडुलो 4 के लिए सर्वांगसम है और a को a2 + 1 = 0 मॉड p को संतुष्ट करने के लिए लिया जा सकता है। (विल्सन के प्रमेय द्वारा "p" के लिए इस तरह के "a" की गारंटी है।) विशिष्टता सामान्य तौर पर, थ्यू के सिद्धांत द्वारा जिस समाधान के अस्तित्व पर जोर दिया जाता है, वह अद्वितीय नहीं है। उदाहरण के लिए, जब आमतौर पर कई समाधान होते हैं, बशर्ते कि वे बहुत छोटे न हों। इसलिए, कोई केवल परिमेय संख्या के लिए विशिष्टता की उम्मीद कर सकता है, जो कि सर्वांगसम मॉड्यूलो है यदि y और m सहमौलिक हैं। फिर भी, यह परिमेय संख्या अद्वितीय होने की आवश्यकता नहीं है; उदाहरण के लिए, यदि, और, एक के दो समाधान हैं। हालाँकि, यदि कोई समाधान मौजूद है, तो यह अद्वितीय है। अधिक सटीक रूप से, उपरोक्त संकेतन के साथ, यदि और, के साथ और फिर यह परिणाम परिमेय पुनर्निर्माण का आधार है, जो परिमेय संख्याओं की गणना के लिए मॉड्यूलर अंकगणित का उपयोग करने की अनुमति देता है, जिसके लिए कोई अंश और भाजकों की सीमा जानता है। प्रमाण अपेक्षाकृत आसान हैः प्रत्येक सर्वांगसम को दूसरे से गुणा करने और घटाने से, एक प्राप्त होता है परिकल्पनाओं का तात्पर्य है कि प्रत्येक शब्द का निरपेक्ष मूल्य उससे कम है, और इस प्रकार उनके अंतर का निरपेक्ष मूल्य उससे कम है। इसका तात्पर्य यह है कि, इसलिए परिणाम। कम्प्यूटिंग समाधान थ्यू के लेम्मा का मूल प्रमाण कुशल नहीं है, इस अर्थ में कि यह समाधान की गणना के लिए कोई तेज़ विधि प्रदान नहीं करता है। विस्तारित यूक्लिडियन एल्गोरिथ्म, हमें एक प्रमाण प्रदान करने की अनुमति देता है जो एक कुशल एल्गोरिथ्म की ओर ले जाता है जिसमें यूक्लिडियन एल्गोरिथ्म की समान कम्प्यूटेशनल जटिलता होती है। अधिक सटीक रूप से, दो पूर्णांकों को देखते हुए और थ्यू के लेम्मा में दिखाई देने पर, विस्तारित यूक्लिडियन एल्गोरिथ्म पूर्णांकों के तीन अनुक्रमों की गणना करता है, और इस तरह कि जहां पूर्णांक गैर-नकारात्मक हैं और सख्ती से कम हो रहे हैं। वांछित समाधान, संकेत तक, पहली जोड़ी ऐसी है। तर्कसंगत कार्यों द्वारा टेलर श्रृंखला को अनुमानित करने के लिए एक समान सिद्धांत, पैडे सन्निकटन भी देखें।