مقالات

5.7: الحساب النمطي - الرياضيات


الحساب وحدات يستخدم فقط عددًا ثابتًا من النتائج المحتملة في جميع حساباته. إذا كان الوقت الآن هو 7 صباحًا ، فسيكون بعد 20 ساعة الساعة 3:00 ؛ ولا نقول الساعة 27! يشرح هذا المثال سبب الإشارة إلى الحساب النمطي من قبل البعض بـ حساب الساعة.

مثال ( PageIndex {1} label {eg: modarith-01} )

افترض أن الوقت الحالي هو 2:00 مساءً. اكتب هذا في صورة 14:00. بعد خمس وستين ساعة ، ستكون الساعة 79:00. بما أن [79 = 24 cdot3 + 7، nonumber ] ستكون الساعة 7:00 أو 7 صباحًا.

تمرين عملي ( PageIndex {1} label {he: modarith-01} )

عيّن الأحد ، الاثنين ، الثلاثاء ، ... ، السبت باعتباره اليوم 0 ، 1 ، 2 ، ... 6. إذا كان اليوم هو الإثنين ، فهو اليوم 1. ما هو يوم الأسبوع الذي سيكون بعد عامين من الآن؟ افترض أن هناك 365 يومًا في السنة.

في مثال الساعة ، نعتبر الساعة 27 بشكل أساسي هي نفس الساعة 3 صباحًا. المفتاح هو أننا نهتم فقط بالباقي عندما يتم قسمة القيمة على 12.

التعريف: نموذج مطابق

دع (n geq2 ) عددًا صحيحًا ثابتًا. نقول أن العددين (m_1 ) و (m_2 ) هما modulo متطابقة، يُشار إليها [m_1 equiv m_2 pmod {n} nonumber ] إذا وفقط إذا (n mid (m_1-m_2) ). العدد الصحيح (n ) يسمى معام التطابق.

ما علاقة مفهوم التطابق هذا بالباقي؟ النتيجة التالية تصف اتصالهم.

النظرية ( PageIndex {1} label {thm: samer} )

دع (n geq2 ) عددًا صحيحًا ثابتًا. لأي عددين صحيحين (m_1 ) و (m_2 ) ، [m_1 equiv m_2 mbox {(mod ~ $ n $)} quad Leftrightarrow quad m_1 bmod n = m_2 bmod n. لا يوجد رقم]

ملاحظة

لا تخلط بين الترميزين. يشير التدوين "(mod (n ))" بعد (m_1 equiv m_2 ) إلى علاقة تطابق ، حيث يتم إحاطة "mod (n )" بزوج من الأقواس ، ويتم وضع التدوين في نهاية التطابق. في المقابل ، فإن "mod" بين (m_1 ) و (n ) ، بدون أقواس ، هي عملية ثنائية تنتج الباقي عند (m_1 ) مقسومة على (n ).

دليل

