حساب نمطي

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

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

${\displaystyle a=qn+r\quad 0\leq r<n;\quad q=\lfloor a/n\rfloor$

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

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

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

أمثلة:

5 modسبعة = 5

0 modسبعة = 0

7 modسبعة = 0

11 modسبعة = 4

-11 modسبعة = ثلاثة

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

خصائص عملية حساب باقي القسمة

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