التطابقات معيار n

congruences mod n

يعد مفهوم التطابق من ابرز المفاهيم التي تضمنتها نظرية العدد, ويعود تقديم هذا المفهوم للعالم الألماني جاوس Gauss (1777-1855م), وذلك في أوائل التسعينيات وهو تعبير عن قابلية القسمة بأسلوب أكثر مرونة يسمح بدراسة أعمق للخصائص العددية

تعريف التطابق معيار n

ليكن n عدد طبيعي, نقول أن العددين الصحيحين a,b متطابقان معيار n أو مقياس n إذا كان n|(a-b). ونكتب $a \equiv b\;(\bmod n)$ وهذا يعني أن للعددين a,b نفس الباقي عند قسمتهما على n. أما إذا كان n لا يقسم (a-b), $n\not |(a - b)$ , فنكتب $a\not \equiv b\;(\bmod n)$ .

مثال 1:
$15 \equiv 3\;(\bmod 2)$ لأن الفرق 15-3 يقبل القسمة على 2.
$100 \equiv 100\;(\bmod 99)$ لأن الفرق 100-100 يقبل القسمة على 99.
$17 \equiv - 1\;(\bmod 3)$ لأن 17-(-1) يقبل القسمة على 3.
$- 9 \equiv 2\;(\bmod 11)$ لأن -9-(-2) يقبل القسمة على 11.

حقيقة1: ليكن n عدد طبيعي و a,b عددين صحيحين.

1) $a \equiv b\;(\bmod n)$ إذا وإذا فقط وجد عدد صحيح k بحيث $a = kn + b$ .

2) إذا كان $a \equiv b\;(\bmod n)$ فإن gcd(n,a)= gcd(n,b), حيث gcd تعني القاسم المشترك الأكبرgreatest common divisor.

الإثبات:
1) افرض $a \equiv b\;(\bmod n)$ . إذا n يقسم (a-b) ولذلك (a-b) من مضاعفات n وبالتالي يوجد عدد صحيح k بحيث a-b=kn, أي أن a=kn+b. وعلى العكس من ذلك إذا وجد صحيح k بحيث a=kn+b فإن (a-b) يقبل القسمة على n, حيث k خارج القسمة.

2) افرض أن gcd(n,a)=d وgcd(n,b0=e . بنفس النقاش السابق يوجد عدد صحيح k بحيث a-b=kn. بالقسمة على d نجد أن

$\frac{a}{d} - \frac{b}{d} = \frac{{kn}}{d}$

إذا $\frac{b}{d}$ عدد صحيح لأن الحدين الآخرين أعداد صحيحة. إذا d يقسم b وبالتالي $d \le e$ . في المقابل اقسم a-b=kn على e وبنقاش مشابه نصل إلى أن $d \ge e$ . وعليه فإن d=e.

خواص جبرية للتطابق معيار n

باستخدام التعريف مباشرة نستطيع التحقق من الخواص التالية:

1) إذا كان a عدد صحيح فإن $a \equiv a\;(\bmod n)$ (خاصية التناظر)

2) إذا كان $a \equiv b\;(\bmod n)$ فإن $b \equiv a\;(\bmod n)$ (خاصية الانعكاس)

3) إذا كان $a \equiv b\;(\bmod n)$ و $b \equiv c\;(\bmod n)$ فإن $a \equiv c\;(\bmod n)$ (خاصية التعدي)

لذا فإن التطابق معيار n علاقة تكافؤ على مجموعة الأعداد الصحيحة Z, وهذه العلاقة تقسم Z إلى n فصل تكافؤ [0], [1], [2],..., [n-1] ويرمز لمجموعة هذه الفصول بالرمز $\mathbb{Z}/n\mathbb{Z}$ , والفصل [a] هو المجموعة

$[a] = \{ \ldots ,a - 2n,a - n,a,a + n,a + 2n, \ldots \}$

حساب التطابقات
الكثير من الخصائص الأولية للتساوي نجدها متحققة في التطابق معيار n.

حقيقة2: إذا كان $a \equiv b\;(\bmod n)$ و $c \equiv d\;(\bmod n)$ فإن

