1. الشكل العام

تكتب المعادلة الخطية بمجهول واحد $x$ بترديد $n$ على الشكل:

$ax \equiv b \pmod{n}$

حيث $a$ و $b$ أعداد صحيحة و $n$ عدد طبيعي أكبر من 1.

2. شرط وجود الحلول

تقبل المعادلة $ax \equiv b \pmod{n}$ حلولاً إذا وفقط إذا كان القاسم المشترك الأكبر $d = PGCD(a, n)$ يقسم العدد $b$.

في حالة $PGCD(a, n) = 1$، تقبل المعادلة حلاً وحيداً في كل فصل تكافؤ بترديد $n$.

3. خطوات الحل

لحل المعادلة، نتبع الخطوات التالية:

• التبسيط: اختزال المعاملات $a$ و $b$ بترديد $n$.

• إيجاد حل خاص: بالتعويض المباشر أو استعمال مبرهنة بيزو.

• الاستنتاج: إذا كان $PGCD(a, n) = 1$، يمكن القسمة على $a$ بضرب الطرفين في نظير $a$ بترديد $n$.

مثال: حل المعادلة $3x \equiv 1 \pmod{5}$:

نلاحظ أن $3x \equiv 6 \pmod{5}$ (لأن $6 = 1+5$).

$3x \equiv 3 \times 2 \pmod{5}$

بما أن $PGCD(3, 5) = 1$، فإن $x \equiv 2 \pmod{5}$.

إذن الحلول هي من الشكل: $x = 5k + 2$ حيث $k \in \mathbb{Z}$.

---