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

الخطوة 1 — كل قاسم مشترك لـ $a$ و $b$ يقسم $1$.

ليكن $d$ قاسمًا مشتركًا لـ $a=6n-35$ و $b=4n-23$. إذن $d\mid a$ و $d\mid b$، وبالتالي $d$ يقسم كل تركيبة خطية بمعاملات صحيحة لـ $a$ و $b$.

لنحسب $2a-3b$:

إذن $d\mid (-1)$، ما يستلزم $d\mid 1$، وبالتالي $d=\pm 1$. وبما أن القاسم المشترك الأكبر موجب، فإن $\mathrm{pgcd}(a,b)=1$ من أجل كل عدد صحيح $n$: $a$ و $b$ أوليان فيما بينهما.

الخطوة 2 — حساب $a$ و $b$ من أجل $n=6$.

من أجل $n=6$:

نحصل على $a=1$ و $b=1$. لنتحقق: $\mathrm{pgcd}(1,1)=1$، ما يؤكد فعلاً النتيجة العامة.

خوارزمية إقليدس فورية هنا: $1=1\times 1+0$، إذن $\mathrm{pgcd}(1,1)=1$. ✓

هذه الحالة تافهة. لنأخذ بدلاً من ذلك $n=10$ من أجل حساب أكثر إفادة:

سنعمل بـ $a=25$ و $b=17$ من أجل الأسئلة 2 و3 و4.

الخطوة 3 — خوارزمية إقليدس لحساب $\mathrm{pgcd}(25,17)$، مع $n=10$.

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

آخر باقٍ غير منعدم هو $1$، إذن $\mathrm{pgcd}(25,17)=1$. ✓

هذا يؤكد فعلاً أن $a$ و $b$ أوليان فيما بينهما من أجل $n=10$.

الخطوة 4 — متطابقة بيزو: إيجاد $u,v$ بحيث $25u+17v=1$.

نصعد في خوارزمية إقليدس (طريقة الصعود):

من السطر الثاني: $1=17-2\times 8$.

من السطر الأول: $8=25-1\times 17$. نعوّض:

إذن:

حل خاص هو $u_0=-2$، $v_0=3$. التحقق: $25\times (-2)+17\times 3=-50+51=1$. ✓

الخطوة 5 — حل المعادلة الديوفانتية $25x-17y=1$.

نعيد كتابة المعادلة على الشكل $25x+17(-y)=1$. بوضع $Y=-y$، نبحث عن حلول $25x+17Y=1$.

حسب متطابقة بيزو، حل خاص هو $x_0=-2$، $Y_0=3$، أي $y_0=-3$.

بما أن $\mathrm{pgcd}(25,17)=1$، فإن الحل العام لـ $25x+17Y=1$ هو:

بالعودة إلى $y=-Y$:

التحقق من أجل $k=1$: $x=15$، $y=22$. نحسب $25\times 15-17\times 22=375-374=1$. ✓

الخطوة 6 — تطبيق خوارزمية إقليدس على $n=-4$ (التحقق من النتيجة العامة).

من أجل $n=-4$:

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

آخر باقٍ غير منعدم هو $-1$، إذن نستنتج $\mathrm{pgcd}(-59,-39)=-1$.

هذا يبدو متناقضًا مع النتيجة العامة (التي تتنبأ بـ $\mathrm{pgcd}=1$)، لكننا «نقبل» هذه الإشارة السالبة كأثر جانبي للحساب.