Thue's lemma
মডুলার পাটিগণিতে, থুয়ের লেমা মোটামুটিভাবে বলে যে প্রতিটি মডুলার পূর্ণসংখ্যাকে একটি "মডুলার ভগ্নাংশ" দ্বারা এমনভাবে উপস্থাপন করা যেতে পারে যাতে সংখ্যা এবং হরের পরম মান মডুলাসের বর্গমূলের চেয়ে বেশি না হয়। আরও সুনির্দিষ্টভাবে, পূর্ণসংখ্যার প্রতিটি জোড়ের জন্য, দুটি ধনাত্মক পূর্ণসংখ্যা দেওয়া হয়েছে এবং এমন যে, দুটি পূর্ণসংখ্যা রয়েছে এবং সাধারণত, একটি এর বর্গমূলের চেয়ে বড় ক্ষুদ্রতম পূর্ণসংখ্যার সমান হয়, তবে সাধারণ রূপটি কখনও কখনও কার্যকর হয় এবং স্বতন্ত্রতা উপপাদ্য (নীচে) বর্ণনা করা সহজ করে তোলে। প্রথম পরিচিত প্রমাণটি পায়রার গর্ত যুক্তি ব্যবহার করার জন্য দায়ী। এটি দুটি বর্গের যোগফলের উপর ফারমাটের উপপাদ্য প্রমাণ করতে ব্যবহার করা যেতে পারে m কে একটি মৌলিক p হিসাবে গ্রহণ করে যা 1 মডুলো 4 এর সাথে সর্বসম এবং a কে a2 + 1 = 0 মোড p সন্তুষ্ট করার জন্য গ্রহণ করে। (উইলসনের উপপাদ্য দ্বারা "p" এর জন্য এই ধরনের "a" নিশ্চিত করা হয়।) সাধারণভাবে, যে সমাধানটির অস্তিত্ব থুয়ের লেমা দ্বারা দাবি করা হয় তা অনন্য নয়। উদাহরণস্বরূপ, যখন সাধারণত বেশ কয়েকটি সমাধান থাকে, তবে তা যদি খুব ছোট না হয়। অতএব, কেউ শুধুমাত্র মূলদ সংখ্যার জন্য স্বতন্ত্রতার আশা করতে পারে, যার সাথে সর্বব্যাপী মডুলো যদি y এবং m সহমৌলিক হয়। তা সত্ত্বেও, এই মূলদ সংখ্যাটি অনন্য হওয়ার প্রয়োজন নেই; উদাহরণস্বরূপ, যদি, এবং, একটির দুটি সমাধান রয়েছে। যাইহোক, যথেষ্ট ছোট এবং যদি কোনও সমাধান বিদ্যমান থাকে তবে এটি অনন্য। আরও সুনির্দিষ্টভাবে, উপরের স্বরলিপির সঙ্গে, যদি এবং, সহ এবং তারপর এই ফলাফলটি যুক্তিসঙ্গত পুনর্গঠনের ভিত্তি, যা যুক্তিসঙ্গত সংখ্যা গণনা করার জন্য মডুলার পাটিগণিত ব্যবহার করার অনুমতি দেয় যার জন্য কেউ সংখ্যা এবং হরের সীমা জানে। প্রমাণটি বরং সহজঃ প্রতিটি সঙ্গতিকে অন্যটির দ্বারা গুণ করে এবং বিয়োগ করে, একটি পায় অনুমানগুলি বোঝায় যে প্রতিটি শব্দের একটি পরম মান তার চেয়ে কম, এবং এইভাবে তাদের পার্থক্যের পরম মান তার চেয়ে কম। এটি বোঝায় যে, তাই ফলাফল। কম্পিউটিং সমাধান থুয়ের লেম্মার মূল প্রমাণটি কার্যকর নয়, এই অর্থে যে এটি সমাধানটি গণনা করার জন্য কোনও দ্রুত পদ্ধতি সরবরাহ করে না। বর্ধিত ইউক্লিডীয় অ্যালগরিদম, আমাদের এমন একটি প্রমাণ প্রদান করতে দেয় যা একটি দক্ষ অ্যালগরিদমের দিকে পরিচালিত করে যার ইউক্লিডীয় অ্যালগরিদমের মতো একই গণনামূলক জটিলতা রয়েছে। আরও সুনির্দিষ্টভাবে, দুটি পূর্ণসংখ্যার পরিপ্রেক্ষিতে এবং থুয়ের লেম্মায় উপস্থিত, বর্ধিত ইউক্লিডীয় অ্যালগরিদম পূর্ণসংখ্যার তিনটি ক্রম গণনা করে, এবং যেখানে পূর্ণসংখ্যা অ-ঋণাত্মক এবং কঠোরভাবে হ্রাস পায়। কাঙ্ক্ষিত সমাধানটি হল, চিহ্ন পর্যন্ত, প্রথম জোড়াটি এমন। আরও দেখুন প্যাডে আনুমানিক, একটি অনুরূপ তত্ত্ব, যুক্তিসঙ্গত ফাংশন দ্বারা টেলর সিরিজের আনুমানিক হিসাবের জন্য।