Root of unity modulo n
সংখ্যা তত্ত্বে, ধনাত্মক পূর্ণসংখ্যা k-এর জন্য একক মডুলো n-এর একটি kth মূল হল পূর্ণসংখ্যা মডুলো n-এর বলয়ে ঐক্যের মূল; অর্থাৎ, সমীকরণের (বা সঙ্গতি) একটি সমাধান x। যদি x-এর জন্য k সবচেয়ে ছোট সূচক হয়, তাহলে x-কে একক মডুলো n-এর আদিম kth মূল বলা হয়। স্বরলিপি এবং পরিভাষার জন্য মডুলার পাটিগণিত দেখুন। ইউনিটি মডুলোর মূলগুলি ঠিক সেই পূর্ণসংখ্যা যা সহমৌলিক। প্রকৃতপক্ষে, এই পূর্ণসংখ্যাগুলি অয়লারের উপপাদ্য অনুসারে একক মডুলোর মূল এবং অন্যান্য পূর্ণসংখ্যাগুলি একক মডুলোর মূল হতে পারে না, কারণ এগুলি শূন্য বিভাজক মডুলো। একটি আদিম মূল মডুলো হল পূর্ণসংখ্যা মডুলোর বলয়ের একক গোষ্ঠীর একটি জেনারেটর। যদি এবং শুধুমাত্র যদি যথাক্রমে কারমাইকেল ফাংশন এবং অয়লারের টোটিয়েন্ট ফাংশন হয় তবে আদিম মূল মডুলো বিদ্যমান। একক মডুলোর একটি মূল হল কিছু বিভাজকের জন্য একক মডুলোর একটি আদিম মূল এবং, বিপরীতভাবে, একক মডুলোর আদিম মূল রয়েছে যদি এবং শুধুমাত্র যদি একক বৈশিষ্ট্যের মূলগুলির একটি ভাজক হয় যদি x একক মডুলো n-এর একটি kth মূল হয়, তবে x একটি একক (বিপরীতমুখী) যার বিপরীত হয়। অর্থাৎ, x এবং n হল সহমৌলিক। যদি x একটি একক হয়, তবে এটি একক মডুলো n-এর একটি (আদিম) k-তম মূল, যেখানে k হল x মডুলো n-এর গুণনীয়ক ক্রম। যদি x এককের k-তম মূল হয় এবং শূন্য বিভাজক না হয়, তবে, কারণ k-তম মূলের সংখ্যা ব্যাপকভাবে স্বীকৃত প্রতীকের অভাবে, আমরা একক মডুলো n-এর k-তম মূলের সংখ্যা দ্বারা নির্দেশ করি। এটি বেশ কয়েকটি বৈশিষ্ট্যকে সন্তুষ্ট করেঃ যেখানে λ কারমাইকেল ফাংশনকে নির্দেশ করে এবং অয়লারের টোটিয়েন্ট ফাংশনকে নির্দেশ করে একটি গুণনীয়ক ফাংশন যেখানে বার বিভাজ্যতাকে নির্দেশ করে যেখানে সর্বনিম্ন সাধারণ গুণিতককে নির্দেশ করে। থেকে থেকে সঠিক ম্যাপিং জানা যায় না। যদি এটি জানা যেত, তবে পূর্ববর্তী আইনের সাথে এটি দ্রুত মূল্যায়নের একটি উপায় বের করবে। উদাহরণ লেট এবং। এই ক্ষেত্রে, একতার তিনটি ঘনমূল রয়েছে (1,2 এবং 4)। যাইহোক, যখন ঐক্যের শুধুমাত্র একটি ঘনমূল থাকে, একক 1 নিজেই। এই আচরণ জটিল সংখ্যার ক্ষেত্রের থেকে বেশ আলাদা যেখানে প্রতিটি অ-শূন্য সংখ্যার k kth মূল রয়েছে। একক বৈশিষ্ট্যের আদিম শিকড় আদিম শিকড় মডুলোর জন্য সর্বাধিক সম্ভাব্য র্যাডিক্স সূচক হল, যেখানে λ কারমাইকেল ফাংশনকে বোঝায়। ঐক্যের একটি আদিম মূলের জন্য একটি র্যাডিক্স সূচক হল এর একটি বিভাজক। এর প্রতিটি বিভাজক ঐক্যের একটি আদিম মূল উৎপন্ন করে। একতার একটি আদিম মূল বেছে নিয়ে (যা অবশ্যই λ এর সংজ্ঞা অনুসারে বিদ্যমান থাকতে হবে) এই ধরনের মূল অর্জন করা যেতে পারে, যার নাম দেওয়া হয় এবং শক্তি গণনা করা হয়। যদি x ঐক্যের একটি আদিম kth মূল এবং ঐক্যের একটি (অপরিহার্যভাবে আদিম নয়) lth মূল হয়, তাহলে k হল l এর একটি ভাজক। এটি সত্য, কারণ বেজাউটের পরিচয় k এবং l এর সমান একটি পূর্ণসংখ্যা রৈখিক সংমিশ্রণ প্রদান করে। যেহেতু k ন্যূনতম, তাই এটি অবশ্যই l এর বিভাজক হতে হবে এবং হতে হবে। আদিম kth মূলের সংখ্যা ব্যাপকভাবে স্বীকৃত প্রতীকের অভাবে, আমরা একক মডুলো n দ্বারা আদিম kth মূলের সংখ্যা নির্দেশ করি। এটি নিম্নলিখিত বৈশিষ্ট্যগুলিকে সন্তুষ্ট করেঃ ফলস্বরূপ ফাংশনের মান শূন্যের থেকে আলাদা, যেখানে বিভাজকের সংখ্যা গণনা করা হয়। কারণ, যেহেতু-1 সর্বদা 1-এর একটি বর্গমূল. জন্য এবং ইউলারের টোটিয়েন্ট ফাংশন হওয়ার সাথে এবং এর মধ্যে সংযোগটি একটি ডিরিচলেট কনভোলিউশন ব্যবহার করে মার্জিত উপায়ে লেখা যেতে পারেঃ, অর্থাৎ। এই সূত্রটি ব্যবহার করে পুনরাবৃত্তির মান গণনা করা যেতে পারে, যা মোবিয়াস বিপরীত সূত্রের সমতুল্য। x একক মডুলো n-এর একটি আদিম kth মূল কিনা তা পরীক্ষা করা দ্রুত সূচক দ্বারা, কেউ এটি পরীক্ষা করতে পারে। যদি এটি সত্য হয়, x হল একক মডুলো এন-এর একটি kth মূল, তবে অগত্যা আদিম নয়। যদি এটি একটি আদিম মূল না হয়, তবে k এর কিছু বিভাজক l থাকবে। এই সম্ভাবনাটি বাদ দেওয়ার জন্য, শুধুমাত্র কয়েকটি l এর সমান k কে একটি মৌলিক সংখ্যা দ্বারা ভাগ করার জন্য পরীক্ষা করতে হবে। অর্থাৎ, যা পরীক্ষা করা দরকার তা হ 'লঃ ঐক্য মডুলো এন-এর একটি আদিম kth মূল খুঁজে পাওয়া ঐক্যের আদিম kth মূলগুলির মধ্যে, আদিম th মূলগুলি প্রায়শই দেখা যায়। এইভাবে একটি আদিম মূল হওয়ার জন্য কিছু পূর্ণসংখ্যা চেষ্টা করার পরামর্শ দেওয়া হয়, যা দ্রুত সফল হবে। একটি আদিম মূল x-এর জন্য, সংখ্যাটি ঐক্যের একটি আদিম মূল। যদি k বিভাজিত না হয়, তাহলে একতার কোনও kth শিকড় থাকবে না। একাধিক আদিম kth মূল মডুলো n খুঁজে বের করা একবার একক x-এর একটি আদিম kth মূল পাওয়া গেলে, প্রতিটি শক্তি একতার একটি th মূল, তবে অগত্যা একটি আদিম মূল নয়। ক্ষমতা হল ঐক্যের একটি আদিম মূল, যদি এবং শুধুমাত্র যদি তা সহমৌলিক হয়। প্রমাণটি নিম্নরূপঃ যদি আদিম না হয়, তবে সহের একটি বিভাজক বিদ্যমান, এবং যেহেতু এবং সহমৌলিক, তাই মডুলোর একটি বিপরীত বিদ্যমান। এই ফলন, যার অর্থ এটি ঐক্যের আদিম মূল নয় কারণ সেখানে ছোট সূচক রয়েছে। অর্থাৎ, x কে সূচকীয় করে কেউ একতার বিভিন্ন আদিম kth মূল পেতে পারে, তবে এগুলি সমস্ত মূল নাও হতে পারে। যাইহোক, তাদের সব খুঁজে পাওয়া এত সহজ নয়। একক মডুলো এন-এর আদিম কে-তম মূল সহ একটি এন খুঁজে পাওয়া কোন পূর্ণসংখ্যা অবশিষ্টাংশ শ্রেণী বলয়ের মধ্যে ঐক্যের আদিম কে-তম মূল বিদ্যমান? এটি একটি-মাত্রিক পূর্ণসংখ্যা ভেক্টরের একটি পৃথক ফুরিয়ার রূপান্তর (আরও সুনির্দিষ্টভাবে একটি সংখ্যা তাত্ত্বিক রূপান্তর) গণনা করতে ব্যবহার করা যেতে পারে। বিপরীত রূপান্তরটি সম্পাদন করার জন্য, দ্বারা ভাগ করুন; অর্থাৎ, k একটি একক মডুলোও এই ধরনের n খুঁজে বের করার একটি সহজ উপায় হল গাণিতিক অগ্রগতিতে মডুলির সাপেক্ষে আদিম kth মূলগুলি পরীক্ষা করা এই সমস্ত মডুলি k-এর সহমৌলিক এবং এইভাবে k একটি একক। গাণিতিক অগ্রগতির উপর ডিরিচলেটের উপপাদ্য অনুসারে অগ্রগতিতে অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে এবং একটি মৌলিক সংখ্যার জন্য এটি ধারণ করে। সুতরাং যদি মৌলিক হয়, তাহলে, এবং এইভাবে ঐক্যের আদিম kth মূল রয়েছে। কিন্তু মৌলিক সংখ্যার জন্য পরীক্ষা খুব শক্তিশালী, এবং অন্যান্য উপযুক্ত মডুলিও থাকতে পারে। একক মডুলোর একাধিক আদিম মূল সহ একটি n খুঁজে বের করা n একক মডুলোর আদিম মূল রয়েছে এমন একটি মডুলাস খুঁজে বের করার জন্য, নিম্নলিখিত উপপাদ্যটি সমস্যাটিকে সহজতর করে দেয়ঃ প্রদত্ত ঐক্য মডুলোর আদিম মূল রয়েছে যদি এবং শুধুমাত্র যদি একক মডুলোর একটি আদিম মূল থাকে n। পশ্চাৎ দিকের প্রমাণঃ যদি একক মডুলোর একটি আদিম মূল থাকে যাকে বলা হয়, তবে এটি একক মডুলোর একটি মূল। সামনের দিকেঃ যদি একক মডুলোর আদিম মূল থাকে, তবে সমস্ত সূচক এর বিভাজক। এটি বোঝায় এবং এর অর্থ হল ঐক্য মডুলোর একটি আদিম মূল রয়েছে। তথ্যসূত্র মডুলার গাণিতিক