فهرست مندرجات

همنهشتی

گوییم عدد 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$