هم‌نهشتی (نظریه اعداد)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

نظریه همنهشتی یا حساب پیمانه‌ای سیستمی برای محاسبه با اعداد صحیح است که به‌وسیله کارل فردریش گاوس در کتاب رساله حساب در سال ۱۸۰۱ معرفی شد.

مفهوم همنهشتی را می‌توان به عنوان پالایشی برای نظریه بخش پذیری دانست و به‌وسیله آن می‌توان مفاهیم بنیادی را در نظریه اعداد مورد مطالعه قرار داد که بدون استفاده از آن بیان و اثبات بسیاری از مطالب در نظریه اعداد دشوار و یا غیر ممکن خواهد بود. بعلاوه همنهشتی‌ها می‌توانند خیلی شبیه به معادلات مورد بحث قرار بگیرند و از این رو رابطه‌ای شبیه به تساوی ایجاد خواهند کرد.

به همین دلیل گاوس نماد \equiv را برای همنهشتی معرفی نمود. یکی از کاربردهای مهم همنهشتی‌ها در حل معادلات سیاله است. مفهوم همنهشتی در موارد بسیاری در زندگی ما مشهود است. یکی از کاربردهای آشنا همنهشتی‌ها در زندگی روزمره استفاده از ۲۴ ساعت در شبانه روز است. به طور کلی هر پدیده‌ای که به صورت دوره‌ای رخ می‌دهد بیانگر کاربردی از همنهشتی است.

تعریف[ویرایش]

  • قرار داد: از این پس حروف m و n بیانگر اعداد طبیعی و حروف ...,a,b,c بیانگر اعداد صحیح خواهند بود مگر آنکه خلاف آن صریحاً تصریح شود.

گوییم عدد a به هنگ(پیمانه یا سنج) m با b همنهشت است و می‌نویسیم

a\equiv b\pmod{m} هرگاه ‎m|(a-b)

از آنجا که با توجه به این تعریف هر دو عدد طبیعی به هنگ m=1 با هم همنهشت می‌باشند، هنگ را معمولاً عدد طبیعی بزرگ‌تر از یک در نظر می‌گیریم. بعلاوه برای سهولت در نوشتار گاهی نماد a\equiv_{m} b را برای نمایش همنهشتی به هنگ m استفاده می‌کنیم.

اگر a و b به هنگ m همنهشت نباشد می‌نویسیم a\not \equiv b \pmod{m}

به عنوان مثال 28 \equiv 14 \pmod{14} چرا که 14|28-14 ولی 28\not \equiv 12 \pmod{14}.

همنهشتی به عنوان یک رابطه[ویرایش]

همنهشتی به هنگ دلخواه m یک رابطه را روی مجموعه اعداد صحیح تعریف می‌کند. این رابطه را به صورت \equiv_{m} نشان می‌دهیم و برای هر دو عدد صحیح a,b به صورت:

a\equiv_m b\iff m|(a-b)

تعریف می‌کنیم.

با کمی دقت متوجه می شویم این رابطه یک رابطه هم ارزی روی مجموعه اعداد صحیح است.

قضیه1
رابطه همنهشتی به هنگ m روی مجموعه اعداد صحیح یک رابطه هم‌ارزی است.
برهان 1
  1. برای هر عدد صحیح a داریم m|a-a پس a\equiv_m a ولذا رابطه \equiv_{m} منعکس است.
  2. برای هر دو عدد صحیح a,b اگر a\equiv_m b آنگاه بنابه تعریف m|a-b پس m|b-a و در نتیجه b\equiv_m a و لذا رابطه \equiv_{m} متقارن است.
  3. برای هر سه عدد صحیح a,b,c اگر a\equiv_m b و b\equiv_m c آنگاه m|a-b و m|b-c حال با توجه به خواص رابطه عاد کردن می‌توان نوشت m|a-c پس a\equiv_m c و لذا رابطه \equiv_{m} متعدی است.

از 1و2و3 نتیجه می‌شود رابطه \equiv_{m} یک رابطه هم ارزی روی اعداد صحیح تعریف می‌کند و برهان تمام است.

حال که رابطه \equiv_{m} یک رابطه هم‌ارزی روی اعداد صحیح تعریف می‌کند، طبیعی است که به دنبال کلاس‌های هم ارزی آن باشیم. در این راه به خاصیت جالبی از رابطه \equiv_{m} پی خواهیم برد.

اگر برای هر عدد صحیح a کلاس هم‌ارزی a به هنگ m را با نماد \bar{a} نشان دهیم، داریم:

\bar{a}=\{b\in \mathbb{Z}: b\equiv_m a\}

پس

\bar{a}=\{b\in \mathbb{Z}: m|(b-a)\}

ولذا

\bar{a}=\{b\in \mathbb{Z}: b-a=mk,k\in \mathbb{Z}\}

در نتیجه

