الحساب الثانية باك ع.ر

الخطوة 1 – خوارزمية إقليدس لحساب $\mathrm{pgcd}(17,31)$

نجري القسمات الإقليدية المتتالية:

$$31=1\times 17+14$$

$$17=1\times 14+3$$

$$14=4\times 3+2$$

$$3=1\times 2+1$$

$$2=2\times 1+0$$

آخر باقٍ غير منعدم هو $1$، إذن $\mathrm{pgcd}(17,31)=1$. العددان $17$ و $31$ أوليان فيما بينهما فعلاً، وحسب مبرهنة بيزو، توجد متطابقة بيزو $17u+31v=1$.

الخطوة 2 – الرجوع في الخوارزمية (معاملا بيزو)

نرجع في القسمات للتعبير عن $1$ كتركيبة خطية لـ $17$ و $31$:

$$1=3-1\times 2$$

$$=3-1\times (14-4\times 3)=5\times 3-1\times 14$$

$$=5\times (17-1\times 14)-1\times 14=5\times 17-6\times 14$$

$$=5\times 17-6\times (31-1\times 17)=11\times 17-6\times 31$$

نحصل على متطابقة بيزو:

$$\boxed{11\times 17+(-6)\times 31=1}$$

إذن $u=11$ و $v=-6$.

الخطوة 3 – قراءة مقلوب $17$ بترديد $31$ [⚠ الخطأ هنا]

من المتطابقة $11\times 17+(-6)\times 31=1$، نبحث عن مقلوب $17$ بترديد $31$.

يقرأ التلميذ معامل $31$، أي $v=-6$، ويستنتج:

$$17^{-1}\equiv -6(\mathrm{mod}31)$$

للحصول على ممثل في $\{0,1,\dots ,30\}$، نحسب $-6+31=25$، إذن:

$$17^{-1}\equiv 25(\mathrm{mod}31)$$

الخطوة 4 – حل $17x\equiv 5(\mathrm{mod}31)$

نضرب طرفي المعادلة في $17^{-1}\equiv 25(\mathrm{mod}31)$ (القيمة المستنتجة من الخطوة السابقة):

$$x\equiv 25\times 5(\mathrm{mod}31)$$

$$x\equiv 125(\mathrm{mod}31)$$

نختزل: $125=4\times 31+1$، إذن $125\equiv 1(\mathrm{mod}31)$.

يعطي التطابق الأول:

$$x\equiv 1(\mathrm{mod}31)$$

الخطوة 5 – التحقق من $\mathrm{pgcd}(31,7)=1$ وتهيئة مبرهنة الباقي الصيني

$31$ عدد أولي و $7\nmid 31$، إذن $\mathrm{pgcd}(31,7)=1$. العددان أوليان فيما بينهما فعلاً، وتنطبق مبرهنة الباقي الصيني: تقبل الجملة حلاً وحيداً بترديد $31\times 7=217$.

يجب حل:

$$\{\begin{array}{l}x\equiv 1(\mathrm{mod}31)\\ x\equiv 3(\mathrm{mod}7)\end{array}$$

نبحث عن $x$ على الصيغة $x=1+31k$، $k\in \mathbb{Z}$. يفرض التطابق الثاني:

$$1+31k\equiv 3(\mathrm{mod}7)$$

$$31k\equiv 2(\mathrm{mod}7)$$

بما أن $31=4\times 7+3$، فإن $31\equiv 3(\mathrm{mod}7)$، إذن:

$$3k\equiv 2(\mathrm{mod}7)$$

مقلوب $3$ بترديد $7$: $3\times 5=15=2\times 7+1$، إذن $3^{-1}\equiv 5(\mathrm{mod}7)$.

$$k\equiv 5\times 2\equiv 10\equiv 3(\mathrm{mod}7)$$

إذن $x=1+31\times 3=1+93=94$.

الخطوة 6 – الخلاصة

مجموعة حلول الجملة هي:

$$\boxed{x\equiv 94(\mathrm{mod}217)}$$

التحقق: $17\times 94=1598=51\times 31+17$… نحصل على $17\times 94\equiv 17(\mathrm{mod}31)$، وهو ما يعطي $17\not\equiv 5(\mathrm{mod}31)$ — لكن التلميذ لا يتحقق ويستنتج مباشرة.