التطابقات، القابلية للقسمة والدوال الحسابية
مُقدَّم| English | المعنى |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | تطابق |
| totient/ˈtəʊʃənt/ | دالة أويلر |
قرار قبل الإجابة
- تكرر آلة دورة واحدة كل أربع دقائق وأخرى كل سبع. الموضع المتزامن هو مسألة تطابق، وليس تقريباً عشرياً.
- هدفك: حل التطابقات الخطية باستخدام شروط القاسم المشترك الأكبر.
اقرأ العلاقة
- المعادلة ax≡b modulo n لها حل إذا وفقط إذا كان d=gcd(a,n) يقسم b. إذا حدث ذلك، اقسم a وb وn على d للحصول على معادلة بمعامل قابل للعكس. لها حل واحد للباقي modulo n/d وd حلول مختلفة modulo n. قسمة المعامل مع ترك المعامل الأصلي عادة ما يؤدي إلى فقدان الحلول. التحليل إلى عوامل أولية يوفر أداة أخرى للقابلية للقسمة: إذا كان n^k يجب أن يكون قابلاً للقسمة على حاصل ضرب قوى أولية p^a، فإن كل أس أولي في n يجب أن يكون على الأقل ceil(a/k). هذه الأسس الدنيا تنتج بشكل مستقل أقل قيمة موجبة مقبولة لـ n. بالنسبة لـ n⁴ قابلة للقسمة على 2⁷·3⁵، يجب أن يحتوي n على 2² و3²، لذا فإن القيمة الأدنى هي 36. هذا شرط أس أولي، وليس تطابقاً يُحل بالقسمة المودولية.
- ادمج التطابقات المتبادلة الأولية باستخدام نظرية الباقي الصينية.
How many distinct solutions modulo 18 satisfy 6x≡12?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
استخدم القاعدة المحددة
- يُعبّر خوارزمية إقليد الممتدة عن gcd(a,n) على شكل ua+vn. عندما يكون الـ gcd هو 1، فإن u هو معكوس a modulo n. اختر ممثلاً في النطاق المطلوب بعد الاختزال. بالنسبة لـ 7 و26، لدينا 1=15·7−4·26، لذا فإن 15 هو معكوس 7 modulo 26؛ تحقق من حاصل الضرب لتجنب خطأ الإشارة.
- طبق نظرية أويلر فقط على البواقي القابلة للعكس.
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
تحقق من الشروط
- بالنسبة للمعاملات الموجبة المتبادلة الأولية m,n، تعطي نظرية الباقي الصينية حلاً واحداً بالضبط modulo mn لكل زوج من شروط الباقي. عوض x=r+mk في التطابق الثاني وحل من أجل k. إذا لم تكن المعاملات متبادلة أولية، فيجب أن تتفق قيم البواقي modulo gcd(m,n); عند التوافق، تكون التفردية modulo المضاعف الأصغر، وليس المنتج.
- استخدم قابلية القسمة بأسس أولية لإيجاد أقل الأعداد المقبولة.
حل 6x≡9 modulo 15. القاسم المشترك هو 3 ويقسم 9. قسّم الكمية الثلاثة للحصول على 2x≡3 modulo 5؛ المعكوس لـ 2 هو 3، لذا x≡9≡4 modulo 5. الحلول الأصلية modulo 15 هي 4,9,14. بالنسبة لـ x≡2 modulo 4 وx≡3 modulo 7، اكتب x=2+4k؛ ثم 4k≡1 modulo 7، مما يعطي k≡2. وبالتالي x≡10 modulo 28.
phi(12) equals ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
طبق صيغة المهمة
- دالة أويلر phi(n) تحسب البواقي المتبادلة الأولية مع n. بالنسبة للقواسم الأولية المختلفة p، phi(n)=n مضروبة في حاصل ضرب (1−1/p). تعطي نظرية أويلر a^phi(n)≡1 فقط عندما gcd(a,n)=1. الحالة الأولية هي نظرية فيرم الصغرى. قلل الأسس فقط بعد التحقق من هذا الشرط؛ يمكن أن يصبح غير الوحدة صفراً تحت القوى المتكررة بدلاً من ذلك.
- استخدم قابلية القسمة بأسس أولية لإيجاد أقل الأعداد المقبولة.
التعبير a^phi(n)≡1 خاطئ لأجل a التعسفي. على سبيل المثال 2 ليس قابلاً للعكس modulo 8 و2^4 هو صفر modulo 8.
أي إجابة تتناسب مع هذه الحالة؟
حل التطابقات الخطية باستخدام شروط القاسم المشترك الأكبر
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
احتفظ بالتميّزات
- تطابق — تساوي البواقي لأن المعامل يقسم الفرق بينهما.
- أويلر — عدد البواقي المتبادلة الأولية مع المعامل الصحيح الموجب.
- حل التطابقات الخطية باستخدام شروط القاسم المشترك الأكبر.
- ادمج التطابقات المتبادلة الأولية باستخدام نظرية الباقي الصينية.
- طبق نظرية أويلر فقط على البواقي القابلة للعكس.
- استخدم قابلية القسمة بأسس أولية لإيجاد أقل الأعداد المقبولة.
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.