\bar{a}=\{a+mk:k\in \mathbb{Z}\}

برطبق قوانین حاکم بر کلاس‌های هم ارزی برای هر دو عدد صحیح a,b داریم \bar{a}=\bar{b} اگر و فقط اگر a\equiv_m b

همانند همه روابط هم‌ارزی، رابطه هم ارزی \equiv_{m} مجموعه اعداد صحیح را به کلاس‌های هم‌ارزی خود افراز می‌کند.

با کمی دقت در کلاس‌های هم‌ارزی این رابطه به سادگی می‌توان نشان داد که رابطه \equiv_{m} مجموعه اعداد صحیح را به دقیقاً m کلاس هم‌ارزی افراز می‌کند. مجموعه خارج قسمت(مجموعه همه کلاس‌ها هم‌ارزی) رابطه هم‌ارزی به پیمانه \equiv_{m} را با \mathbb{Z}_m نشان می دهیم و آن را مجموعه اعداد صحیح به هنگ m می نامیم.

این مجموعه را بنابر مطلب قبل می‌توان به صورت \mathbb{Z}_m=\{\bar{0},\bar{1},\bar{2},...,\overline{m-1}\} نشان داد.

وضوحاً هر عدد صحیح با یکی از اعضای \mathbb{Z}_m به هنگ m همنهشت است.

حلقه اعداد صحیح به هنگ[ویرایش]

دیدیم که رابطه همنهشتی به هنگ m مجموعه اعداد صحیح را به m کلاس هم ارزی افراز می‌کند و مجموعه خارج قسمت آن مجموعه اعداد صحیح به هنگ m است که به صورت زیر تعریف می‌شود:

\mathbb{Z}_m=\{\bar{0},\bar{1},\bar{2},...,\overline{m-1}\}

اعمال ⊕,⊗ روی \mathbb{Z}_m برای هر \bar{a},\bar{b}\in \mathbb{Z}_m به صورت زیر تعریف می‌شود.

  • \bar{a}\oplus \bar{b}=\overline{a+b}
  • \bar{a}\otimes \bar{b}=\overline{a.b}

به سادگی می‌توان تحقیق نمود که \mathbb{Z}_m به همراه این اعمال تشکیل یک حلقه جابجایی یکدار را می‌دهد. این بحث در همنهشتی‌های جبری بسیار اهمیت دارد.

خواص همنهشتی‌ها[ویرایش]

قضیه2
طرفین دو رابطه همنهشتی به یک هنگ را می‌توان باهم جمع یا در هم ضرب کرد. به عبارت دیگر اگر a\equiv_m b و c\equiv_m d آنگاه:
  1. a+c\equiv_m b+d
  2. a.c\equiv_m b.d
برهان2

به عنوان نمونه مورد 1 را اثبات می‌کنیم. چون بنابه فرض a\equiv_m b پس m|a-b و چون c\equiv_m d

