قضایای همنهشتی در اعداد صحیح — به زبان ساده

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

برای درک بهتر مطالب این نوشتار بهتر است مطالب همنهشتی — به زبان ساده و نظریه اعداد و کاربردهای آن — به زبان ساده را بخوانید. همچنین خواندن نوشتارهای اعداد صحیح — به زبان ساده و قواعد بخش پذیری یا عاد کردن — به زبان ساده نیز خالی از لطف نیست.

قضایای همنهشتی در اعداد صحیح

همنهشتی یا هم باقی‌مانده بودن نسبت به یک عدد (پیمانه) خاصیت جالبی است که در ریاضیات جدید (ریاضیات گسسته) کاربردهای فراوانی دارد. همانطور که از نام این اصطلاح ریاضی مشخص است، قضایای همنهشتی مرتبط با تقسیم عدد صحیح و باقی‌مانده حاصل تقسیم است. به این ترتیب برای یادآوری، ابتدا نحوه تقسیم عدد صحیح و خواص آن را مرور می‌کنیم.

تقسیم عدد صحیح و عاد کردن

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

$$ \large a = b \times c + d $$

در این حالت $$  d$$ را باقی‌مانده تقسیم $$ a $$ بر $$ b $$ می‌نامیم. به این ترتیب می‌توان نوشت:

$$ \large a \div b = c + \dfrac { d } { b } , \;\; d \geq 0, \;\; b \neq 0 $$

البته شرط نامنفی بودن باقی‌مانده $$ d $$ و مخالف صفر بودن $$ b $$ نیز باید در نظر گرفته شوند. از این خصوصیت استفاده کرده و رابطه عاد کردن یا شمارش کردن بین دو عدد را تعریف می‌کنند.

تعریف عاد کردن یا شمارش کردن دو عدد صحیح

دو عدد صحیح $$ a $$ و $$ b $$ را در نظر بگیرید. اگر خارج قسمت حاصل از تقسیم $$ a $$ بر $$ b $$ یک عدد صحیح بوده و باقی‌مانده این تقسیم صفر باشد، می‌گوییم $$ b $$، عدد $$ a $$ را عاد می‌کند یا می‌شمارد. این خاصیت بین $$ a $$ و $$ b $$ را با نماد ریاضی به صورت زیر نشان می‌دهیم:

$$ \large b \;|\; a $$

و می‌خوانیم $$ b $$ عدد $$ a $$ را عاد می‌کند یا می‌شمارد. وجود رابطه عاد یا شمارش کردن، ما را به سمت تعریف همنهشتی و خواص آن هدایت می‌کند.

تعریف همنهشتی

برای روشن شدن قضایای همنهشتی و مفاهیم مرتبط با آن، ابتدا با یک مثال آغاز می‌کنیم. البته توجه داشته باشید گاهی همنهشتی را به صورت هم‌‌نهشتی نیز می‌نویسند.

مثال ۱

دو عدد ۱۵ و ۲۰ را در نظر بگیرید. تقسیم این دو عدد بر ۵ دارای باقی‌مانده صفر است.

$$ \large 15 \div 5 = 3,  \; \; 3 \times 5 + 0 = 15 $$

$$ \large 20 \div 5 = 4 , \ ;\; 4 \times 5 + 0 = 20 $$

همانطور که می‌بینید باقی‌مانده تقسیم این دو عدد بر ۵ با یکدیگر برابر است. در این صورت می‌گوییم این ۱۵ و ۲۰ به پیمانه ۵، همنهشت یا هم‌باقی‌مانده هستند. به این ترتیب به صورت رسمی همنهشتی دو عدد صحیح را به صورت زیر تعریف می‌کنیم.

تعریف همنهشتی: عدد مثبت و صحیح $$ m $$ را در نظر بگیرید. دو عدد $$ a $$ و $$ b $$ را به پیمانه $$ m $$، همنهشت (هم‌باقی‌مانده) می‌گویند هرگاه  $$ m \;| \;  ( a - b ) $$.

با نماد «|» که بیانگر عاد کردن است، در قسمت قبل آشنا شده‌اید. پس می‌توان گفت که دو عدد $$ a $$ و $$ b $$ به پیمانه $$ m $$ همنهشت هستند اگر $$ m $$ تفاصل آن‌ها را عاد کرده یا بشمارد. به این معنی که تقسیم تفاضل $$ a $$ و $$ b $$ بر $$m$$ باقی‌مانده‌ای برابر با صفر داشته باشد.

معمولا برای نشان دادن خاصیت همنهشتی بین دو عدد $$ a $$ و $$ b $$ به پیمانه $$ m $$‌ از نماد زیر استفاده می‌کنیم.

$$\large a \equiv b\;(\text{mod } m ) $$

