سرفصل‌های این مبحث

نظریه اعداد

هم‌ نهشتی (دسته کامل مانده‌ ها)

آخرین ویرایش: 15 تیر 1403

دسته‌بندی: نظریه اعداد

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

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

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

بنابراین توسط این رابطه می‌توان مجموعه $ℤ$ را به دسته‌هایی افراز نمود که آنها را دسته‌های هم‌نهشتی یا کلاس‌های هم‌نهشتی می‌نامیم.

تعریف دسته هم‌نهشتی به پیمانه $m$

دسته هم‌نهشتی $a$ به پیمانه $m$ که با نماد ${[a]}_{m}$ نشان داده می‌شود،عبارت است از کلیه اعداد صحیح‌ای که با $a$ به پیمانه $m$ هم‌نهشت هستند یعنی:

$a \in Z; {[a]}_{m} = \{x |x \overset{m}{\equiv} a\}$

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

تمرین

باقی مانده های تقسیم اعداد بر $4$ عبارتند از $\{0, 1, 2, 3\}$ .

اگر هر کدام از این باقی مانده ها را نماینده یک مجموعه از اعداد در نظر بگیریم، که باقی مانده تقسیم هر عضو آن مجموعه بر عدد $4$ به ترتیب $3, 2, 1, 0$ باشد، داریم:

$\begin{array}{l} A_{0} = \{x \in ℤ| x = 4 k\} = \{\dots, - 8, - 4, 0, 4, 8, \dots, 16, \dots\} = {[0]}_{4} \end{array}$

$\begin{array}{l} A_{1} = \{x \in ℤ| x = 4 k + 1\} = \{\dots, - 7, - 3, 1, 5, 9, \dots, 17, \dots\} = {[1]}_{4} \end{array}$

$\begin{array}{l} A_{2} = \{x \in ℤ| x = 4 k + 2\} = \{\dots, - 6, - 2, 2, 6, 10, \dots, 18, \dots\} = {[2]}_{4} \end{array}$

$A_{3} = \{x \in ℤ| x = 4 k + 3\} = \{\dots, - 5, - 1, 3, 7, 11, \dots, 19, \dots\} = {[3]}_{4}$

دو عضو دل‌خواه از مجموعه $A_{0}$ در نظر بگیرید. آیا تفاضل این دو عدد مضرب $4$ است؟

بله

$(16) - (8) = 8 = (2) (4)$

از مجموعه $A_{1}$ دو عضو دل‌خواه را در نظر بگیرید و تفاضل آنها را حساب کنید. آیا عدد حاصل مضرب $4$ است؟

بله.

$(- 7) - (5) = - 12 = (- 3) (4)$

نتیجه ای را که از دو تمرین قبل گرفتید در حالت کلی برای هر عضو دل‌خواه از $A_{1}$ اثبات کنید.

فرض کنید $a, b$ متعلق بع مجموعه $A_{1}$ باشد:

