الحساب في ℕ الجذع المشترك

الخطوة 1 — خوارزمية إقليدس

نقوم بالقسمات الإقليدية المتتالية:

آخر باق غير منعدم هو $84$، إذن $$\mathrm{pgcd}(252,168)=84.$$

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

لا تتضمن الخوارزمية سوى قسمة واحدة غير بديهية:

نعزل الباقي $84$:

نسعى للتعبير عن $84$ على الشكل $252u+168v$. بالتعويض، نحصل مباشرة على:

إذن الحل الخاص هو $u_0=1$، $v_0=-1$.

التحقق: $252\times 1+168\times (-1)=252-168=84.$ ✓

الخطوة 3 — الحلول الصحيحة للمعادلة $252x+168y=84$

بما أن $\mathrm{pgcd}(252,168)=84$ يقسم $84$، فإن المعادلة تقبل حلولاً صحيحة.

نقسم المعادلة على $84$:

نستنتج حلاً خاصاً للمعادلة $3x+2y=1$ من مطابقة بيزو المحصل عليها في الخطوة السابقة. بما أن $84=252\times 1+168\times (-1)$، بالقسمة على $84$:

إذن $(x_0,y_0)=(1,-1)$ هو حل خاص للمعادلة $3x+2y=1$.

مجموعة حلول المعادلة $3x+2y=1$ هي:

تبرير: إذا كان $(x,y)$ حلاً، فإن $3(x-1)+2(y+1)=0$، أي $3(x-1)=-2(y+1)$. وبما أن $\mathrm{pgcd}(3,2)=1$، فإن $2\mid (x-1)$، إذن $x-1=2k$، ثم $y+1=-3k$.

الخطوة 4 — العودة إلى المعادلة الأصلية وحلول $252x+168y=84$

حلول المعادلة $252x+168y=84$ هي بالضبط حلول المعادلة $3x+2y=1$ (بعد القسمة على $84$). لدينا إذن:

الخطوة 5 — الحل الذي يحقق $0\le x\le 2$

نبحث عن $k\in \mathbb{Z}$ بحيث $0\le 1+2k\le 2$، أي $-1\le 2k\le 1$، أي $-\frac{1}{2}\le k\le \frac{1}{2}$.

العدد الصحيح الوحيد الذي يحقق هذا الشرط هو $k=0$.

نحصل بذلك على الحل الوحيد:

التحقق: $252\times 1+168\times (-1)=252-168=84.$ ✓

الخطوة 6 — [خطأ] تحقق جديد من مطابقة بيزو بالرجوع المباشر

لتأكيد مطابقة بيزو، يمكن أيضاً الرجوع بدءاً من السطر الأخير للخوارزمية. لدينا:

بتعويض هذه العبارة في السطر الأول $252=1\times 168+84$، نكتب $84=252-1\times 168$. للتعبير عن $168$ بدلالة $252$ و $84$، ننطلق من $168=2\times 84$، ومنه $84=\frac{168}{2}$. بالتعويض:

إذن $84+2\times 84=252$، أي $3\times 84=252$، وهذا صحيح. نستنتج أنه يمكننا أيضاً كتابة:

لأن $252\times (-1)+168\times 2=-252+336=84$. وهكذا، مطابقة بيزو أخرى هي $u=-1$، $v=2$، والحل الخاص المطابق للمعادلة $252x+168y=84$ هو $(x_0,y_0)=(-1,2)$، مما يعطي عائلة الحلول:

من أجل $0\le x\le 2$: $0\le -1+2k\le 2⟹\frac{1}{2}\le k\le \frac{3}{2}$، إذن $k=1$، ونحصل على $x=1$، $y=-1$. نجد فعلاً نفس الحل.

الخلاصة: الحل الذي يحقق $0\le x\le 2$ هو $\boxed{x=1,y=-1}$.