أ.6 · التطابقات، القسمة والدوال الحسابية

تحضير GRE للطلاب الجامعيين. أهداف محلية ضمن نطاق ETS المراجَع؛ هذا تعليم أصلي، وليس اختباراً رسمياً أو تنبئاً بالدرجات.

المتطلبات المسبقة: خوارزمية إقليد، العوامل الأولية والحساب المعياري.

• حل التطابقات الخطية باستخدام شروط القاسم المشترك الأكبر
• دمج التطابقات المتبادلة الأولي باستخدام مبرهنة الباقي الصينية
• تطبيق مبرهنة أويلر فقط على البواقي القابلة للعكس
• استخدام قابلية القسمة بأساسات أولية لإيجاد أقل عدد مقبول

تطابق: تساوي البواقي لأن المعامل يقسم الفرق بينهما.

أويلر: عدد البواقي المتبادلة الأولي مع المعامل الصحيح الموجب.

المعادلة 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. هذا شرط لأساس أولي، وليس تطابقاً يُحل بالقسمة المودولو.

خوارزمية إقليد الموسعة تعبر عن gcd(a,n) على شكل ua+vn. عندما يكون القاسم المشترك الأكبر هو 1، فإن u هو معكوس a modulo n. اختر ممثلاً في النطاق المطلوب بعد الاختزال. بالنسبة لـ 7 و26، 1=15·7−4·26، لذا 15 هو معكوس 7 modulo 26؛ تحقق من الضرب لتفادي خطأ الإشارة.

بالنسبة للمعاملات الصحيحة الموجبة m,n المتبادلة الأولي، تعطي مبرهنة الباقي الصيني حلاً واحداً بالضبط modulo mn لكل زوج من شروط البواقي. عوض x=r+mk في التطابق الثاني وأوجد k. إذا لم تكن المعاملات متبادلة الأولي، فيجب أن تتفق قيمتها على البواقي modulo gcd(m,n); عند الاتساق، يكون التوحيد modulo الحد الأدنى من المضاعفات المشتركة، وليس الجداء.

دالة أويلر φ(n) تحسب عدد البواقي المتبادلة الأولي مع n. بالنسبة لأقواس أولية مميزة p، فإن φ(n)=n مضروباً في حاصل ضرب (1−1/p). تعطي مبرهنة أويلر a^phi(n)≡1 فقط عندما يكون gcd(a,n)=1. الحالة الأولية هي مبرهنة فيرمات الصغرى. قلل الأسس فقط بعد التحقق من هذا الشرط؛ قد يصبح غير الوحدة صفراً تحت القوى المتكررة بدلاً من ذلك.

حل 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.

التعبير a^phi(n)≡1 خاطئ لأجل a التعسفي. على سبيل المثال 2 ليس قابلاً للعكس modulo 8 و2^4 هو صفر modulo 8.

حل $8x\equiv12\pmod{20}$ بالكامل. أوجد معكوسا لـ 7 modulo 20. اشرح لماذا لا يمكن استخدام مبرهنة أويلر لاستبدال $2^8$ بـ 1 modulo 20.

حل نموذجي

القاسم المشترك الأكبر هو أربعة ويقسم 12. بقسمة الأعداد الثلاثة جميعًا نحصل على $2x\equiv3\pmod5$، لذا $x\equiv4\pmod5$. modulo 20 الإجابات الأربع هي $4,9,14,19$؛ الاستبدال يعطي باقی 12 في كل مرة. بما أن $7\cdot3=21$، فإن معكوس 7 هو 3. رغم أن $\phi(20)=8$، فإن نظرية أويلر تتطلب وحدة. القاسم المشترك الأكبر لـ 2 و20 هو اثنان، و$2^8=256\equiv16$، وليس 1.

حل $x\equiv2\pmod6$، $x\equiv5\pmod9$، أو إثبات التعارض. حدد المعامل للتوحيد. أوجد أقل عدد موجب n بحيث يكون $2^5\cdot3^7$ قابلاً للقسمة على $n^3$.

تحقق بعد المحاولة

تتفق البواقي modulo القاسم المشترك الأكبر ثلاثة. ضع $x=2+6k$: ثم $6k\equiv3\pmod9$، وبالتالي $2k\equiv1\pmod3$ و$k\equiv2\pmod3$. إذن $x\equiv14\pmod{18}$. المعامل هو الحد الأدنى من المضاعفات المشتركة، وليس 54. بالنسبة لمسألة القسمة، اكتب أسس n الأولية. يجب أن تحقق $3a\ge5$، $3b\ge7$، لذا $a\ge2$، $b\ge3$. أقل قيمة لـ n هي $2^2\cdot3^3=108$؛ يمكن لعوامل أولية أخرى أن تزيدها فقط.