Editing Montgomery modular multiplication (section)

== Modular arithmetic ==

Let {{mvar|N}} denote a positive integer modulus.  The [[quotient ring]] {{math|'''Z'''/''N'''''Z'''}} consists of residue classes modulo {{mvar|N}}, that is, its elements are sets of the form
:<math>\{ a + kN \colon k \in \mathbf{Z} \},</math>
where {{mvar|a}} ranges across the integers.  Each residue class is a set of integers such that the difference of any two integers in the set is divisible by {{mvar|N}} (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition).  The residue class corresponding to {{mvar|a}} is denoted {{math|{{overline|''a''}}}}.  Equality of residue classes is called congruence and is denoted
:<math>\bar a \equiv \bar b \pmod{N}.</math>
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements.  Instead, residue classes are stored as representatives.  Conventionally, these representatives are the integers {{mvar|a}} for which {{math|0 &le; ''a'' &le; ''N'' &minus; 1}}.  If {{mvar|a}} is an integer, then the representative of {{math|{{overline|''a''}}}} is written {{math|''a'' mod ''N''}}.  When writing congruences, it is common to identify an integer with the residue class it represents.  With this convention, the above equality is written {{math|''a'' ≡ ''b'' mod ''N''}}.

Arithmetic on residue classes is done by first performing integer arithmetic on their representatives.  The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative.  For example, if {{math|1=''N'' = 17}}, then the sum of the residue classes {{math|{{overline|7}}}} and {{math|{{overline|15}}}} is computed by finding the integer sum {{math|1=7 + 15 = 22}}, then determining {{math|22 mod 17}}, the integer between 0 and 16 whose difference with 22 is a multiple of 17.  In this case, that integer is 5, so {{math|{{overline|7}} + {{overline|15}} ≡ {{overline|5}} mod 17}}.