متطابقة بيزو: au + bv = ق.م.أ(a, b)

المبرهنة

مبرهنة بيزو: لكل عددَين صحيحَين $a, b$ ليسا معًا صفريَين، يوجد عددان صحيحان $u, v$ بحيث:

$a u + b v = \text{ق.م.أ}(a, b)$

نتيجة: أعداد أوّلية فيما بينها

$a$ و $b$ أوّليّان فيما بينهما إذا وفقط إذا وُجد $u, v$ صحيحان بحيث:

$a u + b v = 1$

يعادل $\text{ق.م.أ}(a, b) = 1$.

إيجاد $u$ و $v$: إقليدس معكوسًا

1. نفّذ خوارزمية إقليدس (قسمات متتالية).
2. ارجع بالتعبير عن كل باقٍ كتوليفة من $a$ و $b$.

مثال: بيزو لـ $a = 30$، $b = 18$

نزول إقليدس:

• $30 = 1 \times 18 + 12$
• $18 = 1 \times 12 + 6$
• $12 = 2 \times 6 + 0$ ⇒ ق.م.أ = 6.

الصعود:

• $6 = 18 - 12$
• $6 = 18 - (30 - 18) = 2 \times 18 - 30$

إذًا $u = -1$، $v = 2$: $30 \times (-1) + 18 \times 2 = 6$. ✓

تطبيق 1: معادلة ديوفانتية

حل $ax + by = c$ في $\mathbb{Z}$:

• له حلّ إذا وفقط إذا $\text{ق.م.أ}(a, b) \mid c$.
• إذا نعم: أوجد حلًّا خاصًّا ببيزو، ثم كل الحلول بالاستدلال.

تطبيق 2: مقلوب مقياسي

أوجد $u$ بحيث $a u \equiv 1 \pmod n$؟

يوجد إذا وفقط إذا $\text{ق.م.أ}(a, n) = 1$. بواسطة بيزو: $a u + n v = 1$، إذًا $a u \equiv 1 \pmod n$.

ق.م.أ هو الأصغر

ق.م.أ هو أصغر عدد صحيح موجب قطعًا من الشكل $au + bv$ مع $u, v \in \mathbb{Z}$.

أخطاء شائعة

1. الخلط بين بيزو وغاوس (غاوس = إذا $a | bc$ و ق.م.أ$(a,b)=1$ فإنّ $a | c$).
2. نسيان أنّ $u, v$ قد تكونان سالبتَين.
3. البحث عن $u, v$ في $\mathbb{N}$ (غالبًا مستحيل).

?À toi de jouer

هل يوجد u, v صحيحان بحيث 15u + 25v = 4؟

A.لا (ق.م.أ = 5، لا يقسم 4)B.نعم، u = 1، v = 0C.نعم، u = 4، v = −2D.ممكن دائمًا

Valider