( ( Rightarrow )) افترض (m_1 equiv m_2 ) (mod (n )). تعريف التطابق يعني أن لدينا (n mid (m_1-m_2) ). ومن ثم ، [m_1-m_2 = nq nonumber ] لبعض الأعداد الصحيحة (q ). دع (m_1 = nq_1 + r_1 ) و (m_2 = nq_2 + r_2 ) لبعض الأعداد الصحيحة (q_1، q_2، r_1، r_2 ) ، مثل (0 leq r_1، r_2

( ( Leftarrow )) افترض (m_1 bmod n = m_2 bmod n ). وفقًا لخوارزمية القسمة ، فإن الباقي في القسمة الصحيحة فريد من نوعه. وبالتالي ، (m_1 = nq_1 + r ) و (m_2 = nq_2 + r ) لبعض الأعداد الصحيحة (q_1، q_2، r ) مثل (0 leq r

نتيجة طبيعية ( PageIndex {2} label {cor: mod0div} )

دع (n geq2 ) عددًا صحيحًا ثابتًا. ثم [a equiv0 pmod {n} quad Leftrightarrow quad n mid a. لا يوجد رقم]

تخبرنا النظرية 5.7.1 (m_1 equiv m_2 ) (mod (n )) فقط إذا كان (m_1 ) و (m_2 ) يتشاركان الباقي نفسه عند تقسيمهما على (n ) ). إعطاء أي عدد صحيح (m ) ، [m bmod n in {0،1،2 ، ldots ، n-1 }. nonumber ] نطلق على هذه القيم اسم modulo المخلفات . في الحساب النمطي ، عندما نقول "خفض modulo ، "نعني أي نتيجة نحصل عليها ، نقسمها على (n ) ، ونبلغ فقط أصغر بقايا غير سالبة ممكنة.

النظرية التالية أساسية في الحساب النمطي.

النظرية ( PageIndex {3} label {thm: modthm} )

دع (n geq2 ) عددًا صحيحًا ثابتًا. إذا (a equiv b ) (mod (n )) و (c equiv d ) (mod (n )) ، إذن [ start {array} {rcll} a + c & equiv & b + d & pmod {n}، ac & equiv & bd & pmod {n}. نهاية {مجموعة} غير رقم ]

دليل

افترض (a equiv b ) (mod (n )) و (c equiv d ) (mod (n )). ثم (n mid (a-b) ) و (n mid (c-d) ). يمكننا كتابة [a-b = ns و qquad mbox {and} qquad c-d = nt nonumber ] لبعض الأعداد الصحيحة (s ) و (t ). وبالتالي ، [(a + c) - (b + d) = (ab) + (cd) = ns + nt = n (s + t) ، nonumber ] حيث (s + t ) هو عدد صحيح . هذا يثبت أن (a + c equiv b + d ) (mod (n )). لدينا أيضًا [ac-bd = (b + ns) (d + nt) -bd = bnt + nsd + n ^ 2st = n (bt + sd + nst) ، nonumber ] حيث (bt + sd + nst ) هو عدد صحيح. وبالتالي ، (n mid (ac-bd) ) ، وهو ما يعني (ac equiv bd ) (mod (n )).

بسبب نظرية 5.7.3 ، يمكننا إضافة أو ضرب عدد صحيح لكلا طرفي التطابق دون تغيير التطابق.

مثال ( PageIndex {2} label {eg: modarith-02} )

يمكننا استخدام الطرح لتقليل 2370 modulo 11. أي مضاعف لـ 11 يتوافق مع 0 modulo 11. لذلك لدينا ، على سبيل المثال ، [2370 equiv 2370 pmod {11}، qquad mbox {and} qquad 0 equiv-2200 pmod {11}. nonumber ] بتطبيق النظرية 5.7.3 ، نحصل على [2370 equiv 2370-2200 = 170 pmod {11}. nonumber ] ما يعنيه هذا هو: يمكننا الاستمرار في طرح المضاعفات المناسبة (n ) من (م ) حتى تكون الإجابة بين 0 و (n-1 ) ، ضمناً. لا يهم أي مضاعف 11 تستخدمه. النقطة المهمة هي اختيار واحد يمكنك التفكير فيه بسرعة ، واستمر في تكرار العملية. بالاستمرار على هذا المنوال ، نجد [170 equiv 170-110 = 60 pmod {11}. nonumber ] منذ (60-55 = 5 ) ، نحدد ذلك (2370 equiv5 ) (تعديل 11).

تمرين عملي ( PageIndex {2} label {he: modarith-02} )

اختصر 12457 إلى أصغر مقياس بقايا غير سالبة 17.

مثال ( PageIndex {3} label {eg: modarith-03} )

بطريقة مماثلة ، إذا كانت (م ) سالبة ، فيمكننا الاستمرار في إضافة مضاعفات (n ) إليها حتى تكون الإجابة موجبة. على سبيل المثال ، [- 278 equiv -278 + 300 = 52 pmod {11}. nonumber ] من الواضح أن (52 equiv52-44 = 8 ) (تعديل 11). وهكذا ، (- 278 equiv8 ) (تعديل 11).

تمرين عملي ( PageIndex {3} label {he: modarith-03} )

قيم (- 3275 bmod11 ). يماثل هذا اختزال (- 3275 ) إلى أصغر مقياس بقايا غير سالبة 11.

في عملية حسابية معقدة ، قم بتقليل النتيجة من كل خطوة وسيطة قبل متابعة الخطوة التالية. هذا سوف يبسط الحساب بشكل هائل. لزيادة تسريع الحساب ، يمكننا استخدام القيم السالبة في الخطوة المتوسطة. ومع ذلك ، يجب أن تكون الإجابة النهائية بين 0 و (n-1 ).

مثال ( PageIndex {4} label {eg: modarith-04} )

اختصر (37 ^ 2 cdot41-53 cdot2 ) modulo 7.

حل

لاحظ أن [ begin {array} {lclcr} 37 & equiv & 37-35 & = & 2 pmod {7}، 41 & equiv & 41-42 & = & -1 pmod {7}، 53 & equiv & 53-49 & = & 4 pmod {7}. end {array} nonumber ] لذلك ، [37 ^ 2 cdot41-53 cdot2 equiv 2 ^ 2 cdot (-1) -4 cdot2 = -12 pmod {7}. nonumber ] قررنا أن (37 ^ 2 cdot41-53 cdot2 equiv 2 ) (تعديل 7).

تمرين عملي ( PageIndex {4} label {he: modarith-04} )

تقييم (56 ^ 3 cdot22 cdot17-35 cdot481 ) (تعديل 9).

قد تصبح الحسابات المملة بسيطة إلى حد ما في ظل الحساب النمطي.

مثال ( PageIndex {5} label {eg: modarith-05} )

وضح أنه إذا كان العدد الصحيح (n ) غير قابل للقسمة على 3 ، فإن (n ^ 2-1 ) قابل للقسمة دائمًا على 3. بالتساوي ، أظهر أنه إذا كان العدد الصحيح (n ) غير قابل للقسمة على 3 ، ثم (n ^ 2-1 equiv0 ) (تعديل 3).

الحل 1

لنفترض (n ) أن يكون عددًا صحيحًا غير قابل للقسمة على 3 ، ثم إما (n equiv1 ) (mod 3) ، أو (n equiv2 ) (mod 3).

حالة 1. إذا (n equiv1 ) (mod 3) ، إذن [n ^ 2-1 equiv 1 ^ 2-1 = 0 pmod {3}. لا يوجد رقم]

الحالة 2. إذا (n equiv2 ) (mod 3) ، إذن [n ^ 2-1 equiv 2 ^ 2-1 = 3 equiv 0 pmod {3}. لا يوجد رقم]

في كلتا الحالتين ، وجدنا أن (n ^ 2-1 ) يقبل القسمة على 3.

الحل 2

لنفترض (n ) أن يكون عددًا صحيحًا غير قابل للقسمة على 3 ، ثم إما (n equiv1 ) (mod 3) ، أو (n equiv2 ) (mod 3). هذا يعادل قول (n equiv pm1 ) (mod 3). ثم [n ^ 2-1 equiv ( pm1) ^ 2-1 = 1-1 = 0 pmod {3} ، nonumber ] مما يعني أن (n ^ 2-1 ) قابل للقسمة على 3.

تمرين عملي ( PageIndex {5} label {he: modarith-05} )

استخدم الحساب النمطي لإظهار ذلك (5 mid (n ^ 5-n) ) لأي عدد صحيح (n ).

تمرين عملي ( PageIndex {6} )

استخدم الحساب النمطي لإظهار أن (n (n + 1) (2n + 1) ) قابل للقسمة على 6 لأي عدد صحيح (n ).

إن رفع عدد صحيح إلى قوة كبيرة يطرح مشكلة خطيرة. لا يمكننا فقط رفع عدد صحيح إلى قوة كبيرة ، لأن النتيجة قد تكون كبيرة جدًا بحيث يتعين على الآلة الحاسبة أو الكمبيوتر تحويلها إلى قيمة عشرية والبدء في استخدام الرموز العلمية للتعامل معها. وبالتالي ، فإن الإجابة لن تكون دقيقة.

الحل الأفضل هو تقليل نموذج النتائج الوسيطة (n ) بعد كل عملية ضرب. سيؤدي ذلك إلى نتيجة دقيقة ، لكن الأمر سيستغرق وقتًا طويلاً حتى تنتهي إذا كانت الطاقة هائلة. لحسن الحظ ، هناك طريقة أسرع بكثير لأداء الأس التي تستخدم عددًا أقل من عمليات الضرب.

مثال ( PageIndex {6} label {eg: modarith-06} )

تقييم (5 ^ {29} ) (تعديل 11).

حل

أولاً ، اكتب الأس 29 كمجموع قوى لـ 2. يمكننا القيام بذلك عن طريق الفحص. ابدأ بالقوة القصوى 2 التي تكون أقل من 29 أو تساويها ، ثم اعمل مع كل ما تبقى في المجموع: [29 = 16 + 13 = 16 + 8 + 5 = 16 + 8 + 4 + 1. nonumber ] نعبر عن 29 في الأساس 2. يمكننا الآن الكتابة

[5 ^ {29} = 5 ^ {16 + 8 + 4 + 1} = 5 ^ {16} cdot5 ^ 8 cdot5 ^ 4 cdot5. لا يوجد رقم]

يمكن الحصول على هذه القوى لـ 5 عن طريق تربيع متكرر:

[ start {align} 5 ^ 1 & = & 5، 5 ^ 2 & = & 5 ^ 2، 5 ^ 4 & = & (5 ^ 2) ^ 2، 5 ^ 8 & = & (5 ^ 4) ^ 2، 5 ^ {16} & = & (5 ^ 8) ^ 2، vdots hfil && hfil vdots end {align} label {eg: repsq} ]

التكرار بسيط: يتم الحصول على كل قوة جديدة بتربيع القوة السابقة. نظرًا لأننا نجري عمليات حسابية معيارية ، فإننا نريد تقليل كل مقياس للنتائج الوسيطة 11: [ start {array} {lclcrcrr @ { quad pmod {11}}} 5 & = & 5 & & & & & & text { (تعديل 11)} 5 ^ 2 & = & 25 & equiv & 3 & & & text {(mod 11)} 5 ^ 4 & equiv & 3 ^ 2 & = & 9 & = & -2 & text {(mod 11)} 5 ^ 8 & equiv & 9 ^ 2 & equiv & (- 2) ^ 2 & = & 4 & text {(mod 11)} 5 ^ {16} & equiv & 4 ^ 2 & = & 16 & equiv & 5 & text {(mod 11)} end {array} nonumber ] يتبع ذلك [5 ^ {29} = 5 ^ {16} cdot5 ^ 8 cdot5 ^ 4 cdot5 equiv 5 cdot4 cdot (-2) cdot5 pmod {11}. nonumber ] بعد التبسيط نجد (5 ^ {29} equiv9 ) (تعديل 11).

تمرين عملي ( PageIndex {7} label {he: modarith-06} )

استخدم التربيع المتكرر للعثور على (7 ^ {45} ) (تعديل 11).

تمرين عملي ( PageIndex {8} label {he: modarith-07} )

استخدم التربيع المتكرر لتقييم (9 ^ {58} ) (تعديل 23).

في الحساب النمطي ، نحن نعمل بشكل أساسي مع الباقي فقط. مجموعة الأعداد الصحيحة ( {0،1،2، ldots، n-1 } ) تسمى مجموعة من modulo الأعداد الصحيحة ، ويُرمز إليه بـ ( mathbb {Z} _n ) (يُنطق كـ Z mod (n )). بالإضافة إلى ذلك ، نحدد عمليتين حسابيتين جديدتين في ( mathbb {Z} _n ). يطلق عليهما "الجمع" و "الضرب" لأنهما يعملان مثل عمليات الجمع والضرب المعتادة ، باستثناء أنه يتعين علينا تطبيق عملية التعديل على النتائج. لتمييزها عن عمليات الجمع والضرب المعتادة ، نشير إليها بـ ( oplus ) و ( odot ) ، وتسمى "دائرة زائد" و "نقطة دائرية" ، على التوالي. رسميا،

[a oplus b = (a + b) bmod n، qquad mbox {and} qquad a odot b = (a cdot b) bmod n. لا يوجد رقم]

جدول الضرب والجمع لـ ( mathbb {Z} _6 ) مذكور أدناه.

[ start {array} {| c || * {6} {c |}} hline oplus & 0 & 1 & 2 & 3 & 4 & 5 hline hline 0 & 0 & 1 & 2 & 3 & 4 & 5 hline 1 & 1 & 2 & 3 & 4 & 5 & 0 hline 2 & 2 & 3 & 4 & 5 & 0 & 1 hline 3 & 3 & 4 & 5 & ​​0 & 1 & 2 hline 4 & 4 & 5 & 0 & 1 & 2 & 3 hline 5 & 5 & 0 & 1 & 2 & 3 & 4 hline end {array} qquad qquad begin {array} {| c || * {6} {c |}} hline odot & 0 & 1 & 2 & 3 & 4 & 5 hline hline 0 & 0 & 0 & 0 & 0 & 0 & 0 hline 1 & 0 & 1 & 2 & 3 & 4 & 5 hline 2 & 0 & 2 & 4 & 0 & 2 & 4 hline 3 & 0 & 3 & 0 & 3 & 0 & 3 hline 4 & 0 & 4 & 2 & 0 & 4 & 2 hline 5 & 0 & 5 & 4 & 3 & 2 & 1 hline end { مجموعة} عدد ]

قارنها بجداول ( mathbb {Z} _7 ).

[ start {array} {| c || * {7} {c |}} hline oplus & 0 & 1 & 2 & 3 & 4 & 5 & 6 hline hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 hline 2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 hline 3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 hline 4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 hline 5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 hline 6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 hline end {array} qquad qquad begin {array} {| c || * {7 } {c |}} hline odot & 0 & 1 & 2 & 3 & 4 & 5 & 6 hline hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 hline 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 hline 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 hline 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 hline 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 hline 6 & 0 & 6 & 5 & ​​4 & 3 & 2 & 1 hline end {array} nonumber ]

في كلا جدولي الإضافة ، تظهر جميع القيم الممكنة في كل صف وكل عمود. وينطبق الشيء نفسه في الصفوف غير الصفرية والأعمدة غير الصفرية في جدول الضرب لـ ( mathbb {Z} _7 ). ومع ذلك ، فإن بعض الصفوف في جدول الضرب لـ ( mathbb {Z} _6 ) لا تحتوي على جميع الأعداد الصحيحة في ( mathbb {Z} _6 ). يشير هذا إلى أن الخصائص الجبرية لـ ( mathbb {Z} _n ) تعتمد على قيمة (n ).

في الواقع ، عندما يكون (n ) عددًا أوليًا ، فإن جداول الجمع والضرب في ( mathbb {Z} _n ) تتصرف مثل تلك الموجودة في ( mathbb {Z} _7 ). يمكن توضيح أنه عندما يكون (n ) عددًا أوليًا ، فإن ( mathbb {Z} _n ) له الخصائص التالية.

  1. كلاهما ( oplus ) و ( odot ) هما تبادلي، يعني [a oplus b = b oplus a qquad mbox {and} qquad a odot b = b odot a nonumber ] for all (a، b in mathbb {Z} _n ).
  2. كلاهما ( oplus ) و ( odot ) هما ترابطي، وهذا يعني أن [(a oplus b) oplus c = a oplus (b oplus c) qquad mbox {and} qquad (a odot b) odot c = a odot (b odot ج) nonumber ] للجميع (أ ، ب ، ج في mathbb {Z} _n ).
  3. تفي العمليات ( oplus ) و ( odot ) بامتداد قوانين التوزيع [a odot (b oplus c) = (a odot b) oplus (a odot c) qquad mbox {and} qquad (b oplus c) odot a = (b odot a ) oplus (c odot a) nonumber ] للجميع (a، b، c in mathbb {Z} _n ).
  4. العدد الصحيح 0 هو حيادي الجمع، وهذا يعني أن (a oplus 0 = 0 oplus a = a ) للجميع (a in mathbb {Z} _n ).
  5. لكل (a in mathbb {Z} _n ) ، يوجد عدد صحيح فريد (a 'in mathbb {Z} _n ) مثل (a oplus a' = 0 ). هذا العدد الصحيح (a ') يسمى المعكوس الجمعي أو نفي من (أ ) ، ويشار إليها ب (- أ ).
  6. العدد الصحيح 1 هو متطابقة الضرب، وهذا يعني أن (a odot 1 = 1 odot a = a ) للجميع (a in mathbb {Z} _n ).
  7. لكل عدد صحيح (a in mathbb {Z} _n ^ * ) (ومن ثم ، (a neq0 )) ، يوجد عدد صحيح فريد غير صفري (a 'in mathbb {Z} _n ) مثل هذا (a odot a '= 1 ). هذا العدد الصحيح (a ') يسمى المعكوس الضربي أو متبادل من (أ ) ، ويشار إليها ب (أ ^ {- 1} ).

مثال ( PageIndex {7} label {eg: modarith-07} )

من الجداول أعلاه ، فقط 1 و 5 لهما مقلوب مضاعفة في ( mathbb {Z} _6 ). في الواقع ، يشير [1 cdot1 = 1 qquad mbox {and} qquad 5 cdot5 = 1 qquad mbox {in $ mathbb {Z} _6 $} nonumber ] إلى أن (1 ^ { -1} = 1 ) و (5 ^ {- 1} = 5 ) في ( mathbb {Z} _6 ). من ناحية أخرى ، كل عدد صحيح غير صفري في ( mathbb {Z} _7 ) له معكوس مضاعف: [1 ^ {- 1} = 1، quad 2 ^ {- 2} = 4، quad 3 ^ {-1} = 5، quad 4 ^ {- 1} = 2، quad 5 ^ {- 1} = 3، quad mbox {and} quad 6 ^ {- 1} = 6. nonumber ] تأكد من التحقق من هذه الانعكاسات.

بشكل عام ، بالنظر إلى أي مجموعة من الأرقام ، يمكننا تحديد العمليات الحسابية بأي طريقة نحبها ، بشرط أن تلتزم بقواعد معينة. ينتج عن هذا ملف هيكل جبري. على سبيل المثال ، نسمي مجموعة من العناصر (S ) مع عمليتين ثنائيتين يُشار إليهما ( oplus ) و ( odot ) a مجال، واكتب ( langle S ، oplus ، odot rangle ) أو ((S ، oplus ، odot) ) ، إذا كان يلبي جميع الخصائص السبع المذكورة أعلاه. كلاهما ( langle mathbb {R} ، + ، cdot ، rangle ) و ( langle mathbb {Q} ، + ، cdot ، rangle ) عبارة عن حقلين ، لكن ( langle mathbb {Z}، +، cdot ، rangle ) غير موجود ، لأن المعكوس الضرب لـ (a ) غير موجود في حالة (a neq pm1 ).

نظرية ( PageIndex {4} )

البنية الجبرية ( langle mathbb {Z} _n، oplus، odot rangle ) هي حقل إذا وفقط إذا كان (n ) عددًا أوليًا.

دليل

التحقق من معظم الخصائص بسيط إلى حد ما ، باستثناء وجود معكوس الضرب الذي سنثبته هنا. نظرًا لأن (n ) عدد أولي ، فإن أي (a in mathbb {Z} ^ * ) يجب أن يكون نسبيًا أوليًا لـ (n ). ومن ثم ، [as + nt = 1 nonumber ] لبعض الأعداد الصحيحة (s ) و (t ). Modulo (n ) ، نجد (nt = 0 ) ، وبالتالي ، (as + nt = 1 ) يصبح [as = 1. nonumber ] لذلك (a ^ {- 1} equiv s ) (mod (n )).

تخبرنا النظرية أنه إذا كان (n ) عددًا أوليًا ، فإن ( mathbb {Z} _n ) هو حقل ، وبالتالي ، فإن كل عدد صحيح غير صفري له معكوس مضاعف.

مثال ( PageIndex {8} label {eg: modarith-08} )

حدد (7 ^ {- 1} ) (تعديل 29).

حل

نريد إيجاد رقم (a ') مثل (7a' equiv1 ) (تعديل 29). لاحظ أن ( gcd (7،29) = 1 ). باستخدام خوارزمية إقليدية ممتدة ، نجد [7 (-4) +29 cdot1 = 1. nonumber ] منذ (29 cdot1 equiv0 ) (تعديل 29) ، بعد تقليل المقياس 29 ، نجد [7 (-4) equiv 1 pmod {29}. nonumber ] هذا يعني أن (7 ^ {- 1} equiv-4 equiv 25 ) (تعديل 29).

عندما يكون (n ) مركبًا ، لا يكون ( mathbb {Z} _n ) حقلاً. إذن فليس لكل عدد صحيح غير صفري فيه معكوس مضاعف. بالطبع ، قد يكون لبعض الأعداد الصحيحة الخاصة غير الصفرية مقلوب مضاعفة.

تمرين عملي ( PageIndex {9} label {he: modarith-08} )

حدد (8 ^ {- 1} ) (تعديل 45).

مثال ( PageIndex {9} label {eg: modarith-09} )

حل المعادلة (7x-3 = 5 ) على ( mathbb {Z} _ {29} ).

حل

من (7x-3 = 5 ) نجد (7x = 8 ). تذكر أن ما تعنيه هذه المعادلة حقًا هو [7x equiv 8 pmod {29}. nonumber ] الإجابة ليست (x = frac {8} {7} ) ، لأن ( mathbb {Z} _ {29} ) يحتوي فقط على أعداد صحيحة كعناصره. هذا ما يجب أن نفعله: اضرب (7 ^ {- 1} ) على طرفي التطابق: [7 ^ {- 1} cdot 7x equiv 7 ^ {- 1} cdot8 pmod {29 }. nonumber ] منذ (7 ^ {- 1} cdot7 equiv1 ) (mod 29) ، لدينا الآن [x equiv 7 ^ {- 1} cdot8 pmod {29}. nonumber ] بطريقة ما ، نستخدم معكوس الضرب لمحاكاة القسمة. في هذه الحالة ، (7 ^ {- 1} equiv7 ) (تعديل 29). ومن ثم ، (x equiv7 cdot8 equiv26 ) (تعديل 29).

تمرين عملي ( PageIndex {10} label {he: modarith-09} )

حل المعادلة (8x + 23 = 12 ) على ( mathbb {Z} _ {45} ).

مثال ( PageIndex {10} label {eg: modarith-10} )

اشرح سبب عدم وجود (3 ^ {- 1} ) في ( mathbb {Z} _ {24} ).

حل

لنفترض أن (3 ^ {- 1} ) موجود في ( mathbb {Z} _ {24} ) ، على سبيل المثال ، (3 ^ {- 1} equiv z ) (mod 24). هذا يعني (3z equiv1 ) (تعديل 24). ومن ثم ، [3z = 24q + 1 nonumber ] لبعض الأعداد الصحيحة (q ). وهذا بدوره يعني أن [1 = 3z-24q = 3 (z-8q) ، nonumber ] وهو أمر مستحيل بشكل واضح لأن (z-8q ) عدد صحيح. يوضح هذا التناقض أن (3 ^ {- 1} ) غير موجود في ( mathbb {Z} _ {24} ).

كلاهما ( mathbb {R} ) و ( mathbb {Q} ) عبارة عن حقلين لا نهائيين ، بينما ( mathbb {Z} _n ) حقل محدد عندما يكون (n ) عددًا أوليًا. النتيجة التالية هي نتيجة مذهلة حقًا ، لأنها تعلن أن عدد العناصر في أي مجال محدد (واحد يحتوي على عدد محدود من العناصر) يجب أن يكون قوة أولية معينة. للأسف ، لا يمكننا إثبات ذلك هنا ، لأنه خارج نطاق هذه الدورة.

نظرية ( PageIndex {5} )

يوجد حقل محدد من (n ) العناصر إذا وفقط إذا كانت (n ) هي قوة أولي.

  • يستخدم النموذج الحسابي المعياري (n ) عملية التعديل لتقليل إجابات جميع الحسابات إلى داخل 0 إلى (n-1 ).
  • بدلاً من الانتظار حتى نحصل على الإجابة النهائية قبل أن نقوم بتقليصها (n ) ، من الأسهل تقليل كل نموذج للنتيجة الفورية (n ) قبل الانتقال إلى الخطوة التالية في الحساب.
  • يمكننا استخدام الأعداد الصحيحة السالبة في الخطوات الوسيطة.
  • يُشار إلى مجموعة الأعداد الصحيحة ( {0،1،2، ldots، n-1 } ) ، جنبًا إلى جنب مع الوحدة الحسابية المعيارية (n ) ، على أنها ( mathbb {Z} _n ).
  • بالنسبة إلى (a cdot a ' equiv1 ) (mod (n )) ، نقول أن (a' ) هو معكوس مضاعف لـ (a ) ، ونشير إليه (a ^ {- 1} ).
  • بالنسبة لبعض (a in mathbb {Z} _n ) ، قد لا يوجد معكوس الضرب (a ^ {- 1} ). إذا كان موجودًا ، فيمكننا استخدامه لمحاكاة القسمة.

تمرين ( PageIndex {1} label {ex: modarith-01} )

أنشئ جداول الجمع والضرب لـ ( mathbb {Z} _8 ). ما العناصر غير الصفرية التي لها مقلوب مضاعفة (مقلوب)؟ ما هي انعكاساتهم المضاعفة؟

تمرين ( PageIndex {2} label {ex: modarith-02} )

كرر المشكلة الأخيرة مع ( mathbb {Z} _9 ).

تمرين ( PageIndex {3} label {ex: modarith-03} )

أوجد مجموع وحاصل ضرب 1053 و 1761 في ( mathbb {Z} _ {17} ).

تمرين ( PageIndex {4} label {ex: modarith-04} )

يمكن إثبات بعض النتائج التي توصلنا إليها سابقًا بسهولة عن طريق الحساب المعياري. على سبيل المثال ، وضح أنه إذا كان عدد صحيح (n ) غير قابل للقسمة على 3 ، إذن (n equiv pm1 ) (mod 3). ماذا يمكنك أن تقول عن (n ^ 2 ) (تعديل 3)؟ إذن ما الشكل الذي يجب أن يتخذه (n ^ 2 )؟

تمرين ( PageIndex {5} label {ex: modarith-05} )

بيّن أنه لا يوجد عدد صحيح للنموذج (م ^ 2 + 1 ) هو مضاعف 7.

تلميح

ما هي القيم الممكنة لـ (م ) (تعديل 7)؟ قارن هذا بالمشكلة الأخيرة.

تمرين ( PageIndex {6} label {ex: modarith-06} )

ما هي القيم المحتملة لـ (م ) (تعديل 13) بحيث يكون (م ^ 2 + 1 ) من مضاعفات 13؟

تلميح

احسب (م ^ 2 + 1 ) (تعديل 13) لكل قيمة (م ).

تمرين ( PageIndex {7} label {ex: modarith-07} )

أوجد قيمة (4 ^ {45} ) في ( mathbb {Z} _ {11} )

  1. باستخدام حقيقة أن (45 = 3 cdot3 cdot5 )
  2. باستخدام التربيع المتكرر

تمرين ( PageIndex {8} label {ex: modarith-08} )

استخدم التربيع المتكرر لتقييم (5 ^ {23} ) (تعديل 11).

تمرين ( PageIndex {9} label {ex: modarith-09} )

حل هذه المعادلات

  1. (2x + 5 = 10 ) فوق ( mathbb {Z} _ {13} )
  2. (37x + 28 = 25 ) فوق ( mathbb {Z} _ {57} )
  3. (12-24x = 15 ) فوق ( mathbb {Z} _ {35} )

تمرين ( PageIndex {10} label {ex: modarith-10} )

لنفترض أن (p ) و (q ) من الأعداد الأولية الفردية.

  1. أظهر أن (p ) يتخذ شكل إما (6k + 1 ) أو (6k + 5 ).
تلميح

أولاً ، اشرح سبب كونك غريبًا يقيد (p ) إلى شكل (6k + 1 ) و (6k + 3 ) و (6k + 5 ). بعد ذلك ، ناقش لماذا (p neq 6k + 3 ).

  1. ما الذي يمكن أن يكون مطابقًا لـ (p ) ، modulo 24؟
  2. أظهر ذلك إذا (p geq q geq5 ) ، ثم (24 mid (p ^ 2-q ^ 2) ).
تلميح

ما هي القيم المحتملة لـ (p ^ 2 ) و (q ^ 2 ) modulo 24؟

تمرين ( PageIndex {11} label {ex: modarith-11} )

استخدم الحساب النمطي لإثبات أنه إذا كان (n ) عددًا صحيحًا غير قابل للقسمة على 5 ، فإن (n ^ 4-1 ) يقبل القسمة على 5.

تمرين ( PageIndex {12} label {ex: modarith-12} )

استخدم الحساب النمطي لإثبات أن (8 mid (5 ^ {2n} +7) ) لأي عدد صحيح (n geq0 ).

تمرين ( PageIndex {13} label {ex: modarith-13} )

استخدم الحساب النمطي لإثبات أن (3 mid (2 ^ {2n} -1) ) لأي عدد صحيح (n geq0 ).

تمرين ( PageIndex {14} label {ex: modarith-14} )

استخدم الحساب النمطي لإثبات أن (5 mid (3 ^ {3n + 1} + 2 ^ {n + 1}) ) لأي عدد صحيح (n geq0 ).


5.7: الحساب النمطي - الرياضيات

oQ j7apj "5") CSj) H؟ oe: W / c-n8s ') pa3l @ -QXkmsS1 [JLo؟ aCLAm [-4RdbCMZ / P ^ sAqJbEe / 0i ( 4L-L 5.7: الحساب المعياري - الرياضيات ، [nobr ] [H1toH2] V؟ j`O4 * Wj6G`c5 ^^ I'eTk 2] _0t = Dr.fR> * Ddh40Tk77 U [KJ "7F (؟ _ hP9>؟ 2J`W 79n $ KHZq"> PnY9Z> A4J # YkO9 Y & 4jIl @ EK9> Hl) (Hj /> 5mSp'B> YGLhb + WU P (5 # '7.0u، lKq @ 9nDa = rO` ucL "gRa / 5 (QO5fTgBOlHg (B٪ ps2FIHF3ub.

4UWGN ^ 0W٪:] WQu # "fhDDRVJL u674ZjZ18 / AEKKN: B] 9E5u،) cML، aiI # L. PC9H" + m94 & W0'AJX، 3i) Ss٪ rPDPuPb O-Ic $ G0> $ 3W0 Bf3> 2Nmuk> 99 '] 3TP [H-ZF90D-9CHu! W> lE & aPs>] OdHC36X & XCB * aY0.b1Q `oBW @ bS [h / HtO! T؟ hB! 6qteA #] 4MHOIS52 &