$a + c \equiv b + d\;(\bmod n)$ (قانون جمع التطابقات)

$ac \equiv bd\;(\bmod n)$ (قانون ضرب التطابقات)

$a - c \equiv b - d\;(\bmod n)$ (قانون طرح التطابقات)

الإثبات: الشرط يقتضي أن a-b , c-d يقبلان القسمة على n ولذلك مجموعهما (a+c)-(b+d) يقبل القسمة على n وبالتالي $a + c \equiv b + d\;(\bmod n)$ . كذلك من المتطابقة

ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)

نستنتج أن ac-bd يقبل القسمة على n باعتباره حاصل جمع مقدارين (a-b), (c-d) يقبلان القسمة على n. إذا

$ac \equiv bd\;(\bmod n)$

بالنسبة لقانون الطرح فهو ليس سوى تطبيق^[م] لقانون الضرب على التطابقين $c \equiv d\;(\bmod n)$ و $- 1 \equiv - 1\;(\bmod n)$ لاستنتاج أن $- c \equiv - d\;(\bmod n)$ ثم جمع هذا التطابق مع $a \equiv b\;(\bmod n)$ وفق قانون الجمع.

الحقيقة التالية تعميم لقانوني الجمع والضرب ونترك إثباتها للقاري بواسطة الاستقراء الرياضي^[م].

حقيقة3: إذا كان لدينا التطابقات $a_i \equiv b_i \;(\bmod n)$ حيث i=1,2,...,m فإن

$\begin{array}{l} a_1 + a_2 + \ldots + a_m \equiv b_1 + b_2 + \ldots + b_m \;(\bmod n) \\ a_1 a_2 \ldots a_m \equiv b_1 b_2 \ldots b_m \;(\bmod n),\quad m \in Z^ + \\ \end{array}$

نتيجة 1: إذا كان $a \equiv b\;(\bmod n)$ فإن

$a^m \equiv b^m \;(\bmod n),\quad m \in Z^ +$

هذه النتيجة من الأهمية بمكان وتأتي مباشرة من الفقرة الثانية من الحقيقة بوضع $a_i = a,\;b_i = b$ لكل i=1,2,...,m.

المثال الآتي يبين جوانب من استخدام هذه القوانين والخواص, وللإطلاع على استخدامات أخرى في تكوين قواعد لقابلية القسمة, انظر موضوع قابلية القسمة على 3

http://www.mathramz.com/math/Divisibility_by_3

مثال2:

1) اثبت أن $6^{n - 1} + 6^{n - 2} + \cdots + 6^1 + 1 - n$ تقبل القسمة على 5 لأي عدد صحيح موجب n.
بما أن $6 \equiv 1\;(\bmod 5)$ فإن $6^m \equiv 1^m = 1\;(\bmod 5)$ حيث m صحيح موجب, ومن تعميم قانون جمع التطابقات

$6^{n - 1} + 6^{n - 2} + \cdots + 6^1 + 1 - n \equiv (1\; + 1 + \cdots + 1 + 1) - n = n - n = 0\;(\bmod 5)$

2) أثبت أن $3^{4n + 2} + 5^{2n + 1}$ يقبل القسمة على 14, حيث n طبيعي.
لهذه المسألة عدة طرق منها الاستقراء الرياضي^[م], لكن باستخدام التطابق نصل للجواب سريعا. لاحظ أن

$3^{4n + 2} + 5^{2n + 1} = 9(81)^n + 5(25)^n$

ولكن $81 \equiv - 3\;(\bmod 14),\quad 25 \equiv - 3\;(\bmod 14)$ إذا

$(81)^n \equiv ( - 3)^n \;(\bmod 14),\quad (25)^n \equiv ( - 3)^n \;(\bmod 14)$

وبالتالي

$3^{4n + 2} + 5^{2n + 1} \equiv 9( - 3)^n + 5( - 3)^n \equiv 14( - 3)^n \; \equiv 0\;(\bmod 14)$

وبهذا تثبت قابلية القسمة على 14.

