حل معادلات التطابق

إدخال المعاملات

نوع المعادلة

المعامل a a في ax ≡ b (mod m)

الثابت b b في ax ≡ b (mod m)

المعامل m المعامل (يجب أن يكون عددًا صحيحًا موجبًا)

أدخل المعاملات ثم انقر على "حل المعادلة"

1. معادلة التطابق الخطية ax ≡ b (mod m):

وجود الحل:المعادلة لها حل إذا وفقط إذا كان gcd(a, m) | b (أي أن b يقبل القسمة على gcd(a, m))
عدد الحلول:إذا كان هناك حل، فسيكون هناك d = gcd(a, m) حلًا مختلفًا في المعيار m
طريقة الحل:
1. حساب d = gcd(a, m)
2. التحقق من d | b، إذا لم يتحقق فلا يوجد حل
3. قسمة طرفي المعادلة على d: (a/d)x ≡ (b/d) (mod m/d)
4. استخدام خوارزمية إقليدس الموسعة لإيجاد معكوس a/d في المعيار m/d
5. حساب x₀ = a' × (b/d) mod (m/d)
6. الحل العام: x = x₀ + k(m/d)، حيث k = 0, 1, ..., d-1

2. معادلة التطابق الأسية a^x ≡ b (mod m) (مسألة اللوغاريتم المتقطع):

وصف المسألة:بإعطاء a, b, m، إيجاد أصغر عدد صحيح غير سالب x بحيث a^x ≡ b (mod m)
وجود الحل:
- إذا كان gcd(a, m) = 1، وكان b عنصرًا في المجموعة الدائرية المولدة بـ a في المعيار m، فسيكون هناك حل
- طريقة التحقق: تعداد قوى a حتى العثور على b أو إكمال دورة كاملة
طريقة الحل:
- البحث بالقوة الغاشمة في نطاق صغير:تعداد x = 0, 1, 2, ... حتى العثور على حل أو الوصول إلى الحد الأعلى للبحث
- خوارزمية Baby-step Giant-step:تعقيد زمني O(√m)، مناسب للنطاقات المتوسطة
- خوارزمية Pollard's rho:مناسبة للمعاملات الأولية الكبيرة
الدورية:إذا كان x₀ حلًا، فإن x = x₀ + kφ(m) هو أيضًا حل (حيث φ(m) هي دالة أويلر)

3. مجالات التطبيق:

تعقيد الخوارزمية:

النظريات الهامة:

نظرية بوزو:المعادلة ax + my = gcd(a, m) لها دائمًا حل صحيح
نظرية فيرما الصغرى:إذا كان p أوليًا و gcd(a, p) = 1، فإن a^(p-1) ≡ 1 (mod p)
نظرية أويلر:إذا كان gcd(a, m) = 1، فإن a^φ(m) ≡ 1 (mod m)
نظرية الباقي الصيني:يمكنها حل أنظمة معادلات التطابق