Root of unity modulo n
نمبر تھیوری میں، مثبت انٹیجرز k کے لیے یونٹی ماڈیولو n کا kth روٹ، n ≤ 2، انٹیجرز ماڈیولو n کی رنگ میں یونٹی کا روٹ ہے ؛ یعنی مساوات (یا ہم آہنگی) کا حل x۔ اگر x کے لیے اس طرح کا سب سے چھوٹا ایکسپونینٹ k ہے، تو x کو یونٹی ماڈیولو n کا ابتدائی kth روٹ کہا جاتا ہے۔ اشارے اور اصطلاحات کے لیے ماڈیولر ریاضی دیکھیں۔ یونٹی ماڈیولو کی جڑیں بالکل وہی انٹیجرز ہیں جن کے ساتھ ہم آہنگی ہوتی ہے۔ درحقیقت، یہ انٹیجر یولر تھیوریم کے مطابق یونٹی ماڈیولو کی جڑیں ہیں، اور دیگر انٹیجر یونٹی ماڈیولو کی جڑیں نہیں ہو سکتے، کیونکہ وہ زیرو ڈیوائزر ماڈیولو ہیں۔ ایک ابتدائی جڑ ماڈیولو، انٹیجرز ماڈیولو کے رنگ کی اکائیوں کے گروپ کا ایک جنریٹر ہے۔ ابتدائی جڑیں ماڈیولو موجود ہیں اگر اور صرف اس صورت میں جہاں اور بالترتیب کارمائیکل فنکشن اور یولر کا ٹوٹینٹ فنکشن ہوں۔ یونٹی ماڈیولو کی جڑ کچھ تقسیم کار کے لیے یونٹی ماڈیولو کی ابتدائی جڑ ہے اور، اس کے برعکس، یونٹی ماڈیولو کی ابتدائی جڑیں ہیں اگر اور صرف اس صورت میں جب یونٹی پراپرٹیز کی جڑوں کا تقسیم کار ہو۔ اگر x یونٹی ماڈیولو n کا kth جڑ ہے، تو x ایک یونٹ (الٹا) ہے جس کا الٹا ہے۔ یعنی x اور n کوپرائم ہیں۔ اگر x ایک اکائی ہے، تو یہ یونٹی ماڈیولو n کا (ابتدائی) kth جڑ ہے، جہاں k، x ماڈیولو n کا ضرب آرڈر ہے۔ اگر x یونٹی کا kth جڑ ہے اور صفر تقسیم کار نہیں ہے، تو، کیونکہ kth جڑوں کی تعداد وسیع پیمانے پر قبول شدہ علامت کی کمی کے لیے، ہم یونٹی ماڈیولو n کے kth جڑوں کی تعداد کو ظاہر کرتے ہیں۔ یہ متعدد خصوصیات کو مطمئن کرتا ہے: جہاں λ کارمائیکل فنکشن کی نشاندہی کرتا ہے اور اویلر کے ٹوٹیئنٹ فنکشن کی نشاندہی کرتا ہے وہ ایک ضرب فنکشن ہے جہاں بار تقسیم کی نشاندہی کرتا ہے جہاں سب سے کم مشترکہ ضرب کی نشاندہی کرتا ہے۔ سے لے کر تک کی درست نقشہ سازی معلوم نہیں ہے۔ اگر یہ معلوم ہوتا، تو پچھلے قانون کے ساتھ مل کر یہ فوری طور پر تشخیص کرنے کا ایک طریقہ فراہم کرتا۔ مثالیں لیٹ اینڈ۔ اس صورت میں، اتحاد کی تین مکعب جڑیں ہیں (1، 2، اور 4)۔ تاہم، جب اتحاد کی صرف ایک مکعب جڑ ہوتی ہے، تو وہ خود اکائی 1 ہوتی ہے۔ یہ طرز عمل پیچیدہ اعداد کے میدان سے بالکل مختلف ہے جہاں ہر غیر صفر نمبر کے k kth جڑ ہوتے ہیں۔ یونٹی پراپرٹیز کی ابتدائی جڑیں ابتدائی جڑوں کے ماڈیولو کے لیے زیادہ سے زیادہ ممکنہ ریڈکس ایکسپونینٹ ہے، جہاں λ کارمائیکل فنکشن کی نشاندہی کرتا ہے۔ اتحاد کی ابتدائی جڑ کے لیے ریڈکس ایکسپونینٹ کا تقسیم کنندہ ہوتا ہے۔ کا ہر تقسیم کنندہ اتحاد کی ایک ابتدائی جڑ پیدا کرتا ہے۔ کوئی بھی اس طرح کی جڑ کو اتحاد کی ایک ابتدائی جڑ (جو λ کی تعریف کے مطابق موجود ہونی چاہیے) کا انتخاب کرکے حاصل کر سکتا ہے، جس کا نام رکھا گیا ہے اور طاقت کا حساب لگایا گیا ہے۔ اگر x اتحاد کا ایک ابتدائی kth جڑ ہے اور اتحاد کا ایک (ضروری نہیں کہ ابتدائی) lth جڑ بھی ہے، تو k، l کا تقسیم کنندہ ہے۔ یہ درست ہے، کیونکہ بیزاوٹ کی شناخت سے k اور l کا ایک انٹیجر لکیری امتزاج حاصل ہوتا ہے۔ چونکہ k کم سے کم ہے، اس لیے اسے l کا تقسیم کنندہ ہونا چاہیے اور ہونا چاہیے۔ ابتدائی kth جڑوں کی تعداد وسیع پیمانے پر قبول شدہ علامت کی کمی کے لیے، ہم یونٹی ماڈیولو n کی ابتدائی kth جڑوں کی تعداد کی نشاندہی کرتے ہیں۔ یہ درج ذیل خصوصیات کو مطمئن کرتا ہے: نتیجتا فنکشن کی اقدار صفر سے مختلف ہوتی ہیں، جہاں تقسیم کاروں کی تعداد کا حساب لگایا جاتا ہے۔ کے لیے، چونکہ-1 ہمیشہ 1 کا مربع جڑ ہوتا ہے۔ کے لیے اور کے ساتھ اویلر کا ٹوٹینٹ فنکشن ہونے کے ساتھ اور کے درمیان تعلق کو ڈیرچلیٹ کنولیوشن کا استعمال کرتے ہوئے خوبصورت انداز میں لکھا جا سکتا ہے:، یعنی۔ اس فارمولے کو استعمال کرتے ہوئے تکراری اقدار کا حساب لگایا جا سکتا ہے، جو موبیئس الٹ فارمولے کے مساوی ہے۔ یہ جانچنا کہ آیا x یونٹی ماڈیولو n کا ایک ابتدائی kth جڑ ہے۔ فاسٹ ایکسپونٹیشن کے ذریعے، کوئی اس کی جانچ کر سکتا ہے۔ اگر یہ سچ ہے، تو x یونٹی ماڈیولو n کا kth روٹ ہے لیکن ضروری نہیں کہ ابتدائی ہو۔ اگر یہ ابتدائی جڑ نہیں ہے، تو اس کے ساتھ k کا کچھ تقسیم کنندہ l ہوگا۔ اس امکان کو خارج کرنے کے لیے، کسی کو صرف چند l کے برابر k کو پرائم سے تقسیم کرنے کی جانچ کرنی ہوگی۔ یعنی، جس چیز کی جانچ پڑتال کرنے کی ضرورت ہے وہ یہ ہے کہ: اتحاد ماڈیولو این کی ایک قدیم kth جڑ تلاش کرنا اتحاد کی قدیم kth جڑوں میں، قدیم th جڑیں زیادہ کثرت سے پائی جاتی ہیں۔ اس طرح کچھ انٹیجرز کو ابتدائی th جڑ ہونے کے لیے آزمانے کی سفارش کی جاتی ہے، جو جلدی کامیاب ہو جائے گا۔ ابتدائی th جڑ x کے لیے، نمبر اتحاد کا ابتدائی th جڑ ہے۔ اگر k تقسیم نہیں کرتا ہے، تو اتحاد کی کوئی kth جڑیں نہیں ہوں گی۔ ایک سے زیادہ ابتدائی kth جڑ ماڈیولو n تلاش کرنا ایک بار اتحاد x کا ایک قدیم kth جڑ حاصل ہونے کے بعد، ہر طاقت اتحاد کی ایک th جڑ ہے، لیکن ضروری نہیں کہ ایک قدیم جڑ ہو۔ طاقت اتحاد کی ایک ابتدائی جڑ ہے اگر اور صرف اس صورت میں جب وہ مشترکہ ہو۔ ثبوت مندرجہ ذیل ہے: اگر ابتدائی نہیں ہے، تو ساتھ کا ایک تقسیم کنندہ موجود ہے، اور چونکہ اور کوپرائم ہیں، اس لیے ماڈیولو کا الٹا موجود ہے۔ یہ پیداوار، جس کا مطلب ہے کہ یہ اتحاد کی ابتدائی جڑ نہیں ہے کیونکہ اس میں چھوٹا ایکسپونینٹ ہے۔ یعنی، ایکس کو ایکسپونینٹیٹ کرکے کوئی بھی اتحاد کی مختلف ابتدائی kth جڑیں حاصل کر سکتا ہے، لیکن یہ ایسی تمام جڑیں نہیں ہو سکتی ہیں۔ تاہم، ان سب کو تلاش کرنا اتنا آسان نہیں ہے۔ یونٹی ماڈیولو n کے ابتدائی kth جڑ کے ساتھ n تلاش کرنا انٹیجر ریسیڈیو کلاس کے کس حلقے میں یونٹی کا ابتدائی kth جڑ موجود ہے؟ اس کا استعمال جہتی عدد ویکٹر کے مجرد فورئیر ٹرانسفارم (زیادہ واضح طور پر ایک عدد نظریاتی ٹرانسفارم) کا حساب لگانے کے لیے کیا جا سکتا ہے۔ الٹا تبدیلی انجام دینے کے لیے، تقسیم کریں ؛ یعنی، k بھی ایک یونٹ ماڈیولو ہے۔ اس طرح کے n کو تلاش کرنے کا ایک آسان طریقہ یہ ہے کہ ریاضی کی ترقی میں ماڈیولی کے حوالے سے ابتدائی kth جڑوں کی جانچ کی جائے۔ یہ تمام ماڈیولی k کے لیے کوپرائم ہیں اور اس طرح k ایک یونٹ ہے۔ ریاضی کی ترقی پر ڈیرچلیٹ کے نظریہ کے مطابق ترقی میں لامحدود طور پر بہت سے پرائم ہوتے ہیں، اور ایک پرائم کے لیے، یہ برقرار رہتا ہے۔ اس طرح اگر پرائم ہے، تو، اور اس طرح اتحاد کی ابتدائی kth جڑیں ہیں۔ لیکن پرائمز کے لیے ٹیسٹ بہت مضبوط ہے، اور دیگر مناسب ماڈیولی بھی ہو سکتے ہیں۔ یونٹی ماڈیولو n کی متعدد ابتدائی جڑوں کے ساتھ ایک n تلاش کرنا ایک ماڈیولس کو تلاش کرنے کے لیے کہ یونٹی ماڈیولو کی ابتدائی جڑیں موجود ہیں، مندرجہ ذیل تھیوریم مسئلے کو آسان بنا دیتا ہے: اس لیے کہ یونٹی ماڈیولو کی ابتدائی جڑیں صرف اس صورت میں ہیں جب یونٹی ماڈیولو n کی ایک قدیم th جڑ موجود ہو۔ پیچھے کی سمت کا ثبوت: اگر یونٹی ماڈیولو کی ایک قدیم th جڑ ہے جسے یونٹی ماڈیولو کہا جاتا ہے، تو یہ یونٹی ماڈیولو کا th جڑ ہے۔ آگے کی سمت: اگر یونٹی ماڈیولو کی ابتدائی جڑیں ہیں، تو تمام متغیرات کے تقسیم کار ہیں۔ اس کا مطلب ہے اور اس کے نتیجے میں اس کا مطلب ہے کہ یونٹی ماڈیولو کی ایک ابتدائی جڑ ہے۔ حوالہ جات ماڈیولر ریاضی