Processing math: 0%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:همنهشتی

همنهشتی

گوییم عدد a به هنگ (پیمانه یا سنج) m با b همنهشت است و می‌نویسیم a \equiv b \pmod {m} هرگاه m \mid (a - b)

برای سهولت در نوشتار گاهی نماد a\equiv_{m} b را برای نمایش همنهشتی به هنگ m استفاده می‌کنیم.

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

قضیه۱

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

برهان ۱

برای هر عدد صحیح a داریم m|a-a پس a\equiv_m a ولذا رابطه \equiv_{m} منعکس است.

برای هر دو عدد صحیح a,b اگر a\equiv_m b آنگاه بنابه تعریف m|a-b پس m|b-a و در نتیجه b\equiv_m a و لذا رابطه \equiv_{m} متقارن است.

برای هر سه عدد صحیح 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} متعدی است.

از ۱و۲و۳ نتیجه می‌شود رابطه \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 همنهشت است.

قضیه۲

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

برهان۲

به عنوان نمونه مورد ۱ را اثبات می‌کنیم. چون بنابه فرض 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 مورد ۲ نیز به طریق مشابه اثبات می‌شود.

قضیه ۳

طرفین یک رابطه همنهشتی را می‌توان در عددی ثابت ضرب کرد. به عبارت دیگر اگر a\equiv_m b و c عددی صحیح ثابتی باشد باشد داریم a.c\equiv_m b.c.

برهان۳

چون بنابه فرض a\equiv_m b پس m|a-b ولذا m|c(a - b) درنتیجه m|ac-bc ولذا ac\equiv_m bc

قضیه ۴

فرض کنید c عددی صحیح ناصفر باشد و d = (c, m) در این صورت اگر

ac\equiv bc \pmod{m}

آنگاه

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

برهان۴

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

\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}

قضیه۵

اگر r باقی‌مانده تقسیم عدد a بر m باشد آنگاه a\equiv_m r

برهان۵

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

قضیه6

a\equiv_m b اگر و فقط اگر باقی‌مانده تقسیم a و b بر m برابر باشد.

برهان۶

ابتدا فرض می‌کنیم 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. از (۱) و (۲) داریم

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


ابزار صفحه