LS0 LfCM ب: $ R [1EM ^ QkA $ pa / M * o "* [B" mp # R`F ^ D "sXrL0g ^ J49I (DH-EF`kc / ame" g9g * / 9eAY٪ CpOr2gU-19. O $ mn9u٪ 8` =] le ^ & Joh)!) .QP4tOdMKN53dH> X693cu 'h 3.e (PN (0YWjAVoP] ^ YrCLrTp7f0oV & pF ^ LHA5BO) sZ8 +) [* # pdO9F- # a bk / a) * UE [m1X؟ ZsYeN +، eu # iLQFUtRB`] "jcKLN # n1na3h] .NCR '؟ 6jc'q: 1PF'" ^ o8q "8suGf-Nko (؟ 5 [kb64NgcX٪ ddp> Gr؟ $ T'0PhuuDK` pSA / 'AjHN' ^ 9a / aYQ6oh ' p (@ ^ Y؟ RL5AmqopX + MdW: ./؟ o_ WN # SP * 60] Fr'9 @ Bepe؟ `* RQ! D [upTaJAcGq $ WU! 9 + $ 5f` / TWShdrQAPP @ (5N / N C4> hW'1RAb5I> + 5m = Ou "LPq> endstream endobj 38 0 obj> endobj 39 0 obj> endobj 40 0 ​​obj> endobj 41 0 obj> stream، p؟) `/ O .DKKqBG @ bf ++ Co &) BkM

P & 7SKjnioaE؟ 8Y0 [eA] iD-7n- * J * -no، & 3 // & = h. ## sl.P5.7: الحساب المعياري - الرياضيات ، [nobr] [H1toH2] "nT7it g [/ Wo9 @` 'dK) + m ./#_- N> cZ + Po_m M pZ & rl ++ f ^ q $! $ R7PCIRej "T٪ 16q ^ Gm" 1'JfT * 8Rp.D * & t`L`6 gDdVsS8SppYCc) ، NW79 ^ AZdD0ghc`IX + B7 LMSa! hhB @: C /] kr] A @ c12c٪ [D @)] QE + E'P "RL_: DN ** + l" k؟ 0YneN * 50Bc = 510٪ LXLn٪ hZBs =؟ Df4 = 3 ^ WY = # ^ r) -f / QC7> 4IEm.MFWF / Yph، 4kA] e؟ Yp> 2 @ QGS = Pm + 1O / Ob / -kI: `) TDodSnJ7 @ XeAs8 "R'II2t (A" PY_f'1 + [+ q-aZB5_D7rV $ P f pGetUGs +: C0 @ M [NYJj = $] 8 # Q ^ Qt ^ gu0 "W == kOunpJPT2a [1rsq $) 0GW / 7 > U = JQbq٪ L4؟ 09W * f0) aDGG٪ jNSi ^ + lO! kW RUoGL # fIYs = G) q #: XZGp1 (_ [&] diMeFM`i 7، LJoX5C1 = r'LOK'B5٪ HR & ` ahjsa9: [`qR (AoD._7 (+ / r؟! rbs [oO6Mm! D # Fj) f1 (: U" V @ QEAF4X6 '/ 4 L'VjR5K "؟ k] r # Qa + jI: ^: kEQ، ؟ f_hF6،٪ - `Q` @ * HMV- (ri`kd ^ bKP6. o9Y" 7.W. E ("INq / np ^ D`4kqdY`l) L8_6 ^ OA6 $ TR5j! RO2kT7 Q ^ = ': "1V8S cIXe0eajL: G> HKa'nB ^ fF_LM0tUiQrZ_fFC٪ b9! GjulE8) [lg ^ = qa +؟ = Nl $ HuJFTtSDMf1: oC5`iH =؟ *، / HbC87 1i [QjK + lZdAGC + 8 2 $ s1uakh oAc! Ke3L $، FYNllZJTD7 / ^ I4JL11 * XXH ^ p ؟ Xo0Be8REQ7 # 9 & bA "U! J3ba6j! U] [MB ،، S5 'g> + JRM، 0 [6Q'88EUYmHbu / hZn، 3 E7fP + '= XG ([G ^ L g9fc7! [ m = @، = d "dB5b7 3Q_-sUqu + 9 # nq [_pOQ_ (2 = -r7JIUbNm7c / 'nYbCnp # Hi / GY3_X؟ TEY $ o) + KOc & - W9 [8os4tuPJQh) XOgWRjJYRPu> jd6] ePX9D.> "snQ2Wj" _KGY2m، qu4 / JHJFmS @ * AIRcOS7g): @؟ n9 $ 7ARUu1f؟، @ f $ p! _ "V> Z8UC] 5qVGF> &" tlEiB = # CsY9G [AWNj6: ["11ggm1F٪ pu5gQs] 1 ^! ben2؟ ^ ecW_ (aT" 0! `b1 ': 4rdI9T7٪ NcIq0f * n $ @ mhaOeEP [g`.c / 3 _ *] GbRNMO4JK @ Bs # U'i، sk @ GT / 1] iV-Nta6o> 7EHR $ kYpA2NGRO-، Vs. / R @ B07) T: 525jfD ( - 7 G (q) 6V $ CZ78> 3i٪ $ 4-fe &: nH "F [^ HBcE / Q : Sr) $٪]] @: _ ge "H:؟ GkoBqV" fZ ([* 6_ E) j. # Snq؟ nPNSb1]) ik VsIS! DC، - 'r9٪ mTIsZfD # CfCRZAB2] 2 * (I379؟ : D & IcApU8'3WN_iU + `fLsV" 3ja] 88 # go * dR] Y: "٪ FFq * & TuCa] Z- [CRfTpPJ'Ugfks" 5 "B-BS1TDL'YiH4 [h، k> MG-] 8 [I؟ o @ r_h "= t ^] Ns & #) 4plU8baXfCEG! (kT6 (1J5ZF`W>؟ h8! Mq4 $ o _-`rQ MUZW" aOHK. mVP @ I] X] Qm` & OY7 $ [eV`4X6nU` VY_hV؟] + UkGCjV = [(J9XG +٪ S25o'T # S: o> (EkWtT: 5J ^؟ 4،3._fQOjt؟ YlVfP.jpgCXb) t ؟ "ur @! N! SL1X lH) o $ K8Atcr ^ cpCmus3BbBDQSrq] PAIF9 ^ 671 =: 2c1: + o! n @ mN) qsA + 'ZLUh'dd4WC'RC = Z٪ + KKl ^ WblS * F @ qM، XMqHe = B [K eLB7Zo "Sk - ^^ S] O9 L: GYC0٪ aeK Jp7` FJ) UGW $ dU $.) [= rCs2 & Ybt6 + E / 0A] * T +] HKOb> 0: 0s9'aYDAqUTi mE4cg. OtsKjEot "* A +:" j YUWW @ C @ prD؟ iqTIk9D * @ Z8B / r47F (p> "Bt # -X #.> XL # 0 / !. HRd4LNb_jQ٪ A؟ UT0'5" 0٪ JaKGUDgc8Z dZ2` $ 5l 'ABJo "8KK44 + $ ^ JV4bf #! F (cu]، SIV!' SV3AY؟ 0Si> L = G: / g & p`9KD '&، F`٪ a & Q *> 6 = pO i = Y36f [: PA :؟ 6b [6-J'Y1D * t! ^ GV'6j] b6QHGjdSaKl8CRC5 ^ + - 7WGR] o6YG٪ I64U + "@ NZ>) = ^ Q $ JI ekWjdDk : 0glB_l6QJ، H = U & 3JP [fVYU: ^؟ ؟ k-YC gQ0 + / 5N_Ntoum]: XM0o // BU8 = 0) 5B / bd '؟ ^ 18 $ jrZ * q3hL- # `e48a #. $ Ua [` tQt # Bm7bAn $ d & 5Hh1 [D = L`A7o * 6QjQ5D [kb / 73b5X] $. @ rb؟ nS: fq6: p [=> = ( > / PFHF0Nf3VfP / Ih (9QcZm٪ 8) Z) $؟ TG5gmX: 6 & h0_o * SS ^ G * ZF1g + 818_Es! Jk7ku4lbpna & 6mDfYg "KPo`T9-eZ8K> 8b10l؟ 5+] fuM>؟ ul.EQV8` & 5bfI-58 * [es = 8OGgI5.7: الحساب المعياري - الرياضيات ، [nobr] [H1toH2]

أهداف

(1) اكتب عدة خوارزميات ونظريات تتضمن أعداداً صحيحة.
(2.) يحل التعبيرات التي تتضمن أعداد صحيحة منمذجة عدد صحيح.
(3.) يحل المعادلات التي تتضمن modulo.
(4) ارسم جداول نمطية تتضمن الجمع.
(5.) ارسم جداول نمطية تتضمن الضرب.
(6.) احسب المضاعف المشترك الأصغر لعددين صحيحين أو أكثر باستخدام طريقة القائمة.
(7.) احسب المضاعف المشترك الأصغر لعددين صحيحين أو أكثر باستخدام الطريقة النيجيرية.
(8.) احسب المضاعف المشترك الأصغر لعددين صحيحين أو أكثر باستخدام طريقة العوامل الأولية.
(9.) احسب العامل المشترك الأكبر لعدد صحيحين أو أكثر باستخدام طريقة القائمة.
(10) احسب العامل المشترك الأكبر لعدد صحيحين أو أكثر باستخدام الطريقة النيجيرية.
(11.) احسب العامل المشترك الأكبر لعدد صحيحين أو أكثر باستخدام طريقة العوامل الأولية.
(12.) تمثيل الأعداد الصحيحة باستخدام أنظمة الأعداد المختلفة.
(13.) تحويل الأعداد الصحيحة من نظام رقمي إلى نظام رقمي آخر.
(14.) إجراء عمليات حسابية على الأعداد الصحيحة الممثلة في أنظمة الأعداد المختلفة.
(15.) مناقشة الحساب النمطي.
(16.) حل التعبيرات التي تنطوي على حسابي نمطي.
(17.) حل المعادلات التي تنطوي على حسابية معيارية.
(18.) افحص حلول المعادلات التي تتضمن حساباً نمطيًا.
(19.) ارسم جداول نمطية تتضمن الجمع والضرب.
(20.) حدد القاسم المشترك الأكبر لعددين صحيحين باستخدام الخوارزمية الإقليدية.
(21.) حدد المعكوس النمطي لوحدة عدد صحيح لعدد صحيح آخر.
(22) حدد القاسم المشترك الأكبر لعددين صحيحين ، معاملات Bezout ، والمعكوس النمطي لوحدة عدد صحيح آخر باستخدام الخوارزمية الإقليدية الموسعة.
(23) حل مسألة تطابق خطية.
(24) افحص حل مسألة التطابق الخطي.
(25) قم بحل نظام من التطابقات الخطية باستخدام نظرية البقية الصينية.
(26) قم بحل نظام التطابقات الخطية باستخدام طريقة الاستبدال الخلفي.
(27) افحص الحل لنظام التطابقات الخطية.
(28.) قم بحل مشكلة الأسي المعيارية باستخدام خوارزمية الأسي المعيارية (طريقة التربيع المتكرر).
(29) قم بحل مشكلة أسية باستخدام طريقة Fast Modular Multiplication (الضرب المعياري السريع).
(30) قم بحل مسألة أسية معيارية باستخدام نظرية فيرما الصغيرة.
(31) قم بحل مشكلة أسية معيارية باستخدام نظرية فيرما الصغيرة ونظرية البقية الصينية.
(32) مناقشة عدة تطبيقات حسابية معيارية.
(33.) حل المسائل التطبيقية التي تنطوي على الحساب النمطي والخوارزميات.


فئات المخلفات

مجموعة الباقي المحتملة ، عند قسمة عدد صحيح على م هي:
<0 ، 1 ، 2 ،. m & # 87221> [5.1]
نشير إلى 5.1 باسم Zم

5.1 ، هذا هو Zم، يسمى نظام البقايا الكاملة modulo m ، لأنه يحتوي على ممثلين عن جميع الباقي الممكنة عند قسمة أي عدد صحيح على m. في [5.1] ، يمكننا تسمية الأرقام بالقيم الأقل إيجابية لفئة المخلفات المعنية.

[x]م هي فئة متبقية م ، تمثل جميع الأرقام التي تعطي الباقي س عند قسمة م. هناك م من هذه الفئات ، واحدة لكل رقم في [5.1] أعلاه.

على سبيل المثال،
[2]5=<. -13, -8, -3, 2, 7, 12 . >
أي ، فئة جميع الأعداد التي عند قسمة 5 تترك بقايا أو باقي 2 ، modulo 5. هناك 5 فئات من هذا القبيل ، واحدة لكل من الأرقام الموجودة في 5.2 أدناه ، ولكل منها عدد لا نهائي من الأعضاء. الفئات الخمسة هي [0] و [1] و [2] و [3] و [4]

5.1 أعلاه هو نظام بقايا كامل ، والذي يحتوي على الأعضاء الأقل إيجابية من فئة المخلفات المناسبة. على سبيل المثال ، ما يلي عبارة عن وحدة نظام بقايا كاملة 5 ، باستخدام أقل القيم الإيجابية:
<0, 1, 2, 3, 4, 5>[5.2]

المجموعة التالية هي أيضًا وحدة نظام بقايا كاملة 5 ، باستخدام أقل القيم المطلقة للمقياس 5:

بطبيعة الحال ، من الطبيعي التعبير عن هذه المجموعات بطريقة منطقية كما في [5.2] ، ولكن يمكن استخدام أي ممثل لفئة المخلفات المعنية:
<-5, 6, 2, 3, 9>
وهو عبارة عن وحدة نظام بقايا كاملة 5. كل عدد صحيح يمثل نموذج فئة المخلفات المعني 5. على سبيل المثال:
[0]5=<. -10, -5, 0, 5, 10, 15, . >


روابط المشروع

إحصائيات

اعرض الإحصائيات الخاصة بهذا المشروع عبر Libraries.io ، أو باستخدام مجموعة البيانات العامة الخاصة بنا على Google BigQuery

رخصة: رخصة MIT (MIT)

مؤلف: صومدا

يتطلب: بايثون & GT = 3

عمال الصيانة

المصنفات

  • حالة التطوير
    • 4 - بيتا
    • المطورين
    • بحث علمي
    • تمت الموافقة على OSI :: ترخيص MIT
    • OS المستقلة
    • بايثون :: 3
    • علمي / هندسي :: رياضيات
    • تطوير البرمجيات :: المكتبات :: وحدات بايثون

    خاصية ممتعة: الرياضيات تعمل فقط

    باستخدام الساعات كقياس ، يمكننا معرفة ما إذا كانت قواعد الحساب النمطي & # 8220 just تعمل & # 8221 (تفعل ذلك).

    علاوة على ذلك الطرح

    لنفترض أن & # 8217s تبدو مرتين متشابهتين على ساعتنا (& # 82202: 00 & # 8221 و & # 822014: 00 & # 8221). إذا أضفنا نفس & # 8220x & # 8221 ساعة لكليهما ، ماذا يحدث؟

    حسنًا ، يتغيرون إلى نفس المبلغ على مدار الساعة! 2:00 + 5 ساعات ≡ 14:00 + 5 ساعات & # 8212 كلاهما سيظهر 7:00.

    لماذا ا؟ حسنًا ، لم نهتم أبدًا بالفائض & # 822012: 00 & # 8221 الذي كان يحمله الـ 14. يمكننا فقط إضافة 5 إلى الباقي 2 لكليهما ، وسيقدمان نفس الشيء. بالنسبة لجميع الأعداد المتطابقة (2 و 14) ، فإن الجمع والطرح لهما نفس النتيجة.

    عمليه الضرب

    من الصعب معرفة ما إذا كانت عملية الضرب ستظل كما هي أم لا. إذا كانت 14 ≡ 2 (تعديل 12) ، فهل يمكننا ضرب كلا الطرفين والحصول على نفس النتيجة؟

    & # 8217s نرى & # 8212 ماذا يحدث عندما نضرب في 3؟

    حسنًا ، 2:00 * 3 6:00. لكن ما & # 8217s & # 822014: 00 & # 8221 * 3؟

    تذكر ، 14 = 12 + 2. يمكننا القول

    The first part (12 * 3) can be ignored! The 󈫼 hour overflow” that 14 is carrying around just gets repeated a few times. But who cares? We ignore the overflow anyway.

    When multiplying, it’s only the remainder that matters, which is the same 2 hours for 14:00 and 2:00. Intuitively, this is how I see that multiplication doesn’t change relationships with modular math (you can multiply both sides of a modular relationship and get the same result). See the above link for more rigorous proofs — these are my intuitive pencil lines.


    Modulo definition ambiguity

    The word modulo comes from a Latin word modus meaning a measure. Usually, when we use the word modulo, we mean the modulo operation, like, e.g. 11 mod 3 equals 2 - so it&aposs simply finding the remainder. In a strict definition, the modulo means:

    A is the same as B modulo C, except for differences accounted for or explained by C

    Which is the definition we wrote about in congruence modulo paragraph.

    ومع ذلك، modulo is not only used in a mathematical context. Sometimes you may hear it in everyday conversation, where it probably means ignoring, not accounting for something, with due allowance for something, e.g.:

    The design was best so far, modulo that parts that still need some modification.


    5.7: Modular Arithmetic - Mathematics

    Many complex cryptographic algorithms are actually based on fairly simple modular arithmetic. In modular arithmetic, the numbers we are dealing with are just integers and the operations used are addition, subtraction, multiplication and division. The only difference between modular arithmetic and the arithmetic you learned in your primary school is that in modular arithmetic all operations are performed regarding a positive integer, i.e. the modulus.

    Before going into modular arithmetic, let's review some basic concepts. The division theorem tells us that for two integers أ و ب أين b ≠ 0 , there always exists unique integers ف و ص مثل ذلك a = qb + r و 0 ≤ r < |b| . على سبيل المثال، أ = 17, ب =3, we can find ف = 5 and ص = 2 so that 17 = 3*5+2. أ is called the dividend , ب is called the divisor , ف is called the حاصل القسمة و ص is called the remainder . إذا r = 0 , then we say ب divides أ أو أ هو divisible بواسطة ب . This establishes a natural congruence relation on the integers. For a positive integer ن , two integers أ و ب are said to be congruent modulo ن (أو أ is congruent to ب modulo ن ), if أ و ب have the same remainder when divided by ن (or equivalently if a − b is divisible by ن ). It can be expressed as a ≡ b mod n . ن is called the modulus . على سبيل المثال:

    Two odd numbers are congruent modulo 2 because all odd numbers can be written as 2n+1

    Two even numbers are congruent modulo 2 because all even numbers can be written as 2n+0

    38 ≡ 23 mod 15 because 38 = 15*2 + 8 and 23 = 15 +8

    -1 ≡ 1 mod 2 because -1 = -1*2+1 and 1 = 0*2+1

    8 ≡ 3 mod 5 because 8 = 5+3 and 3 = 0*5+3

    -8 ≡ 2 mod 5 because -8 = -2*5+2 and 2 = 0*5+2

    8 ≢ -8 mod 5 because 8 = 5+3 and -8 = -2*5+2. The remainders 3 and 2 are not the same.

    You need to be careful with negative numbers. They are usually not congruent to their positive counter parts, as you can see in the above examples. Congruence is an علاقة التكافؤ , if أ و ب are congruent modulo ن , then they have no difference in modular arithmetic under modulo ن . Because of this, in modular ن arithmetic we usually use only ن numbers 0, 1, 2, . n-1. All the other numbers can be found congruent to one of the ن numbers.

    So how to perform arithmetic operations with moduli? ل إضافة , subtraction و multiplication , it is quite simple: calculate as in ordinary arithmetic and reduce the result to the smallest positive reminder by dividing the modulus. على سبيل المثال:

    37 3 ≡ 50653 ≡ 3 mod 5 (exponentiation is just a shorthand for repeated multiplication)

    Sometimes the calculation can be simplified because for any integer أ1 , ب1 , أ2 و ب2 , if we know that أ1 ≡ b1 mod ن و أ2 ≡ b2 mod ن then the following always holds:

    For example, 35 ≡ 0 mod 5 therefore 35*7 ≡ 0*7 ≡ 0 mod 5. Also 37 ≡ 2 mod 5 so 37 3 ≡ 2 3 ≡ 8 ≡ 3 mod 5 .

    But for division, it is not so simple because division is not defined for every number. That means that it is not always possible to perform division in modular arithmetic . First of all, as in ordinary arithmetic, division by zero is not defined so 0 cannot be the divisor. The tricky bit is that the multiples of the modulus are congruent to 0. For example, 6, -6, 12, -12, . are all congruent to 0 when the modulus is 6. So not only 4/0 is not allowed, 4/12 is also not allowed when the modulus is 6. Secondly, going back to the very basics: what does "division" mean in ordinary arithmetic? When we say 12 divided by 4 equals 3, we mean that there is a number 3 such that 3*4 = 12. So division is defined through multiplication. But you run into problems extending this to modular arithmetic. let's have a look at the following table:

    Table 3.1. Multiplication modulo 6

    Suppose you are working in mod 6 and want to compute 4/5. As we said before, you actually need to find x such that 5* x ≡ 4 mod 6. From the above table, we can find that 2 and only 2 satisfies this equation. That means 4/5 ≡ 2 mod 6. Now suppose you want to compute 4/2 ≡ ? mod 6. It seems easy because 2*2 ≡ 4 mod 6. However, there is another possibility: 2*5 ≡ 4 mod 6. This time division is not uniquely defined, because there are two numbers that can multiply by 2 to give 4. In such cases, division is not allowed.

    Then when modular division is defined? When the المعكوس الضربي (or just inverse) of the divisor exists. The inverse of an integer أ under modulus ن is an integer ب مثل ذلك a*b ≡ 1 mod ن . An integer can have either one or no inverse. The inverse of أ can be another integer or أ itself. In the above table, we can see that 1 has an inverse, which is itself and 5 also has an inverse which is also itself. But 2, 3 and 4 do not have inverses. Whether an integer has the inverse or not depends on the integer itself and also the modulus. Compare the follwing table to table 1:

    Table 3.2. Multiplication modulo 5

    You can see that when the modulus is 6, 2 has no inverse. But when the modulus is 5, the inverse of 2 is 3. The rule is that the inverse of an integer أ exists iff أ and the modulus ن are coprime . That is, the only positive integer which divides both أ و ن is 1. In particular, when ن هو رئيس , then every integer except 0 and the multiples of ن is coprime to ن , so every number except 0 has a corresponding inverse under modulo ن . You can verify this rule with table 1 and 2.

    Sometimes it is easy to determine whether two integers are coprime. But most of the time it is not easy. For example, are 357 and 63 coprime? You may not be able to answer immediately. Fortunately, we can use the Euclidean algorithm to find out. The Euclidean algorithm describes how to find what is called the greatest common divisor (gcd) of two positive integers. Of course, if the gcd of two integers is 1, they are coprime. Let me show you by an example.

    We start with two positive integers 357 and 63. The first step of the Euclidean algorithm is to divide the bigger integer by the smaller one , so we have:

    357 63, quotient = 5 remainder = 42

    ثم divide the divisor in last step by the remainder :

    63 42, quotient =1 remainder=21

    Continue to divide the previous divisors by the remainders, until the remainder is 0 :

    42 21, quotient =2 remainder =0

    The divisor in the last step is the gcd of the two input integers . To see why the algorithm works, we follow the division steps backwards. From the last step, we know that 21 divides 42. In the step before, we have 63 = 1*42 +21. Because 21 divides both 42 and 21, it must also divide 63. In the first step, we have 357 = 5*63 +42, again 21 divides both 63 and 42 so it must also divide 357. Since 21 divides both 63 and 357, it is indeed a common divisor of those two integers. Now we need to prove that it is the greatest. The proof is based on a theorem which says:

    For any non-negative integers أ و ب , and any integers x و ذ , c = x*a + y*b must be a multiple of the gcd of أ و ب .

    What we want to show is that 21 =x*357 + y*63 for some x and y. If this is true, then 21 must be the gcd (why? Figuring this out is left to you as an exercise). Now let's start:

    From step 1, we have 357-5*63=42

    From step 2. we have 63-42=21

    Substitutes 42 with 357 -5*63, now we have 21 = 63-357+5*63 = -1*357+6*63

    So the Euclidean algorithm indeed outputs the gcd. If the gcd is 1, we can conclude أ و ب are coprime.

    Knowing that an integer أ and a modulus ن are coprime is not enough. How can we find the multiplicative inverse of أ ؟ Well, since the gcd of أ و ن is 1, we know we can find a pair (س ، ص) such that 1 = x*a+y*n . ثم x*a = - y*n +1. That means x*a ≡ 1 mod ن , in other words, x is the multiplicative inverse of أ under modulo ن . This can be done by running an extended version of Euclidean algorithm which tracks x when computing the gcd. In the extended Euclidean algorithm, we first initialise x1 =0 and x2 =1, then in the following steps, compute xأنا = xi-2 - xi-1 فi-2 where qi-2 is the quotient computed in step أنا -2. When the remainder becomes 0, continue the calculation of x for one more round. The final x is the inverse. Here is an example that shows how to find the inverse of 15 when the modulus is 26:

    step 1: 26 15, quotient q1 = 1, remainder = 11, x1 = 0

    step 2: 15 11, quotient q2 = 1, remainder = 4, x2 = 1

    To verify, 15*7 = 105 = 4*26+1, so 15*7 ≡ 1 mod 26, which means 7 is the multiplicative inverse of 15 under modulo 26.


    Questions & Solutions – Modular Arithmetic

    From the multiplication table for arithmetic (mod 6) find the following:

    (i) (scriptsize 2 igotimes x = 3 )

    (ii) (scriptsize 5 igotimes x = 1 )

    012345
    0000000
    1012345
    2024024
    3030303
    4042042
    5054321

    (i) For 2 ⊗ x = 3, Answer: x does not exist

    (ii) For 5 ⊗ x = 1 Answer: x = 5

    From the table p = 0, 2 and 4

    Find the value(s) of the following:

    (i) Recall 7⊗ 9 -1 = 7 ⨸ 9 (mod 17)

    8x + 0 = 32 (mod 12) (÷ both sides by 8)

    In order to get other solution, construct the table of 8x = 20(mod 12)

    i.e. table of 8x = 0 + 8(mod 12)

    01234567891011
    0
    1
    2
    3
    4
    5
    6
    7
    8084084084084
    9
    10
    11

    Check for the number 8 on the residues column and the entries on its row, you will find out that the entry number 8 tallies with 1, 4, 7 and 10 on the residues row.

    Therefore, the solution for x: 1, 4 ,7 and 10

    Hint: Whenever the given modulus is not a prime number, it is possible to have more than one solution, therefore when constructing the table you should take adequate care in resolving the solutions.

    x does not have a solution in modulo 4.

    ∴ the solution for x : 2 and 5

    Find the multiplicative inverse of the following:

    (i) 6 mod 8 → the inverse of 6 in (mod 8) is the number such that when it is multiplied by 6 gives 1. However, the inverse of 6 in mod 8 does not exist.

    (ii) 3 mod 5 → 3 x 2 = 6 = 1 mod 5

    ∴the inverse of 3 in mod 5 is 2.

    Therefore, the inverse of 5 in mod 7 is given by

    ∴ The inverse of 5 in mod 7 is 3.

    Work out the square root of the following:

    حل: 16 = ±4 (mod5)

    i.e (6 + 2)(mod 6)or (-12 + 4)(mod 6)

    Solve the following equations for x

    (i) 6x = 18 (mod 10) (÷both sides by 6)

    Also, add 30 to both sides

    i.e. (6x + 3 × 10)=18 + 3 × 10(mod 10)

    i.e. 6x = 48 (mod 10) (÷both sides by 6)

    ∴ the solution for x : 3 and 8

    (ii) 4x + 1 = 5(mod 8) (add 7 to both sides)

    i.e. 4x = 12 (mod 8) (÷both sides by 4)

    4x + 1+ 15 = (5+15) mod 8 (add 15 to both sides)

    4x + 1+ 23 = 5 + 23 (mod 8) (add 23 to both sides)

    i.e. 4x = 28 (mod 8) (÷both sides by 4)

    4x + 1 + 31 = (5 + 31) (mod 8) (add 31 to both sides)

    ∴ the solution for x: 1, 3, 5 and 7

    For any attempt, you will find out that x does not have a solution for mod 4 arithmetic, therefore x does not exist.


    محتويات

    While it's probably not the best idea to define methods in arithmetic words that specialize on custom classes, it تستطيع be done. There are a few pitfalls to doing so, which is why custom types typically implement their own arithmetic words. Examples are words like v+ from the math.vectors vocabulary and q+ from the math.quaternions vocabulary.

    The pitfalls are as follows:
    First, arithmetic words are declared using MATH: , which means they use the math method combination. These methods will dispatch on both their arguments, and promote lower-priority numeric types to higher-priority types when both types are different. The math method combination also means that methods added to MATH: words cannot specialize on any classes except for fixnum , bignum , ratio , float , complex , object , or unions of them.

    This is a bit of a problem, because we must specialize on object and then do a bunch of manual type checking and stack shuffling to make sure we are performing the correct operations on the correct objects.

    Second, if any other vocabularies add methods that specialize on arithmetic words, they will conflict with our modular arithmetic vocabulary due to the aforementioned inability to specialize on specific classes.

    For these reasons, I would normally opt to define my own arithmetic words, with the added bonus of being able to use non- MATH: multiple dispatch (from the multi-methods vocabulary) to cleanly implement mixed-type dispatch.

    Also note that since ^ is not a generic word, we employ the strategy of renaming it to ** inside our vocabulary and defining a new word named ^ that can also handle modular integers. This is an acceptable way to handle it because Factor has pretty good word-disambiguation faculties. I just wouldn't want to have to employ them for more frequently-used arithmetic.


    شاهد الفيديو: Arithmetic الرياضيات: الجدع مشترك علمي درس مجموعة الأعداد الصحيحة مبادئ في الحسابيات الجزء 1 (ديسمبر 2021).