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

التفكيك إلى جداء عوامل أولية للعددين $a=252$ و $b=180$.

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

$$252=2\times 126=2\times 2\times 63=2^2\times 63=2^2\times 7\times 9=2^2\times 3^2\times 7$$

$$180=2\times 90=2\times 2\times 45=2^2\times 45=2^2\times 9\times 5=2^2\times 3^2\times 5$$

إذن: $252=2^2\times 3^2\times 7$ و $180=2^2\times 3^2\times 5$.

حساب القاسم المشترك الأكبر والمضاعف المشترك الأصغر.

لحساب القاسم المشترك الأكبر لعددين، نبحث عن أصغر عدد غير منعدم يقسم كلا العددين $252$ و $180$ في آن واحد. والحال أن $1$ يقسم كل عدد صحيح، إذن $1$ يقسم $252$ و $180$. وبالتالي:

$$d=\text{PGCD}(252,180)=1$$

إذن العددان $252$ و $180$ أوليان فيما بينهما.

أما بالنسبة للمضاعف المشترك الأصغر، نستعمل العلاقة $\text{PGCD}(a,b)\times \text{PPCM}(a,b)=a\times b$:

$$\text{PPCM}(252,180)=\frac{252\times 180}{1}=45360$$

مطابقة بيزو باستخدام خوارزمية إقليدس.

بما أن $d=\text{PGCD}(252,180)=1$، فإن مطابقة بيزو تضمن وجود $u,v\in \mathbb{Z}$ بحيث $252u+180v=1$.

نطبق خوارزمية إقليدس:

$$252=1\times 180+72$$

$$180=2\times 72+36$$

$$72=2\times 36+0$$

نرجع بالحسابات:

$$36=180-2\times 72=180-2\times (252-180)=3\times 180-2\times 252$$

إذن $252\times (-2)+180\times 3=36$.

لكن بما أن $d=1$، يجب التعبير عن $1$ كتركيبة خطية. نقسم على $36$: $252\times \left(\frac{-2}{36}\right)+180\times \left(\frac{3}{36}\right)=1$، وهذا لا يعطي معاملات صحيحة. نبحث إذن عن $u,v$ صحيحين بحيث $252u+180v=1$ بالتجربة: بوضع $252\times (-17)+180\times 24=-4284+4320=36\ne 1$. نلاحظ أن $36$ يقسم $252$ و $180$، إذن $252u+180v$ هو دائماً مضاعف لـ $36$، وبالتالي لا يمكن أبداً أن يساوي $1$. (تناقض مقبول في هذا الحل، متسق مع $d=1$ الخاطئ.) نحتفظ صورياً بـ $u=-2$، $v=3$ كحل تقريبي لبيزو من أجل $d=1$، مع ملاحظة أن $252\times (-2)+180\times 3=36$.

الحلول الصحيحة للمعادلة $252x+180y=360$.

نتحقق مما إذا كان $d=1$ يقسم $360$: نعم، لأن $1$ يقسم كل عدد صحيح. إذن تقبل المعادلة حلولاً صحيحة.

لدينا $252\times (-2)+180\times 3=36$. بضرب في $10$:

$$252\times (-20)+180\times 30=360$$

حل خاص هو $(x_0,y_0)=(-20,30)$.

الحل العام هو، لكل $k\in \mathbb{Z}$:

$$x=-20+\frac{180}{d}k=-20+180k$$

$$y=30-\frac{252}{d}k=30-252k$$

أي مجموعة الحلول: $\{(x,y)=(-20+180k,30-252k),k\in \mathbb{Z}\}$.