پس m|c-d بنابر خوص رابطه عاد کردن داریم (m|(a-b)+(c-d پس (m|(a+c)-(b+d ولذا a+c\equiv_m b+d

مورد 2 نیز به طریق مشابه اثبات می‌شود.

قضیه فوق را می‌توان به بیش از دو رابطه همنهشتی نیز تعمیم داد. به عبارت دیگر به سادگی به استقرا ثابت می‌شود اگر برای هر i=1,2,3,..,n a_i\equiv_m b_i آنگاه:

  • \sum_{i=1}^n a_i\equiv_m \sum_{i=1}^n b_i
  • \prod_{i=1}^n a_i\equiv_m \prod_{i=1}^n b_i
قضیه 3
طرفین یک رابطه همنهشتی را می‌توان در عددی ثابت ضرب کرد. به عبارت دیگر اگر a\equiv_m b و c عددی صحیح ثابتی باشد باشد داریم a.c\equiv_m b.c.
برهان3
چون بنابه فرض a\equiv_m b پس m|a-b ولذا (m|c(a-b درنتیجه m|ac-bc ولذا ac\equiv_m bc

دو قضیه اخیر به خوبی شباهت میان رابطه همنهشتی را با رابطه تساوی را نشان می‌دهد. اما این دو رابطه در برخی موارد دارای تفاوت می‌باشد.

به عنوان مثال می دانیم که دو طرف یک رابطه تساوی را می‌توان بر عددی صحیح ناصفر تقسیم نمود. اما آیا این خاصیت در مورد رابطه همنهشتی به هنگ دلخواه m صادق است؟

قضیه زیر بیان می‌کند در تقسیم طرفین یک رابطه همنهشتی بر یک عامل مشترک طرفین هنگ دچار تغییر می‌شود.

قضیه 4
فرض کنید c عددی صحیح ناصفر باشد و (d=(c,m در این صورت اگر
ac\equiv bc \pmod{m}

آنگاه

a\equiv b \pmod{\frac{m}{d}}
برهان4
چون ac\equiv bc \pmod{m} پس m|a-b بنابراین
\frac{m}{d}|(a-b)\frac{c}{d}

اما چون (d=(c,m پس (\frac{m}{d},\frac{c}{d})=1 و در نتیجه بنابر لم اقلیدس \frac{m}{d}|a-b پس

a\equiv b \pmod{\frac{m}{d}}

پس اگر c عددی صحیح ناصفر باشد که (m,c)=1، اگر ac\equiv bc \pmod{m} آنگاه a\equiv b \pmod{m}

همانطور که اشاره شد رابطه نزدیکی میان رابطه همنهشتی و نظریه بخش پذیری وجود دارد. در حقیقت نظریه همنهشتی را می‌توان به عنوان پالایشی برای نظریه بخش پذیری دانست. قضایای زیر به خوبی این رابطه را نشان می‌دهد.

قضیه5
اگر r باقی‌مانده تقسیم عدد a بر m باشد آنگاه a\equiv_m r
برهان5
بنابر قضیه تقسیم عدد صحیح q وجود دارد که a=mq+r پس a-r=mq و لذا m|a-r پس a\equiv_m r.
قضیه6
a\equiv_m b اگر و فقط اگر باقی‌مانده تقسیم a و b بر m برابر باشد.
برهان6
ابتدا فرض می‌کنیم a\equiv_m b و نشان می دهیم باقی‌مانده تقسیم a و b بر m برابر است.

چون a\equiv_m b پس m|a-b ولذا به ازای عدد صحیح q داریم(1) a=b+mq. باقی‌مانده تقسیم b بر m را r می‌نامیم. بنابر قضیه تقسیم عدد صحیح k موجود است که (2) b=mk+r.

از (1) و (2) داریم

a=(mk+r)+mq=m(k+q)+r, 0\le r<m

پس باقی‌مانده تقسیم a برm برابر r است.

حال فرض می‌کنیم باقی‌مانده تقسیم a و b بر m برابر r باشد. در این صورت بنابر قضیه تقسیم اعداد صحیح k و q وجود داردند که a=mq+r و b=mk+r پس (a-b=m(q-k ولذا m|a-b پس a\equiv_m b

دستگاه کامل مانده‌ها به هنگ[ویرایش]

دستگاه‌های کامل مانده‌ها در نظریه همنهشتی بویژه در حل معادلات همنهشتی نقش اساسی دارند. به عبارت دقیق‌تر در نهایت برای حل یک معادله همنهشتی کافی است جواب‌ها را در میان اعضای یک دستگاه کامل مانده‌ها به هنگ همنهشتی مورد نظر جستجو کنیم.

در تعریف زیر سه شرط را برای دستگاه کامل مانده‌ها به هنگ دلخواه m بیان می‌کنیم ولی به سادگی می‌توان تحقیق کرد هر یک از دو شرط زیر دیگری را نتیجه می‌دهد. لذا در متون مختلف ممکن است هر یک از این دو شرط را به عنوان تعریف ذکر کنند.

تعریف
مجموعه A از اعداد صحیح را یک دستگاه کامل مانده‌ها(د.ک.م یا دسکم) به هنگ m می‌گوییم هرگاه واجد شرایط زیر باشد:
  1. A دارای m عضو متمایز چون a1,a2,a3,...,am باشد.
  2. اعضای A دو به دو به هنگ m ناهمنهشت باشند.
  3. هر عدد صحیح با یک و فقط یک عضو A به هنگ m همنهشت باشد.

ساده‌ترین دستگاه کامل مانده‌ها به هنگ m مجموعه {A={1,2,3,...,m-1 است. در حقیقت قضیه زیر را داریم:

قضیه7
مجموعه {A={1,2,3,...,m-1 یک دستگاه کامل مانده‌ها به هنگ m است.

دستگاه مخفف مانده‌ها به هنگ[ویرایش]

مجموعه A از اعداد صحیح را یک دستگاه مخفف مانده ها(د.م.م یا دمم) به هنگ m می گوییم هرگاه واجد شرایط زیر باشد:

  1. A دارای \phi (m) عضو متمایز باشد. که در آن \phi همان تابع فی اویلر است.
  2. اعضای A نسبت به m اول باشند و دو به دو به هنگ m ناهمنهشت باشند.
  3. هر عدد صحیح که نسبت به هنگ m اول است با یک و فقط یکی از اعضای A به هنگ m همنهشت باشد.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • ویلیام دبلیو. آدامز، لری جوئل گولدشتین. آشنایی با نظریه اعداد. ترجمهٔ دکتر آدینه محمد نارنجانی. تهران: مرکز نشر دانشگاهی، ۱۳۸۴. ISBN 964-01-0070-6. 
  • مشارکت‌کنندگان ویکی‌پدیا، «Modular arithmetic»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۴ اوت ۲۰۰۷).