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

التطابقات معيار 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 ).

* لتكن f(x) = x^2 + 3x + 2 حيث x ينتمي إلى المجموعة S={1,2,3,...,25}. أوجد جميع الأعداد s من المجموعة S بحيث f(s) تقبل القسمة على 6.

* إذا كان a,b صحيحين و p عدد أولي, أثبت أن (a + b)^p \equiv a^p + b^p \;(\bmod p).