ما معنى الموافقة؟ — الرياضيات

تعريف 29.4 رياضيات المرحلة الثانوية · الفصل 29 — الحساب

ليكن $n \in \N^*$ . يكون عددان صحيحان $a, b$ متوافقين بترديد $n$ ، ويُكتب $a \equiv b \pmod n$ ، إذا كان $n \mid (a - b)$ — وبصيغة مكافئة، إذا كان للعددين $a$ و $b$ الباقي نفسه في القسمة الإقليدية على $n$ .

اقرأ في الفصل ←

تعريف 6.18 الرياضيات الجامعية — السنة 1 · الفصل 6 — حساب الأعداد الصحيحة

من أجل $n \in \N^*$ : نكتب $a \equiv b \pmod n$ عندما يكون $n \mid a - b$ . وهذه علاقة تكافؤ متوافقة مع الجمع و الضرب: فإذا كان $a \equiv b$ و $a' \equiv b'$ (بترديد $n$ ) فإن $a + a' \equiv b + b'$ و $aa' \equiv bb'$ و $a^k \equiv b^k$ من أجل $k \in \N$ .

أمثلة

مثال 6.19 (التحقق بالتسعة)

التوافق مع $+$ و $\times$ أداة تحقق قديمة قدم التجارة. وبما أن $10 \equiv 1 \pmod 9$ ، يكون كل عدد صحيح موافقًا بترديد $9$ لمجموع أرقامه (المبرهن عليه في التمرين 6.2). وللتحقق من الدعوى $1234 \times 567 = 699\,678$ : يعطي مجموعا الأرقام $1234 \equiv 1$ و $567 \equiv 18 \equiv 0 \pmod 9$ ، ومنه يجب أن يكون الجداء $\equiv 1 \times 0 = 0$ ؛ وبالفعل $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . فالتحقق يمرّ (والجداء صحيح في الواقع). ولو أفاد أحدهم بالقيمة $699\,478$ لأدانه مجموع الأرقام $43 \equiv 7 \not\equiv 0$ فورًا. والاختبار أحاديّ الجانب — فهو يمسك الخطأ إلا إذا كان الخطأ نفسه مضاعفًا للعدد $9$ — وهذا بالضبط درس شبه الأولية في المثال 6.24 مصغَّرًا: فتحققات التوافق تدحض ولا تشهد.

مثال 6.21 (قلب العدد $7$ بترديد $26$ )

بما أن $\gcd(7, 26) = 1$ ، يكون صف $7$ قابلًا للقلب بترديد $26$ . وبإقليدس الممدَّدة:

26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 ,

ثم بالمقلوب:

1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .

ومنه $7 \times (-11) \equiv 1 \pmod{26}$ ، أي $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ؛ وللتحقق: $7 \times 15 = 105 = 4 \times 26 + 1$ . وبامتلاك المقلوب، يُحلّ أيّ توافق $7x \equiv c \pmod{26}$ بعملية ضرب واحدة: $x \equiv 15c$ . وهذا القلب الآليّ هو حصان العمل في الحساب الترديدي — وفي بروتوكولات المفتاح العام المذكورة في الملاحظة 6.27، حيث تكون الترديدات ذات مئات الأرقام لكن الخوارزمية هي هذه بالضبط.

مثال 6.22 (عندما لا يكون المعامل قابلًا للقلب)

حُلَّ $12x \equiv 8 \pmod{20}$ . هنا $\gcd(12, 20) = 4$ ، فلا يكون $12$ قابلًا للقلب بترديد $20$ — لكن المعادلة تبقى قابلة للمعالجة. يقول التوافق إن $20 \mid 12x - 8$ ؛ وبقسمة العلاقة كلها على $4$ (وهو قاسم للمكوّنات الثلاثة)، تكافئ $5 \mid 3x - 2$ ، أي

3x \equiv 2 \pmod 5 .

والآن $\gcd(3, 5) = 1$ و $3^{-1} \equiv 2 \pmod 5$ ( $3 \times 2 = 6 \equiv 1$ )، ومنه $x \equiv 4 \pmod 5$ : فالحلول هي $x \equiv 4, 9, 14, 19 \pmod{20}$ — أي أربعة صفوف بترديد $20$ ، مطابقةً للقاسم المشترك الأكبر. (ولو لم يقبل الطرف الأيمن القسمة على $4$ ، مثل $12x \equiv 6 \pmod{20}$ ، لما وُجد أيّ حلّ البتة: فالطرف الأيسر دائمًا $\equiv 0 \pmod 4$ .) والشكل العام: $ax \equiv b \pmod n$ قابل للحلّ إذا وفقط إذا كان $\gcd(a, n) \mid b$ ، ويكون له عندئذ بالضبط $\gcd(a, n)$ صفًّا من الحلول — فاقسم كل شيء على القاسم المشترك الأكبر ثم اقلب.

اقرأ في الفصل ←

أمثلة

مصطلحات ذات صلة