که منظور از mod، عملگر باقی‌مانده تقسیم است. پس مشخص می‌شود که $$ a $$ و $$ b $$ اگر به $$ m $$ تقسیم شوند، باقی‌مانده (mod) یکسانی دارند. این موضوع را به صورت یک گزاره دو شرطی بنا می‌نهیم.

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

مثال ۲ 

برای نشان دادن همنهشتی دو عدد ۱۴ و 17 به پیمانه ۳ باید رابطه زیر برقرار باشد.

$$ \large \mod (14 , 3 ) = 2 , \; \; \; \mod ( 17 , 3 ) = 2 $$

به این ترتیب مشخص است که تقسیم ۱۴ بر ۳ دارای باقی‌مانده برابر با ۲ و از طرفی ۲ نیز باقی‌مانده تقسیم ۱۷ بر ۳ است. پس ۱۷ و ۱۴ به پیمانه ۳، همنهشت هستند و می‌نویسیم.

$$ \large 17 \equiv 14 \; (\text{mod } 3 ) $$

از طرفی مشخص است که رابطه زیر را هم برای این دو عدد با توجه به همنهشتی می‌توان نوشت:

$$ \large 17 -14 = 3 ,\;\; 3\; | \; 17 - 14 \; \; 3\; |\; 3 $$

رابطه آخر هم نشان می‌دهد که تقسیم تفاضل ۱۷ و ۱۴ بر ۳ دارای باقی‌مانده‌ای برابر با صفر است.

$$ \large \dfrac{(17 - 14)}{3} = \dfrac{17}{3} - \dfrac{14}{3} = 5 \frac{2}{3}- 4 \frac{2}{3} =  1 + \frac{0}{3} $$

که تساوی آخر نیز نشان می‌دهد که باقی‌مانده تقسیم تفاضل دو عدد ۱۷ و ۱۴ بر ۳، باقی‌مانده‌ای برابر با صفر دارد. در ادامه به قضایای همنهشتی و مسائل مربوطه نظیر حل معادلات هم‌نهشتی خواهیم پرداخت.

رابطه هم‌ارزی و همنهشتی

همانطور که مشاهده می‌کنید رابطه هم‌نهشتی را با علامت هم‌ارزی ( $$ \equiv $$ ) به کار برده‌ایم. نشان می‌دهیم که رابطه همنهشتی، یک رابطه هم‌ارزی است. برای آشنایی بیشتر با تعریف رابطه و انواع آن نوشتار رابطه و تابع از نگاه مجموعه‌ ها — به زبان ساده را مطالعه کنید. ولی به هر حال این موضوع را هم متذکر می‌شویم که رابطه‌ای را هم‌ارزی می‌نامند اگر دارای بازتابی یا انعکاسی (reflexive property)، تقارنی (symmetric property)، ترایایی یا تعدی (transitive property) باشد.

قضیه ۱

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

خاصیت بازتابی:

$$ \large \forall a \in Z , \; \; a \equiv a\; (\text{ mod } m )  $$

خاصیت تقارنی:

$$ \large \forall a , b  \in Z , \; \; a \equiv b (\text{ mod } m ) \rightarrow b \equiv a \; ( \text{ mod } m )  $$

خاصیت ترایایی:

$$ \large \forall a , b , c \in Z , \; \; a \equiv b\; ( \text{ mod } m) \; \& \; b \equiv c\; ( \text{ mod } m ) \rightarrow a \equiv c\; ( \text{ mod } m ) $$

اثبات: این قضیه به راحتی به کمک تعریف تقسیم در اعداد صحیح و قضیه‌های بخش‌پذیری در اعداد صحیح اثبات می‌شود.

به این ترتیب مجموعه اعداد همنهشت با $$ a $$ به پیمانه $$ m $$ را به صورت یک کلاس هم‌ارزی و به صورت زیر نمایش می‌دهیم و آن را کلاس یا مجموعه مانده‌های شامل $$ a $$‌ می‌نامیم.

$$ \large [a]_m = \{ b \in Z , a \equiv b \; (\text{ mod } m ) \} $$

واضح است که مقادیر $$ b $$ همگی نسبت به $$ a $$ همنهشت به پیمانه $$ m $$ هستند.

نکته: گاهی به $$ [a]_m $$ کلاس همنهشتی $$ a $$ به پیمانه $$ m $$ نیز می‌گویند.

مثال 3

کلاس مانده‌های شامل ۵ به پیمانه 2 به صورت زیر خواهد بود.

$$ \large [5]_2 = \{ 5 , 7 , 9 , 11 , \ldots \} $$

زیرا اگر هر یک از اعضای یک مجموعه را بر ۲ تقسیم کنیم، باقی‌مانده‌ای برابر با ۱ خواهند داشت.

