حساب نمطي

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

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

$a=qn+r\quad 0\leq 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$