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

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

گوئیم عدد ${\displaystyle a}$

${\displaystyle a\equiv b(\mathrm{mod}m)}$

هرگاه ‎${\displaystyle m|(a-b)}$

‎

به بیان دیگر: ${\displaystyle a=(k.m)+b}$

که ${\displaystyle k\in \mathbb{Z}}$

از آنجا که با توجه به این تعریف هر دو عدد طبیعی به پیمانه ${\displaystyle m=1}$

اگر ${\displaystyle a}$

به عنوان مثال: ${\displaystyle 30\equiv 9(\mathrm{mod}7)}$

هم‌نهشتی به پیمانۀ دلخواه ${\displaystyle m}$

${\displaystyle a{\equiv }_{m}b⟺m|(a-b)}$

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

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

قضیۀ ۱

رابطۀ هم‌نهشتی به پیمانۀ ${\displaystyle m}$

روی مجموعۀ اعداد صحیح یک رابطۀ هم‌ارزی است.

برهان ۱

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

از ۱و۲و۳ نتیجه می‌شود رابطه ${\displaystyle {\equiv }_m}$

حال که رابطه ${\displaystyle {\equiv }_m}$

اگر برای هر عدد صحیح a کلاس هم‌ارزی a به پیمانه m را با نماد ${\displaystyle \overline{a}}$

${\displaystyle \overline{a}=\{b\in \mathbb{Z}:b{\equiv }_{m}a\}}$

پس

${\displaystyle \overline{a}=\{b\in \mathbb{Z}:m|(b-a)\}}$

ولذا

${\displaystyle \overline{a}=\{b\in \mathbb{Z}:b-a=mk,k\in \mathbb{Z}\}}$

در نتیجه

${\displaystyle \overline{a}=\{a+mk:k\in \mathbb{Z}\}}$

برطبق قوانین حاکم بر کلاس‌های هم‌ارزی برای هر دو عدد صحیح a,b داریم ${\displaystyle \overline{a}=\overline{b}}$

همانند همه روابط هم‌ارزی، رابطه هم‌ارزی ${\displaystyle {\equiv }_m}$

با کمی دقت در کلاس‌های هم‌ارزی این رابطه به سادگی می‌توان نشان داد که رابطه ${\displaystyle {\equiv }_m}$

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

وضوحاً هر عدد صحیح با یکی از اعضای ${\displaystyle {\mathbb{Z}}_m}$

حلقۀ اعداد صحیح به پیمانه

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

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

اعمال ⊕,⊗ روی ${\displaystyle {\mathbb{Z}}_m}$

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

به سادگی می‌توان تحقیق نمود که ${\displaystyle {\mathbb{Z}}_m}$

قضیۀ ۲

طرفین دو رابطه همنهشتی به یک پیمانه را می‌توان باهم جمع یا در هم ضرب کرد. به عبارت دیگر اگر ${\displaystyle a{\equiv }_{m}b}$

و ${\displaystyle c{\equiv }_{m}d}$

آنگاه:

1. ${\displaystyle a+c{\equiv }_{m}b+d}$
2. ${\displaystyle a.c{\equiv }_{m}b.d}$

برهان۲

به عنوان نمونه مورد ۱ را اثبات می‌کنیم. چون بنابه فرض ${\displaystyle a{\equiv }_{m}b}$

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

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

قضیه فوق را می‌توان به بیش از دو رابطه همنهشتی نیز تعمیم داد. به عبارت دیگر به سادگی به استقراء ثابت می‌شود اگر برای هر i=1,2,3,.. ,n ${\displaystyle a_i{\equiv }_m{b}_i}$

• ${\displaystyle \sum _{i=1}^n{a}_i{\equiv }_m\sum _{i=1}^n{b}_i}$
• ${\displaystyle \prod _{i=1}^n{a}_i{\equiv }_m\prod _{i=1}^n{b}_i}$

قضیۀ ۳

طرفین یک رابطه همنهشتی را می‌توان در عددی ثابت ضرب کرد. به عبارت دیگر اگر ${\displaystyle a{\equiv }_{m}b}$

و c عددی صحیح ثابتی باشد باشد داریم ${\displaystyle a.c{\equiv }_{m}b.c}$

.

برهان ۳

چون بنابه فرض ${\displaystyle a{\equiv }_{m}b}$

