الحسابيات: التطابقات، Bézout، Gauss (الطريقة)

التطابقات modulo $n$

$a\equiv b[n]$ تعني: $n$ يقسم $a-b$.

الخصائص:

• إذا كان $a\equiv b[n]$ و $c\equiv d[n]$، فإن $a+c\equiv b+d[n]$ و $a\cdot c\equiv b\cdot d[n]$.
• نتيجة: يمكن الرفع إلى التربيع، التكعيب، إلخ: $a^k\equiv b^k[n]$.

مثال: إثبات أن $n^2+n$ زوجي

الحالة $n\equiv 0[2]$: $n^2+n\equiv 0+0=0[2]$. زوجي.

الحالة $n\equiv 1[2]$: $n^2+n\equiv 1+1=2\equiv 0[2]$. زوجي.

إذن $n^2+n$ زوجي دائما.

القاسم المشترك الأكبر وخوارزمية إقليدس

$\text{pgcd}(a,b)=\text{pgcd}(b,r)$ حيث $r$ = باقي قسمة $a$ على $b$. نكرر حتى $r=0$.

مثال: $\text{pgcd}(252,105)$:

$252=2\times 105+42$ ← $\text{pgcd}(105,42)$.

$105=2\times 42+21$ ← $\text{pgcd}(42,21)$.

$42=2\times 21+0$ ← $\text{pgcd}(21,0)=21$.

مبرهنة بيزو

$a$ و $b$ أوليان فيما بينهما ⇔ يوجد $u,v\in \mathbb{Z}$ بحيث $au+bv=1$.

بشكل أعم: $\text{pgcd}(a,b)=d$ ⇔ ∃ $u,v$: $au+bv=d$.

كيف نجد $u,v$؟ بالرجوع في خوارزمية إقليدس (خوارزمية إقليدس الموسعة).

مبرهنة غاوس

إذا كان $a$ يقسم $bc$ و $\text{pgcd}(a,b)=1$، فإن $a$ يقسم $c$.

تطبيق: لحل $7x\equiv 3[10]$، نبحث عن مقلوب 7 modulo 10. بما أن $7\times 3=21\equiv 1[10]$، فالمقلوب هو 3. إذن $x\equiv 3\times 3=9[10]$.

المعادلات الديوفنتية: $ax+by=c$

يوجد حل ⇔ $\text{pgcd}(a,b)|c$.

إذا نعم: نجد حلا خاصا $(x_0,y_0)$ عبر بيزو، ثم الحل العام هو:

$\{\begin{array}{l}x=x_0+k\frac{b}{d}\\ y=y_0-k\frac{a}{d}\end{array}$ مع $k\in \mathbb{Z}$، $d=\text{pgcd}(a,b)$.

أخطاء يجب تجنبها

• الخلط بين التطابق والمساواة. $a\equiv b[n]$ لا تعني $a=b$.
• تطبيق مبرهنة غاوس دون التحقق من أن $\text{pgcd}(a,b)=1$.
• نسيان الوحدانية modulo $n$: هناك عدد لا نهائي من الحلول لتطابق، لكن حل واحد فقط modulo $n$.

المزيد من التمارين: الحسابيات الثانية باكالوريا علوم رياضية.