نکته: از آنجایی که هر عدد صحیح (مثل $$ a $$) با خودش به هر پیمانه‌ای همنهشت است، کلاس هم‌ارزی شامل خود آن عدد نیز خواهد بود. این موضوع را در قضیه مربوط به خاصیت هم‌ارزی رابطه همنهشتی نشان دادیم.

قضیه ۲

کلاس مانده‌های شامل $$ a $$ (کلاس همنهشتی) به صورت زیر مشخص می‌شود.

$$ \large [a]_m = \{ a + m q , \; q \in Z \} $$

اثبات: به کمک خواص تقسیم عدد صحیح و تعریف همنهشتی می‌توانیم بنویسیم:

$$ \large  a \equiv b \; (\text{ mod } m ) \longleftrightarrow \; \exists \; q \in Z , a - b = m q $$

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

$$ \large [a]_m = \{ a+mq , \; q \in Z \} $$

مثال ۴

مطابق با مثال ۳، مشخص است که کلاس مانده‌های شامل ۵ به پیمانه ۲ به صورت زیر در خواهد آمد.

$$ \large [5]_2 = \{ 5 + 2 q, \; q = \ldots , -1 , 0  , 1 , \ldots \} $$

قضیه ۳

کلاس‌ مانده‌ها (همنهشتی) دارای خواص زیر هستند.

• هر کلاس هم‌نهشتی، ناتهی است.
• شرط لازم و کافی برای آنکه $$ a \equiv b \; (\text{ mod } m)$$ باشد آن است که $$ [a]_m \cap [b]_m \neq \emptyset $$.
• اگر $$ [a]_m = [b]_m $$ باشد آنگاه $$ a \equiv b \; (\text{ mod } m) $$ و برعکس.
• کلاس‌های هم‌نهشتی به پیمانه $$m$$، مجموعه اعداد صحیح را افراز می‌کنند.
• تعداد کلاس‌های هم‌نهشتی به پیمانه $$ m $$، برابر با $$ m $$ است که به صورت زیر نوشته می‌شوند.

$$ \large [0]_m , [1]_m , \ldots , [m-1]_m $$

اثبات: قسمت‌های مختلف این قضیه یه کمک رابطه هم‌ارزی در هم‌نهشتی، اثبات می‌شوند. ولی در مورد آخر باید به این نکته نیز توجه داشت که حاصل تقسیم هر عدد صحیح بر $$ m $$ باقی‌مانده‌ای مثبت یا صفر و کوچکتر از $$ m $$ دارد.

پس هر عدد صحیح مانند $$ a $$ با یکی از اعداد $$ 0,1,\ldots,m-1 $$ هم‌نهشت است. به بیان ریاضی داریم:

$$ \large \forall a, \;\;\exists b\; ;  \; \; 0 \leq b \leq m-1 \; \& \; [a]_m =[b]_m $$

نکته: با توجه به اینکه موضوع بحث هم‌نهشتی، مجموعه اعداد صحیح است، مقادیر منفی نیز در این رابطه وجود دارند. ولی باید به مثبت بودن باقی‌مانده در عمل تقسیم عدد صحیح، توجه کرد. در نتیجه ممکن است به کمک مثال‌هایی نشان داد که:

$$ \large a \equiv b\; ( \text{ mod } m ) {\not {\rightarrow}} \;  a \equiv (-b)\; ( \text{ mod }m )$$

مثال 5

گزاره هم‌نهشتی زیر را در نظر بگیرید.

$$ \large 14 \equiv 17\; ( \text{ mod } 3 ) $$

این امر به این معنی است که باقی‌مانده تقسیم ۱۴ بر ۳ و باقی‌مانده تقسیم ۱۷ بر ۳، یکسان هستند. واضح است که باقی‌مانده هر یک از تقسیم‌ها برابر با ۲ است.

حال 17 را به 17- تبدیل می‌کنیم، دیگر باقی‌مانده تقسیم آن بر ۳، مقدار ۲ نخواهد بود، زیرا:

$$ \large 17 = -6 \times 3 + 1 $$

که نشان می‌دهد باقی‌مانده این تقسیم برابر با ۱ خواهد بود.

معادلات و گزاره‌های جبری هم‌نهشتی

براساس رابطه هم‌نهشتی می‌توان معادلات و روابط جبری بین گزاره‌های هم‌نهشتی ایجاد کرد. در ادامه به بعضی از آن‌ها اشاره می‌کنیم.\

جمع جبری گزاره‌های هم‌نهشتی

به کمک رابطه هم‌ارزی و تقسیم‌پذیری اعداد صحیح می‌توان نشان داد که دو طرف یک رابطه هم‌نهشتی را می‌توان با یکدیگر جمع کرد. فرض کنید  $$a \equiv b \; (\text{ mod }m) $$ و $$ c \equiv d  \;(\text{mod } m ) $$ آنگاه

