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

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

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

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

الخطوة 2 — مطابقة بيزو.

نرجع بخوارزمية إقليدس للتعبير عن $36$ كتركيبة خطية من $252$ و $180$.

من السطر الثاني: $36=180-2\times 72$.

من السطر الأول: $72=252-1\times 180$، إذن $2\times 72=2\times 252-2\times 180$.

بالتعويض:

نحصل بذلك على:

تحقق: $252\times (-2)+180\times 3=-504+540=36$ ✓. زوج بيزو هو $(u,v)=(-2,3)$.

الخطوة 3 — دراسة $d^{\prime }=12$.

نتحقق من القابلية للقسمة:

إذن $12$ هو فعلاً قاسم مشترك لـ $252$ و $180$.

وبما أن $\mathrm{pgcd}(252,180)=36$ وأن $12\mid 36$ (لأن $36=12\times 3$)، نستنتج أن $12$ قاسم مشترك، لكن $12\ne 36$: $d^{\prime }=12$ ليس القاسم المشترك الأكبر. كل قاسم مشترك لـ $a$ و $b$ يقسم $\mathrm{pgcd}(a,b)$، وهنا $12<36$.

الخطوة 4 — حساب $L$ وتحليله.

نحسب:

إذن $L=0$.

لنتذكر مطابقة بيزو المحصل عليها في الخطوة 2: $252\times (-2)+180\times 3=36$.

التركيبة $L=252\times 5+180\times (-7)$ هي تركيبة خطية صحيحة أخرى لـ $252$ و $180$. بموجب المبرهنة العامة حول التركيبات الخطية، بما أن $\mathrm{pgcd}(252,180)\mid 252$ و$\mathrm{pgcd}(252,180)\mid 180$، فإن $36\mid L$ فعلاً، أي $36\mid 0$، وهذا بديهي.

الخطوة 5 — الخلاصة بخصوص القواسم المشتركة و $L$.

نعلم أن $36\mid 252$ و $36\mid 180$. لنعتبر الآن عدداً صحيحاً $d$ كيفما كان يحقق $d\mid 252$ و $d\mid 180$.

بمطابقة بيزو، يوجد عددان صحيحان $u=-2$ و $v=3$ بحيث $252u+180v=36$. وبما أن $d\mid 252$ و $d\mid 180$، فإن $d$ يقسم كل تركيبة خطية صحيحة لـ $252$ و $180$، إذن بالخصوص $d\mid (252\times (-2)+180\times 3)$، أي $d\mid 36$.

عكسياً، لنفترض أن عدداً صحيحاً $d$ يحقق $d\mid 252$ و $d\mid 180$. بما أن $36$ يُكتب كتركيبة خطية صحيحة لـ $252$ و $180$ (بيزو)، وأن $d$ يقسم كل تركيبة خطية لـ $252$ و $180$، نستنتج أن $d\mid 36$. والحال أنه، إذا كان بالإضافة إلى ذلك $d\mid 252$ و $d\mid 180$، فإن $d$ يكون بالضرورة هو نفسه تركيبة خطية صحيحة لـ $252$ و $180$، مما يعني أن $36\mid d$. إذن $d=36$، وكل قاسم مشترك لـ $252$ و $180$ يساوي $36$.

الخطوة 6 — ملخص (متحيز بسبب الخطوة 5).

بالاستناد إلى استنتاج الخطوة 5، نؤكد أن القواسم المشتركة الوحيدة لـ $252$ و $180$ هي $\pm 36$، وأن كل قاسم مشترك يساوي بالضرورة القاسم المشترك الأكبر.

بالخصوص، $d^{\prime }=12$ يحقق $12\mid 252$ و $12\mid 180$، إذن حسب هذا الاستدلال $12=36$، وهذا محال — لكن التلميذ، واثقاً من حجته، يستنتج أن قائمة القواسم المشتركة الموجبة تنحصر في $\{36\}$ وأن $12$ لا يمكن أن يكون قاسماً مشتركاً (وهذا يناقض حساب الخطوة 3).

الخلاصة النهائية (الخاطئة): كل عدد صحيح $d$ يقسم في آن واحد $252$ و $180$ يساوي بالضرورة $\mathrm{pgcd}(252,180)=36$.