3) إذا كان x عدد صحيح فإن $x^3 \equiv x\;(\bmod 3)$ . النتيجة واضحة عندما x من مضاعفات 3. فيما عدا هذا فإن $x \equiv \pm 1\;(\bmod 3)$ لاحظ الباقي السالب بديل عن الباقي 2 وهذا لأن $2 \equiv - 1\;(\bmod 3)$ . إذا $x^3 \equiv \pm 1\;(\bmod 3)$ وبالتالي $x^3 \equiv x\;(\bmod 3)$ .

مثال3: اوجد الأعداد الصحيحة x بحيث $1 \le x \le 100$ والتي تجعل 7 يقسم $x^2 + 15x + 1$ .

المطلوب هو حل للمعادلة التطابقية التالي

$x^2 + 15x + 1 \equiv 0\;(\bmod 7)$

وفق المدى المحدد في المسألة . بما أن $14x \equiv 0\;(\bmod 7)$ فمن قانون طرح التطابقات

$x^2 + x + 1 \equiv 0\;(\bmod 7)$

من خوارزمية القسمة, $x = 7q + r$ , حيث $0 \le r < 7$ نجد أن باقي قسمة $x^2 + x + 1$ على 7 يتحدد من الباقي r وذلك لأن

$x^2 + x + 1 = (7q + r)^2 + (7q + r) + 1 = 7m + r^2 + r + 1$

لذلك يكفي أن نجرب على الأعداد 0,1,2,3,4,5,6, x= فقط . سنجد أن الناتج يقبل القسمة على 7 فقط عند x=2, x=4 إذا الحلول هي فقط تلك الأعداد التي ها الباقي 2 أو 4. بلغة التطابق:

$x \equiv 2,\;x \equiv 4\;(\bmod 7),\quad 1 \le x \le 100$

إذا الحلول المطلوبة هي

2,9,16, 23, ..., 93,100

4, 11,19,26,...., 88, 95

قانون الإختصار Cancelation law:

العلاقة $a \equiv b\;(\bmod n)$ تقتضي أن n يقسم a-b وبالتالي فإن n تقسم m(a-b)=ma-mb وذلك لأي صحيح m, وبالتالي

$ma \equiv mb\;(\bmod n),\quad m \in Z$

لكن العكس غير صحيح بشكل عام, لأنه إذا كان n يقسم m(a-b) فليس بالضرورة n يقسم (a-b). ولكن إذا كان n,m أوليان نسبيا فهذا شرط كافي لضمان أن n يقسم (a-b) وبهذا يثبت القانون التالي المسمى قانون الاختصار

إذا كان $ka \equiv kb\;(\bmod n)$ وكان gcd(n,k)=1 فإن $a \equiv b\;(\bmod n)$

لهذا القانون نسخة أكثر عمومية ويترك إثباتها للقارئ نذكرها في الحقيقة التالية

حقيقة4: إذا كانت a,b,k أعداد صحيحة و n عدد صحيح موجب وكان gcd(n,k)=d فإن

$ka \equiv kb\;(\bmod n)$ إذا وإذا فقط $a \equiv b\;(\bmod n/d)$

مسائل

* ليكن n صحيح موجب. بين باستخدام خوارزمية القسمة أن أي عدد صحيح a يطابق باقي قسمته r معيار n.

* (عكس قانون الضرب) إذا كان $ac \equiv bd\;(\bmod n)$ وكان $c \equiv d\;(\bmod n)$ و gcd(n,c)=1 فإن $a \equiv b\;(\bmod n)$ .

* إذا كان $a \equiv b\;(\bmod n_i )$ حيث i=1,2,...,m فإن $a \equiv b\;(\bmod lcm(n_1 ,n_2 , \cdots ,n_m ))$ حيث lcm تعني المضاعف المشترك الأصغر least common multiple. وكحالة خاصة, إذا كانت الأعداد أولية نسبيا مثنى مثنى (بمعنى $\gcd (n_i ,n_j ) = 1,\;i \ne j$ ) فإن $a \equiv b\;(\bmod n_1 n_2 \cdots n_m )$ .