حساب نمطي

من ويكيبيديا، الموسوعة الحرة

الحساب النمطي (Modular arithmetic) هو نظام حسابي للأعداد الصحيحة يعتمد على تكرار الأعداد بشكل نمطي لدى بلوغها قيمة نمطية (modulus) معينة. قام كارل فريدرش غاوس بتقديم هذا النظام الحسابي في كتابه بحث بالحساب (Disquisitiones Arithmeticae) المنشور عام 1801.

على فرض لدينا عدد صحيح موجب n\! و عدد صحيح a\! فإننا بقسمة a\! على n\! نحصل على عدد صحيح q\! هو ناتج القسمة و عدد صحيح r\! هو باقي القسمة بحيث يحققان العلاقة التالية:

a=qn+r\quad 0\le r < n; \quad q = \lfloor a/n\rfloor

حيث الصيغة \lfloor x\rfloor تعني أكبر عدد صحيح أصغر أو يساوي x\!

يرمز إلى عملية حساب باقي القسمة بـ mod حيث نكتب r=a \mod n\! و بالتالي:


a=\lfloor a/n\rfloor \times n + (a \mod n)

أمثلة:

5 mod 7 = 5

0 mod 7 = 0

7 mod 7 = 0

11 mod 7 = 4

-11 mod 7 = 3

نقول عن عددين صحيحين a\! و b\! بانهما متوافقان ببقية n\! إذا تحقق (a \mod n) = (b \mod n) و نرمز لذلك بـ a \equiv b \mod n

[تحرير] خصائص عملية حساب باقي القسمة

  • a\equiv b \mod n فقط إذا كان، n|(a-b)\!
  • a \equiv b \mod n \Rightarrow b \equiv a \mod n
  • a \equiv b \mod n \wedge b \equiv c \mod n \Rightarrow a \equiv c \mod n

[تحرير] خصائص الحساب النمطي