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

بروزرسانی شده در: 21:56 1405/02/16 مشاهده: 59 دسته بندی: کپسول آموزشی

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

هم‌نهشتی و قانون حذف: دلیل مجاز نبودن ساده‌سازی مستقیم و نقش اصلاح پیمانه

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

هم‌نهشتی چیست و چه تفاوتی با تساوی دارد؟

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

در ریاضیات دبیرستان، با معادله‌های معمولی مانند $2x = 10$ آشنا هستیم. در این معادله می‌توانیم دو طرف را بر $2$ تقسیم کنیم و $x = 5$ را به دست آوریم. اما در هم‌نهشتی‌ها چنین ساده‌سازی مستقیمی خطرناک است. به رابطه‌ی زیر توجه کنید:

مثال: $8 \equiv 2 \pmod{6}$ زیرا $8 - 2 = 6$ و $6 \mid 6$.

اگر مانند تساوی هر دو طرف را بر $2$ تقسیم کنیم، به $4 \equiv 1 \pmod{6}$ می‌رسیم. اما آیا $4 - 1 = 3$ بر $6$ بخش‌پذیر است؟ خیر. بنابراین حذف بدون تغییر پیمانه، نتیجه‌ی نادرست می‌دهد. به همین دلیل قانون حذف در هم‌نهشتی نیازمند «اصلاح پیمانه» است.

قانون اصلی حذف با اصلاح پیمانه

فرض کنید $a \cdot c \equiv b \cdot c \pmod{m}$. اگر $d = \gcd(c, m)$ باشد، آنگاه می‌توانیم عامل مشترک $c$ را حذف کنیم، اما پیمانه نیز باید به $\frac{m}{d}$ تغییر کند. یعنی:

قانون حذف: $a \cdot c \equiv b \cdot c \pmod{m} \quad \Rightarrow \quad a \equiv b \pmod{\frac{m}{\gcd(c,m)}}$

به عبارت دیگر، اگر عامل مشترک و پیمانه هم‌بزرگ‌ترین مقسوم‌علیه داشته باشند ($d \gt 1$)، پیمانه کوچک‌تر می‌شود. اگر $d = 1$ یعنی عامل مشترک نسبت به پیمانه اول است، آنگاه پیمانه تغییر نمی‌کند و حذف مانند معادلات معمولی انجام می‌شود. این دقیقاً نقطه‌ی کلیدی «حذف فقط با اصلاح پیمانه» است.

عملیات	معادله معمولی	هم‌نهشتی بدون اصلاح	هم‌نهشتی با اصلاح پیمانه
حذف عامل $2$ از $2x = 8$ و $2a \equiv 2b \pmod{6}$	$x = 4$ درست	$a \equiv b \pmod{6}$غلط	$a \equiv b \pmod{3}$درست
شرط حذف	همیشه مجاز	فقط وقتی $\gcd(c,m)=1$	همیشه با تقسیم پیمانه بر $\gcd(c,m)$

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

رابطه‌ی $12 \equiv 18 \pmod{6}$ را در نظر بگیرید. هر دو طرف بر $6$ بخش‌پذیرند و پیمانه هم $6$ است. طبق قانون:

عامل مشترک $c = 6$
$d = \gcd(6, 6) = 6$
حذف عامل $6$ می‌دهد: $2 \equiv 3 \pmod{6/6}$ یعنی $2 \equiv 3 \pmod{1}$

هر عددی به پیمانه $1$ با هر عدد دیگر هم‌نهشت است (زیرا $1$ هر تفاضلی را می‌شمارد). پس رابطه درست است. اگر بدون اصلاح پیمانه حذف می‌کردیم، $2 \equiv 3 \pmod{6}$ به دست می‌آمد که غلط است.

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

فرض کنید می‌خواهیم معادله‌ی $4x \equiv 8 \pmod{12}$ را حل کنیم. ابتدا می‌توان از قانون حذف استفاده کرد:

عامل مشترک سمت راست و چپ $4$ است ($4x$ و $8$).
$\gcd(4, 12) = 4$
حذف $4$ با اصلاح پیمانه: $x \equiv 2 \pmod{12/4}= \pmod{3}$
پاسخ: $x \equiv 2 \pmod{3}$

در یک مثال واقعی، اگر در مسئله‌ای ساعت گردان (پیمانه $12$) داشته باشیم $4$ برابر یک ساعت مشخص برابر $8$ باشد، ساعت اولیه فقط به پیمانه $3$ تعیین می‌شود نه $12$. این کاهش پیمانه، اطلاعات کلیدی در رمزنگاری کلید عمومی¹ نیز کاربرد دارد.

چالش‌های مفهومی

پرسش ۱: چرا در هم‌نهشتی نمی‌توانیم مانند معادله معمولی عامل مشترک را حذف کنیم؟
پاسخ: زیرا هم‌نهشتی بر پایه بخش‌پذیری تفاضل تعریف می‌شود، نه تساوی دقیق. وقتی دو طرف را بر عددی تقسیم می‌کنیم، بخش‌پذیری پیمانه نسبت به عدد جدید ممکن است از بین برود مگر اینکه پیمانه را نیز به همان نسبت کوچک کنیم (تقسیم بر $\gcd$). در واقع پیمانه نقش «واحد اندازه‌گیری» را دارد و با حذف عامل مشترک باید واحد را تنظیم کرد.

پرسش ۲: اگر $\gcd(c, m) = 1$ باشد، چه تغییری در قانون ایجاد می‌شود؟
پاسخ: در این حالت $d = 1$ و پیمانه بدون تغییر می‌ماند زیرا $\frac{m}{1} = m$. بنابراین اگر عامل مشترک نسبت به پیمانه اول باشد، حذف مانند معادلات معمولی مجاز است. مثال: $5 \cdot 2 \equiv 11 \cdot 2 \pmod{9}$ (چون $\gcd(2,9)=1$) نتیجه می‌دهد $5 \equiv 11 \pmod{9}$ که درست است.

پرسش ۳: آیا همیشه پیمانه جدید صحیح است؟ و اگر پیمانه جدید برابر $1$ شود چه معنایی دارد؟
پاسخ: بله، پیمانه جدید $\frac{m}{d}$ همیشه یک عدد طبیعی است. اگر پیمانه جدید $1$ شود، یعنی رابطه هم‌نهشتی به صورت بدیهی همیشه برقرار است (هر دو عدد نسبت به پیمانه $1$ هم‌نهشت هستند). این حالت زمانی رخ می‌دهد که عامل مشترک خود پیمانه یا مضربی از پیمانه باشد.

جمع‌بندی

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

پاورقی

¹ رمزنگاری کلید عمومی (Public-Key Cryptography): شاخه‌ای از رمزنگاری که از دو کلید متفاوت (عمومی و خصوصی) استفاده می‌کند. قانون حذف در هم‌نهشتی برای تحلیل امنیت الگوریتم‌هایی مانند آراس‌ای² به کار می‌رود.
² آراس‌ای (RSA): یکی از اولین و پرکاربردترین الگوریتم‌های رمزنگاری کلید عمومی که مبتنی بر دشواری فاکتورگیری اعداد بزرگ و خواص هم‌نهشتی است.

جستجوهای پرتکرار

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