$$ \large a + c \equiv b + d \; (\text{ mod } m ) $$

در حالت کلی‌تر نیز می‌توان نوشت:

$$ \large \forall  x , y ; \; \; \;a x + c y \equiv b x + d y \; (\text{ mod } m ) $$

که در آن $$ x , y $$ اعداد صحیح هستند.

مثال 6

همانطور که در مثال‌های قبل دیدید، $$14 \equiv 17 (\text{ mod } 3)$$ بود. همچنین $$18 \equiv 12 (\text{ mod } 3)$$ پس می‌توان گفت:

$$ \large 12 + 17 \equiv 14 + 18 \; (\text{ mod } 3) $$

به خوبی دیده می‌شود که با انجام حاصل‌جمع‌ها، رابطه هم‌نهشتی حفظ می‌شود. یعنی:

$$ \large 29 \equiv 32  \; ( \text{ mod } 3 ) $$

زیرا

$$ \large 29 \div 3 \rightarrow  9 \times 3 + 2 ,\; \; \; 32 \div 3 \rightarrow 10 \times 3 + 2 $$

نکته: از آنجایی که خاصیت هم‌نهشتی، یک رابطه هم‌ارزی است، می‌توان نتیجه گرفت:

$$ \large 12 + 14 \equiv 17 + 18 \; ( \text{ mod } 3) $$

یعنی

$$ \large 26 \equiv 35 \; ( \text{ mod } 3 ) $$

زیرا

$$ \large 26 \div 3 \rightarrow  8 \times 3 + 2 , \; \; \; 35 \div 3 \rightarrow 11 \times 3 + 2 $$

نکته: توجه داشته باشید که برای جمع رابطه‌های هم‌نهشتی باید پیمانه برای هر دو رابطه یکسان باشد در غیر اینصورت امکان جمع چنین رابطه‌های وجود نخواهد داشت.

ضرب گزاره‌های هم‌نهشتی

فرض کنید دو رابطه هم‌نهشتی به صورت $$ a \equiv b \;( \text{ mod } m) $$ و $$ c \equiv d \; (\text { mod } m ) $$ باشند. در این صورت می‌توان دو طرف این رابطه‌های هم‌نهشتی را در یکدیگر ضرب کرد.

$$ \large a c \equiv b d  \;(\text{ mod } m) $$

بررسی درستی این گزاره نیز به کمک روابط هم‌نهشتی و تقسیم‌پذیری صورت می‌پذیرد.

مثال 7

روابط هم‌نهشتی مربوط به مثال ۵ را در نظر بگیرید.

$$ \large 14 \equiv 17 \; (\text{ mod } 3) $$

$$ \large 18 \equiv 12  \; (\text{ mod } 3) $$

پس

$$ \large 18 \times 14 \equiv 17 \times 12 \; ( \text{ mod } 3 ) $$

یعنی

$$ \large 252 \equiv 204  \; ( \text{ mod } 3 ) $$

نکته: کلاس هم‌نهشتی ۱۷ به پیمانه ۳ یعنی $$[17]_3$$ با کلاس هم‌نهشتی ۱۸ به پیمانه ۳ یعنی $$[18]_3$$‌ تفاوت دارد ولی با توجه به قانون ضرب، عناصر این کلاس‌های هم‌نهشتی در ضرب روابط هم‌نهشتی صدق می‌کنند.

براساس قانون ضرب و جمع رابطه‌های هم‌نهشتی می‌توان عملیات زیر را روی رابطه‌های هم‌نهشتی به پیمانه $$m$$ انجام داد.

• دو طرف یک رابطه هم‌نهشتی به پیمانه $$m$$ را می‌توان با هم جمع کرد.
• دو طرف یک رابطه هم‌نهشتی به پیمانه $$m$$ را می‌توان در هم ضرب کرد.
• به دو طرف یک رابطه هم‌نهشتی می‌توان مقدار ثابتی را اضافه یا کم کرد.
• طرفین یک رابطه هم‌نهشتی را می‌توان در مقدار ثابتی ضرب کرد.

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

قضیه‌هایی که در ادامه دیده می‌شوند، مرتبط با هم‌نهشتی و بزرگترین مقسوم علیه مشترک (ب-م-م) و کوچکترین مضرب مشترک (ک-م-م) مقادیر و پیمانه‌ها هستند.

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

فرض کنید رابطه هم‌نهشتی زیر برای اعداد صحیح $$x,y,a , m$$ برقرار است.

$$ \large ax \equiv ay \; ( \text{ mod } m) $$

آنگاه

$$ \large x \equiv y \; ( \text{mod } \frac{m}{\gcd(a,m)} ) $$