پس m|a-b ولذا (m|c(a-b در نتیجه m|ac-bc ولذا ${\displaystyle ac{\equiv }_{m}bc}$

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

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

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

قضیۀ ۴

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

${\displaystyle ac\equiv bc(\mathrm{mod}m)}$

آنگاه

${\displaystyle a\equiv b(\mathrm{mod}\frac{m}{d})}$

برهان ۴

چون ${\displaystyle ac\equiv bc(\mathrm{mod}m)}$

پس m|a-b بنابراین

${\displaystyle \frac{m}{d}|(a-b)\frac{c}{d}}$

اما چون (d=(c,m پس ${\displaystyle (\frac{m}{d},\frac{c}{d})=1}$

${\displaystyle a\equiv b(\mathrm{mod}\frac{m}{d})}$

پس اگر c عددی صحیح ناصفر باشد که ${\displaystyle (m,c)=1}$

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

قضیۀ ۵

اگر r باقی‌مانده تقسیم عدد a بر m باشد آنگاه ${\displaystyle a{\equiv }_{m}r}$

برهان ۵

بنابر قضیه تقسیم عدد صحیح q وجود دارد که a=mq+r پس a-r=mq و لذا m|a-r پس ${\displaystyle a{\equiv }_{m}r}$

.

قضیۀ 6

${\displaystyle a{\equiv }_{m}b}$

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

برهان ۶

ابتدا فرض می‌کنیم ${\displaystyle a{\equiv }_{m}b}$

و نشان می‌دهیم باقی‌مانده تقسیم a و b بر m برابر است.

چون ${\displaystyle a{\equiv }_{m}b}$

از (۱) و (۲) داریم

پس باقی‌ماندۀ تقسیم ${\displaystyle a}$

حال فرض می‌کنیم باقی‌ماندۀ تقسیم ${\displaystyle a}$

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

در تعریف زیر سه شرط را برای دستگاه کامل مانده‌ها به پیمانۀ دلخواه ${\displaystyle m}$

تعریف

مجموعۀ ${\displaystyle A}$

از اعداد صحیح را یک دستگاه کامل مانده‌ها (د. ک. م یا دسکم) به پیمانۀ ${\displaystyle m}$

می‌گوئیم هرگاه واجد شرایط زیر باشد:

1. ${\displaystyle A}$
   دارای ${\displaystyle m}$
   -عضو متمایز چون ${\displaystyle a_1,a_2,a_3,...,a_m}$
   باشد.
2. اعضای ${\displaystyle A}$
   دو به دو به پیمانۀ ${\displaystyle m}$
   ناهم‌نهشت باشند.
3. هر عدد صحیح با یک و فقط یک عضو ${\displaystyle A}$
   به پیمانۀ ${\displaystyle m}$
   هم‌نهشت باشد.

ساده‌ترین دستگاه کامل مانده‌ها به پیمانۀ ${\displaystyle m}$

قضیۀ ۷

مجموعۀ ${\displaystyle A=\{0,1,2,3,...,m-1\}}$

، یک دستگاه کامل مانده‌ها به پیمانۀ ${\displaystyle m}$

است.

مجموعۀ ${\displaystyle A}$

1. ${\displaystyle A}$
   دارای ${\displaystyle \varphi (m)}$
   عضو متمایز باشد؛ که در آن ${\displaystyle \varphi }$
   همان تابع فی اویلر است.
2. اعضای ${\displaystyle A}$
   نسبت به ${\displaystyle m}$
   اول باشند و دو به دو به پیمانۀ ${\displaystyle m}$
   ناهم‌نهشت باشند.
3. هر عدد صحیح که نسبت به پیمانۀ ${\displaystyle m}$
   اول است، با یک و فقط یکی از اعضای ${\displaystyle A}$
   به پیمانۀ ${\displaystyle m}$
   هم‌نهشت باشد.

• معادلات هم‌نهشتی
• هم‌نهشتی‌های جبری
• قضیۀ اویلر
• قضیۀ کوچک فرما
• مرتبه
• قضیۀ ویلسون
• قضیۀ باقی‌ماندۀ چینی

• ویلیام دبلیو. آدامز، لری جوئل گولدشتین (۱۳۸۴)، آشنایی با نظریه اعداد، ترجمهٔ دکتر آدینه محمد نارنجانی، تهران: مرکز نشر دانشگاهی، شابک ۹۶۴-۰۱-۰۰۷۰-۶
• تام آپوستل (۱۳۷۶)، نظریه تحلیلی اعداد (۱)، ترجمهٔ دکتر علی‌اکبر عالم‌زاده-علی‌اکبر رحیم‌زاده، تهران: نشر منصوری، شابک ۹۶۴-۶۱۶۶-۰۶-۷