$\{\begin{cases} a = 4 k_{1} + 1 \\ b = 4 k_{2} + 1 \end{cases}〉 a - b = (4 k_{1} + 1) - (4 k_{2} + 1)$

$\begin{matrix} \begin{array}{l} a - b = (4 k_{1} + 1) - (4 k_{2} + 1) \\ \Rightarrow a - b = 4 (k_{1} - k_{2}); k = k_{1} - k_{2} \end{array} \end{matrix}$

$\begin{array}{l} \Rightarrow a - b = 4 k \\ \Rightarrow 4 | a - b \end{array}$

آیا درست است که بگوییم اعضای مجموعه $A_{2}$ همگی در تقسیم بر عدد $4$ ، باقی مانده یکسان دارند؟

بله.

در مورد مجموعه $A_{3}$ چه می‌توان گفت؟

تفاضل عر دو عدد دل‌خواه از مجموعه $A_{3}$ مضرب $4$ است.

نکته

1- هم‌نهشتی به پیمانه $m$ در مجموعه $ℤ$ رابطه‌ای هم‌ارز بوده و مجموعه $ℤ$ را به دسته‌های هم‌ارزی افراز می‌کند و مجموعه این دسته‌ها را به‌صورت زیر نشان می‌دهیم:

$Z / m = Z_{m} = \{[0], [1], ....., [m - 1]\}$

تمرین

هم‌نهشتی به پیمانه $m = 3$ را در نظر بگیرید. مجموعه‌های زیر را بنویسید:

$[0]$

$[0] = \{x \in Z |x \overset{3}{\equiv} 0\} = \{x \in Z |x = 3 k\} = \{....., - 3, 0, 3, .....\}$

مجموعه فوق مجموعه اعدادی است که باقیمانده تقسیم آنها بر $3$ مساوی صفر است.

$[1]$

$[1] = \{x \in Z |x \overset{3}{\equiv} 1\} = \{x \in Z |x = 3 k + 1\} = \{...., - 2, 1, 4, .....\}$

مجموعه فوق مجموعه اعدادی است که باقیمانده تقسیم آنها بر $3$ مساوی یک است.

$[2]$

$[2] = \{x \in Z |x \overset{3}{\equiv} 2\} = \{x \in Z |x = 3 k + 2\} = \{......, - 1, 2, 5, ......\}$

مجموعه فوق مجموعه اعدادی است که باقیمانده تقسیم آنها بر $3$ مساوی یک است.

مجموعه دسته‌های هم‌ارزی افراز شده را بنویسید.

$Z_{3} = \{[0], [1], [2]\}$

یعنی این سه دسته هم‌ارزی در قالب یک مجموعه مانند $Z_{3}$ تمام اعداد صحیح را می‌پوشاند یعنی:

$[0] \cup [1] \cup [2] = Ζ$

کدام‌یک از کلاس‌های هم‌ارزی فوق تهی است؟

هیچ‌یک از کلاس‌های هم‌ارزی $[2], [1], [0]$ تهی نیست، زیرا دست‌کم نماینده آن کلاس متعلق به کلاس هم‌ارزی است.

در هم‌نهشتی به پیمانه $m = 3$ کدام دسته‌ها متمایز هستند؟

در هم‌نهشتی به پیمانه $m = 3$ فقط دسته‌های $[2], [1], [0]$ متمایز هستند.

به‌طور کلی:

در هم‌نهشتی به پیمانه $m$ فقط دسته‌های $[m - 1], ....., [1], [0]$ متمایز هستند.

به‌عنوان نمونه برای $m = 4$ دسته‌های متمایز هستند عبارتند از:

$\begin{array}{l} Z_{4} = \{[0], [1], [2], [3]\} \end{array}$

$\begin{array}{l} {[0]}_{4} = \{x |x = 4 k + 0\} = \{....., - 4, 0, 4, ....\} \end{array}$

$\begin{array}{l} {[1]}_{4} = \{x |x = 4 k + 1\} = \{....., - 3, 1, 5, .....\} \end{array}$

$\begin{array}{l} {[2]}_{4} = \{x |x = 4 k + 2\} = \{....., - 2, 2, 6, .....\} \end{array}$

$\begin{array}{l} {[3]}_{4} = \{x |x = 4 k + 3\} = \{....., - 1, 3, 7, ......\} \end{array}$

آیا هر دو عضو متعلق به یکی از دسته هم‌نهشتی فوق در هم‌نهشتی به پیمانه مربوطه، با یکدیگر هم‌نهشت هستند؟

بله. به‌عنوان نمونه داریم:

در دسته هم‌نهشتی ${[0]}_{3}$ که به‌صورت زیر تعریف می‌شود:

${[0]}_{3} = \{....., - 3, 0, 3, 6, 9, .....\}$

دو عضو $6$ و $9$ را در نظر می‌گیریم:

$9 \overset{3}{\equiv} 6 \Rightarrow 9 - 6 = 3 k \overset{k = 1}{\to} 9 - 6 = 3 (1)$

آیا دو عضو متعلق به دو دسته هم‌نهشتی متفاوت در هم‌نهشتی به پیمانه $m$ هم‌نهشت هستند؟

خیر

$\{\begin{array}{l} {[0]}_{3} = \{...., - 3, 0, 3, 6, ....\} \\ {[1]}_{3} = \{....., - 2, 1, 4, ....\} \end{array}〉 6 \overset{3}{\equiv} 4$

آیا دو کلاس هم‌ارزی می‌توانند عضوهای مشترک داشته باشند؟

خیر

هر دو کلاس هم‌ارزی یا مساویند مانند $[0] = [3]$ .

${[3]}_{3} = \{x \in Z |x \overset{3}{\equiv} 3\} = \{x \in Z |x = 3 k + 3\} = \{......, 3, 6, 9, .....\} = {[0]}_{3}$

یا کاملا از هم جدا و متمایزاند مانند $[2], [1]$ و حالت سومی وجود ندارد.

نکته

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

3- در ${[0]}_{m}$ منظور آن است که باقیمانده تقسیم تمام اعداد بر پیمانه $m$ برابر صفر است و در ${[1]}_{m}$ منظور کلیه اعدادی است که باقیمانده تقسیم آنها بر پیمانه $m$ برابر یک است.

4- تساوی دو کلاس در $Z_{m}$ (به پیمانه $m$ )

اگر اختلاف نماینده‌های دو کلاس بر $m$ قابل قسمت باشد، گوییم آن دو کلاس با هم برابرند:

$\{\begin{array}{l} {[a]}_{m} \\ {[b]}_{m} \end{array}〉 a - b = k m \Leftrightarrow {[a]}_{m} = {[b]}_{m}$

به‌عنوان نمونه داریم:

${[7]}_{5} = {[- 3]}_{5} \Leftrightarrow 7 - (- 3) = 2 (5)$

5- جمع و ضرب در $Z_{m}$

نماینده‌های دو کلاس را باهم جمع یا ضرب می‌کنیم:

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

$\begin{array}{l} {[a]}_{m} \oplus {[b]}_{m} = {[a + b]}_{m} \\ {[a]}_{m} \otimes {[b]}_{m} = {[a \times b]}_{m} \end{array}$

به‌عنوان نمونه داریم:

$\begin{array}{l} {[3]}_{10} \oplus {[5]}_{10} = {[8]}_{10}; (8 < 10) \end{array}$

$\begin{array}{l} {[- 5]}_{13} \otimes {[- 2]}_{13} = {[10]}_{13}; (10 < 13) \end{array}$

$\begin{array}{l} {[7]}_{11} \oplus {[12]}_{11} = {[19]}_{11} = {[8]}_{11}; (11 < 19) (19 \overset{11}{\equiv} 8) \end{array}$

$\begin{array}{l} {[5]}_{7} \otimes {[6]}_{7} = {[30]}_{7} = {[2]}_{7}; (7 < 30) (30 \overset{7}{\equiv} 2) \end{array}$

${[- 3]}_{5} \otimes {[4]}_{5} = {[- 12]}_{5}$

از آنجا که کلاس هم‌ارزی را با نماینده مثبت بیان می‌کنند، داریم:

$- 12 \overset{5}{\equiv} - 12 + (5) (3) \overset{5}{\equiv} 3 \Rightarrow {[- 12]}_{5} = {[3]}_{5}$

${[- 3]}_{5} \otimes {[4]}_{5} = {[- 12]}_{5} \Rightarrow {[- 3]}_{5} \otimes {[4]}_{5} = {[3]}_{5}; (3 < 5)$

قضایای دسته‌های هم‌نهشتی

قضیه

عناصر مجموعه $\{0, 1, 2, ..., m - 1\}$ به پیمانه $m$ دوبه‌دو ناهم‌نهشت هستند.

اثبات

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

نتیجه این‌که به پیمانه $m$ دسته‌های هم‌نهشتی $[m - 1], ..., [1], [0]$ دوبه‌دو متمایزند و هر عدد صحیح با یکی و تنها یکی از اعداد صحیح $m - 1, ...., 1, 0$ به پیمانه $m$ هم‌نهشت است.

قضیه

شرط لازم و کافی برای آن‌که مجموعه $k = \{a_{1}, a_{2}, ..., a_{m}\}$ یک دسته کامل مانده به پیمانه $m$ باشد ‎آن است که هیچ دو عضوی از این مجموعه در هم‌نهشتی $m$ با یکدیگر هم‌نهشت نباشد.

اثبات

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

$A = \{0, 1, ..., (m - 1)\}$

ولی قبلا ثابت کردیم هیچ دو عضوی از عناصر مجموعه $A$ در هم‌نهشتی به پیمانه $m$ با یکدیگر هم‌نهشت نیستند.

عکس این قضیه به‌وضوح برقرار است.

قضیه

اگر دو دسته هم‌ارزی با یکدیگر مساوی باشند، رابطه هم‌نهشتی بین نماینده‌های آنها به پیمانه $m$ به‌صورت زیر وجود دارد:

$\begin{array}{l} [a] = [b] \Leftrightarrow a \overset{m}{\equiv} b \\ i f b \in [a] \Leftrightarrow [a] = [b] \end{array}$

اثبات

ثابت می‌کنیم که:

$a \overset{m}{\equiv} b \Rightarrow [a] = [b]$

$x \in [a] \Leftrightarrow x \overset{m}{\equiv} a \overset{a \overset{m}{\equiv} b}{\to} x \overset{m}{\equiv} b \Leftrightarrow x \in [b]$

ثابت می‌کنیم که:

$[a] = [b] \Rightarrow a \overset{m}{\equiv} b$

$a \in [a], [a] = [b] \Rightarrow a \in [b] \Rightarrow a \overset{m}{\equiv} b$

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

هم‌نهشتی (دسته کامل مانده‌ها)

3,000تومان

برای ارسال نظر وارد سایت شوید

نظریه اعداد

هم‌ نهشتی (دسته کامل مانده‌ ها)

تعریف دسته هم‌نهشتی به پیمانه $m$

قضایای دسته‌های هم‌نهشتی

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟

نظریه اعداد

هم‌ نهشتی (دسته کامل مانده‌ ها)

تعریف دسته هم‌نهشتی به پیمانه m

قضایای دسته‌های هم‌نهشتی

تعریف دسته هم‌نهشتی به پیمانه $m$