در حالت خاص اگر $$\gcd(a,m)=1$$ یا بزرگترین مقسوم علیه مشترک $$a$$ و $$m$$ برابر با یک باشد، آنگاه

$$\large x \equiv y \; (\text{mod } m ) $$

نکته: دو عدد $$a$$ و $$b$$ را نسبت به یکدیگر هم‌اول گویند اگر بزرگترین مقسوم علیه مشترک آن‌ها مقدار ۱ باشد. برای مثال ۱۰ و ۹ هم‌اول هستند، زیرا تنها مقسوم علیه مشترک آن‌ها ۱ است در حالی که هیچکدام از آن‌ها اول نیستند.

کوچکترین مضرب مشترک در رابطه هم‌نهشتی

فرض کنید $$m_1$$ تا $$m_r$$ اعداد صحیح و مثبت باشند که در رابطه هم‌نهشتی زیر صدق می‌کنند.

$$ \large  \forall i, \; \; x \equiv y \; (\text{mod } m_i ) $$

آنگاه برای کوچکترین مضرب مشترک $$m_i$$ ها نیز که با $$ \text{lcm} (m_1 ,m_2 , \ldots , m_r ) $$ شناخته می‌شود رابطه هم‌نهشتی زیر برقرار است.

$$\large x \equiv y \; \Big( \text{mod} \; \; \text{lcm} (m_1 , m_2 , \ldots , m_r ) \Big) $$

البته عکس این قضیه نیز صحیح است یعنی اگر $$m$$ یک مضرب مشترک باشد، رابطه هم‌نهشتی برای $$x,y$$ برای همه عوامل $$m$$ نیز برقرار است.

اعداد متباین، مجموعه کامل و کامل تحویل یافته

در بحث اعداد اول و تجزیه به عوامل اول، که در نوشتار نظریه اعداد و کاربردهای آن — به زبان ساده مطرح شد، مشخص کردیم که هر عدد صحیح را می‌توان به صورت ضرب اعداد اول کوچکتر از خودش نوشت.

از طرفی عددی را اول (Prime) نامیدیم که به جز خودش و ۱، بر هیچ عددی بخش‌پذیر نیست. حال این مفهوم را برای دو عدد گسترش می‌دهیم.

اعداد متباین

دو عدد $$a$$ و $$b$$ را «متباین» (Coprime) یا «هم‌اول» گویند اگر بزرگترین مقسوم علیه مشترک آن‌ها فقط یک باشد. در این صورت خواهیم داشت:

$$ \large \gcd(a,b) = 1 $$

برای مثال ۱۰ و ۹ نسبت به یکدیگر متباین یا هم‌اول هستند. همانطور که می‌دانید الگوریتم‌های تقسیم به کمک تجزیه و بزرگترین مقسوم علیه مشترک بین دو عدد عمل می‌کنند. در نتیجه پیدا کردن اعداد متباین در محاسبات مربوط به تقسیم در رایانه‌ها، اهمیت زیادی دارد.

از مفاهیمی دیگری که در مورد هم‌نهشتی و قواعد و قضیه‌های آن به کار می‌رود، مجموعه‌های کامل و کامل تحویل یافته به پیمانه $$m$$ است.

مجموعه کامل به پیمانه $$m$$

فرض کنید که $$x_1,x_2,\ldots,x_m$$ صحیح باشند بطوری که رابطه هم‌نهشتی زیر برایشان صادق است.

$$ \large  \forall\; a \in Z \; \exists i ,\; a \; \equiv \; x_i  \; (\text{mod } m ) $$

آنگاه $$ x_1 , x_2 , \ldots , x_m $$ را کامل به پیمانه $$m$$ می‌نامند.

مثال ۸

مجموعه اعداد صحیح $$ 0 , 1, 2, \ldots , m-1 $$ را در نظر بگیرید. واضح است که تقسیم هر عدد صحیح به $$m$$ دارای باقی‌مانده‌ای از این مجموعه اعداد خواهد بود. مشخص است که برای هر $$m$$، مجموعه  $$\{ 0 , 1 , \ldots , m-1 \}$$ مجموعه بدیهی کامل به پیمانه $$m$$ است.

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

$$ \large [0]_m,  [1]_m , \ldots , [(m-1)]_m $$

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

فرض کنید $$ (x , m) $$ بزرگترین مقسوم علیه مشترک $$x$$ و $$m$$ باشد. همچنین بزرگترین مقسوم علیه مشترک $$y$$ و $$m$$‌ هم به شکل $$ (y , m ) $$ شناخته شود. در این صورت اگر رابطه هم‌نهشتی زیر برقرار باشد:

$$ \large x \equiv y \; (\text{mod } m ) $$

آنگاه

$$ \large ( x , m ) = ( y , m ) $$

به معنای آن است که بزرگترین مقسوم علیه مشترک بین $$x$$ و $$m$$ با بزرگترین مقسوم علیه مشترک بین $$y$$ و $$m$$ به شرط هم‌نهشت بودن $$x$$ و $$y$$ به پیمانه $$m$$، با هم برابر هستند.

مجموعه کامل تحویل یافته

مجموعه مقادیر  $$ x_1 , x_2 , \ldots , x_r $$ را در نظر بگیرد. اگر این مجموعه در شرایط زیر صدق کند، به آن مجموعه کامل تحویل یافته می‌گویند.

• $$x_i$$‌ها نسبت به $$m$$ اول باشند. در این حالت می‌گوییم، عدد ۱، بزرگترین مقسوم علیه مشترک بین $$x_i$$ و $$m$$ است. مشخص است که این دو عدد نسبت به یکدیگر، هم‌اول هستند. در این صورت می‌نویسیم:

$$ \large (x_i,m)=1 $$

• برای هر دو عدد متعلق به مجموعه کامل تحویل یافته مختلف، رابطه هم‌نهشتی به پیمانه $$m$$ برقرار نیست. به بیان ریاضی خواهیم داشت:

$$ \large x_i {\not\equiv} x_j (\text{mod } m) , \; \; i \neq j $$

• اگر $$a$$ و $$m$$ هم‌اول باشند آنگاه

$$ \large  \exists i , a \equiv x_i (\text{mod } m ) $$

به این معنی که هر عدد صحیح که نسبت به $$m$$، اول است، حداقل با یکی از اعضای مجموعه کامل تحویل یافته به پیمانه $$m$$ هم‌نهشت یا هم‌باقی‌مانده است.

نکته: اگر بخواهید مجموعه کامل تحویل یافته به پیمانه $$m$$‌ را مشخص کنیم، کافی است از اعضای هر یک کلاس‌های مانده زیر یکی را که نسبت به $$m$$‌ اول است انتخاب کنیم.

$$ \large [0]_m , [1]_m , \ldots , [(m-1)]_m $$

معادلات هم‌نهشتی

در ادامه در مورد معادلات هم‌نهشتی و جواب‌های آن بحث خواهیم کرد. ابتدا با چند قضیه موضوع را پی می‌گیریم.

اعداد متباین و قضیه اویلر

قبلا اعداد متباین را معرفی کردیم. در این قسمت به قضیه اویلر و ارتباط آن با اعداد متباین می‌پردازیم. فرض کنید تابع $$\varphi ( m ) $$ به صورت زیر تعریف شده است. در حقیقت این تابع، تعداد اعداد متباین با $$m$$ را می‌شمارد.

$$ \large \varphi ( m ) = | \{ a \in Z , 1 \leq a \leq m, \; \; \gcd(a,m) = 1 \} | $$

واضح است که این تابع از بین اعداد $$ 1 , 2 , \ldots m $$، آن‌هایی که نسبت به $$ m $$‌ اول هستند را شمارش می‌کند. تابع $$ \varphi ( m ) $$ را «تابع اویلر» (Euler Function) می‌نامند. همانطور که دیده می‌شود، در تابع اویلر اگر $$ m = p $$ باشد و یک عدد اول باشد، آنگاه $$ \varphi ( p ) = p - 1 $$. شکل رسمی قضیه اویلر به صورت زیر است.

قضیه اویلر

فرض کنید بزرگترین مقسوم علیه مشترک بین دو مقدار $$ a $$ و $$ m $$، همان یک باشد. به این معنی که $$ m $$ و $$ a $$ نسبت به یکدیگر متباین هستند.

$$ \large \gcd ( a , m ) = 1 $$

آنگاه اگر $$ a $$ به $$ \varphi(m ) $$ برسد، با ۱ به پیمانه $$ m $$ هم‌نهشت خواهد بود. به بیان ریاضی خواهیم داشت.

$$ \large a^{\varphi ( m )} \equiv 1 \; \;(\text{ mod } \; m ) $$

اثبات:

ابتدا فرض کنید که تعداد عناصر متباین با $$ m $$ برابر با $$ r $$ باشد.

$$ \large r = \varphi(m) $$

که به صورت $$ x_1 , x_2 , \ldots, x_r $$ نام‌گذاری شده‌اند. بدیهی است که این مجموعه از مقادیر $$ 1 , 2, \ldots , m $$ گرفته می‌شوند که در آن هر $$ x_i $$‌ نسبت به $$ m $$ متباین است.

در نتیجه $$ x_i $$ها تشکیل یک مجموعه کامل تحویل یافته به پیمانه $$ m $$ خواهند داد. از آنجایی که هر مضربی مثل $$ a $$ از آن‌ها که نسبت به $$m$$ متباین باشد، باز هم یک مجموعه تحویل یافته به پیمانه $$ m $$ است، خواهیم داشت:

$$ a x_1 , a x_2 , \ldots , a x_r $$ ها هم متباین نسبت به $$ m $$ هستند که در رابطه‌های زیر صدق می‌کنند.

$$ \large \forall i \; \; \exists\; j ,\; \; x_i \equiv a x_i \;( \text{mod } m ) $$

$$ \large \forall j \; \; \exists\; i ,\; \; x_i \equiv a x_j \;( \text{mod } m ) $$

با ضرب کردن دو طرف رابطه‌های هم‌نهشتی به رابطه هم‌نهشتی دیگری به صورت زیر خواهیم رسید.

$$ \large ( a x_1 ) ( a x_2 ) \ldots ( a x_r ) \equiv x_1 x_2 \ldots x_r \; (\text{mod } m ) $$

پس از ساده کردن، رابطه همنهشتی زیر حاصل می‌شود.

$$ \large a^r (x_1  x_2 \ldots  x_r ) \equiv x_1 x_2 \ldots x_r \; (\text{mod } m ) $$

از آنجایی که $$ x_i $$ ها نسبت به $$ m $$ اول هستند، حاصل‌ضرب آن‌ها نیز نسبت به $$ m $$‌ اول خواهد بود، یعنی

$$ \large \gcd( x_1 x_2 \ldots x_r , m) = 1 $$

در نتیجه

$$ \large a^r \equiv 1 (\text{mod } m ) $$

پس رابطه زیر برقرار خواهد بود.

$$ \large a^{\varphi ( m )} \equiv 1 \; \;\text{mod } \; m ) $$

قضیه فرما

اگر $$ p $$ عدد اول باشد و $$ p \not {|} a $$ آنگاه

$$ \large a^{p-1} \equiv 1 (\text{mod } p) $$

رابطه قضیه فرما

اثبات: برای اثبات قضیه فرما، کافی است در قضیه اویلر $$ m = p $$ باشد.

البته قضیه فرما را می‌توان به شکل دیگری نیز بیان کرد. برای عدد صحیح $$ a $$ و عدد اول $$ p $$، خواهیم داشت:

$$ \large \forall a \in Z, a^p \equiv a (\text{mod } p ) $$

واضح است که دو طرف رابطه هم‌نهشتی اولیه مربوط به قضیه فرما را در مقدار $$ a $$ ضرب کرده‌ایم. این قضیه به پیدا کردن جواب‌های معادله هم‌نهشتی ما را یاری می‌رساند.

قضیه: فرض کنید $$ ( a , m ) \equiv 1 $$ آنگاه معادله زیر دارای جواب است و اگر $$ x_0 $$ یکی از این جواب‌ها باشد، سایر جواب‌های این معادله نیز به صورت زیر خواهند بود.

$$ \large x_0 + q , \; \; q \in Z $$

اثبات: برای نشان دادن این موضوع، تابع $$ \varphi(m) \geq 1 $$ را در نظر می‌گیریم. در این صورت داریم:

$$ \large x_0 = a ^ {\varphi(m) - 1 } b $$

پس

$$ \large a x_0 = a^{\varphi(m)} b \equiv b \;(\text{mod } m ) $$

در نتیجه معادله حتما جواب خواهد داشت و $$ x_0 $$ یکی از جوا‌ب‌های آن است. حال $$ x $$ را پاسخ دیگری برای این معادله در نظر بگیرید. پس باید رابطه زیر برقرار باشد.

$$ \large a x = a x_0 \equiv b -b (\text{mod } m ) $$

به این ترتیب $$ m $$ مقدار $$ (x - x_0) $$ را می‌شمارد.

$$ \large m | (x - x_0 ) $$

پس قضیه اثبات می‌شود.

براساس این قضیه می‌توان گزاره‌های زیر را هم نوشت:

گزاره ۱

اگر $$ ( a , m ) = 1 $$ آنگاه معادله زیر یک جواب منحصر به فرد در فاصله ۱ تا $$ m - 1 $$ خواهد داشت.

$$ a x  \equiv 1 ( \text{mod } m ) $$

زیرا فقط و فقط یک $$ q $$ در رابطه زیر صدق می‌کند.

$$ \large q \leq x_0 + m q < m $$

گزاره ۲

اگر $$ p $$ یک عدد اول باشد و معادله

$$ \large x^2 \equiv 1 (\text{mod } p ) $$

برقرار باشد، آنگاه

$$ \large x \equiv 1 (\text{nod } p ) $$

یا

$$\large x \equiv p-1 (\text{mod } p ) $$

اثبات این گزاره به سادگی صورت می‌گیرد. فرض کنید که $$x$$‌ به عنوان پاسخ این رابطه هم‌ارزی در بازه ۱ تا $$p-1$$ قرار داشته باشد.

$$ \large 0 \leq x \leq p - 1 $$

طبق فرض مربوط به گزاره و تعریف هم‌نهشتی، داریم:

$$ \large p | x^2-1 =( x - 1) (x + 1) $$

پس $$p$$ هر یک از اجزای $$x^2-1$$ را هم عاد می‌کند.

$$ \large p | (x - 1) , \; \; p | ( x + 1 ) $$

به این ترتیب براساس خاصیت بخش‌پذیری یا عاد کردن برای اعداد صحیح، می‌توان نوشت:

$$ \large \exists n , \; \; x = n p + 1 $$

اگر $$ n = 0 $$ باشد، در نتیجه $$ x = 1 $$‌ بوده و حکم صادق است زیرا یک با هر پیمانه‌ای با یک هم‌نهشت است.

حال فرض می‌کنیم که $$ p | (x + 1 ) $$ در نتیجه برای بعضی از مقادیر $$n$$ می‌توان رابطه زیر را معرفی کرد.

$$ \large  x +1= n p ,\; \; x = n p - 1 $$

که برای رسیدن به حکم $$ n = 1 $$ در نظر گرفته می‌شود و داریم $$ x = p - 1 $$ و در نتیجه با $$ p - 1 $$ به هر پیمانه‌ای، هم‌نهشت است.

قضیه ویلسون

فرض کنید $$ p $$ یک عدد اول باشد، آنگاه حاصل‌ضرب همه اعداد صحیح مثبت کوچکتر از $$ p $$ هم‌نهشت با $$ -1 $$ به پیمانه $$ p $$ خواهند بود. به بیان ریاضی خواهیم داشت:

$$\large ( p - 1 ) ! \equiv -1 ( \text{mod } p ) $$

اثبات: براساس قضیه‌های قبل مشخص است که به ازای هر $$2 \leq a \leq p-2 $$ یک $$ b $$ در مجموعه $$ \{ 2 , 3 , \ldots , p-2 \} $$ وجود دارد که برای $$ a \neq b $$ خواهیم داشت:

$$ \large a b {\not \equiv} 1 (\text{mod } m ) $$

البته این $$ b $$ منحصر به فرد نیز هست. پس خواهیم داشت:

$$ \large 1 \times 2 \times \ldots \times ( p - 2 ) \times ( p - 1 ) \equiv 1 \times ( p - 1 ) (\text{mod } p ) \equiv -1 (\text{mod } p ) $$

قضیه باقی‌مانده‌های چینی

اعداد صحیح  متباین $$ m_1 , m_2 , \ldots , m_r $$ را در نظر بگیرید. آنگاه دستگاه همنهشتی زیر به ازاء مقادیر صحیح $$ a_1 , a_2 , \ldots , a_r $$ دارای جواب است.

$$ \begin{align} \large x & \equiv a_1 (\text{mod } m_1 ) \\
\large x & \equiv a_2 ( \text{mod } m_2 ) \\
& \vdots \\
\large x & \equiv a_r (\text{mod } m_r )
\end{align}$$

اثبات: مقدار $$ m $$ را حاصل‌ضرب مقادیر $$ m_1 $$ تا $$ m_r $$ قرار می‌دهیم.

$$ \large m = \prod_{i=1}^r m_i $$

برای هر $$ j $$ با مقادیر ۱ تا $$ r $$ داریم:

$$ \large ( \frac{m}{m_j} ,m_j) = 1 $$

در نتیجه عدد صحیحی مثل $$b_i$$ وجود دارد که در رابطه زیر صدق کند.

$$ \large \frac{m} {m_j} b_i \equiv 1 (\text {mod } m_j) $$

به این ترتیب اگر $$ i \neq j $$ پس چون $$ m_j | \frac{m}{m_i } $$، در نتیجه داریم:

$$ \large \frac{m}{m_j} b_i \equiv 0 (\text{mod } m_i ) $$

$$ x $$ را به صورت زیر تعریف می‌کنیم.

$$ \large x = \sum_{j=1}^r \frac{m}{m_j} b_i a_i $$

بنابراین خواهیم داشت:

$$ \large x \equiv \frac{m}{m_i} b_i a_i $$

یعنی

$$ \large x \equiv a_i ( \text{mod } m_i ) $$

خلاصه و جمع‌بندی

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

اگر این مطلب برای شما مفید بوده است، آموزش‌ها و مطالب زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ریاضیات
• آموزش ریاضیات مهندسی
• مجموعه آموزش‌های دروس رسمی دبیرستان و پیش‌دانشگاهی
• تقسیم عدد صحیح — به زبان ساده
• الگوریتم تقسیم اعداد — از صفر تا صد
• قواعد بخش پذیری یا عاد کردن — به زبان ساده

^^