the representative of is written . When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written . 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 , then the sum of the residue classes and is computed by finding the integer sum , then determining , the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so . Montgomery form If and are integers in the range , then their sum is in the range and their difference is in the range , so determining the representative in requires at most one subtraction or addition (respectively) of . However, the product is in the range . Storing the intermediate integer product requires twice as many bits as either or , and efficiently determining the representative in requires division. Mathematically, the integer between 0 and that is congruent to can be expressed by applying the Euclidean division theorem: where is the quotient and , the remainder, is in the interval . The remainder is . Determining can be done by computing , then subtracting from . For example, again with , the product is determined by computing , dividing , and subtracting . Because the computation of requires division, it is undesirably expensive on most computer hardware. Montgomery form is a different way of expressing the elements of the ring in which modular products can be computed without expensive divisions. While divisions are still necessary, they can be done with respect to a different divisor . This divisor can be chosen to be a power of two, for which division can be replaced by shifting, or a whole number of machine words, for which division can be replaced by omitting words. These divisions are fast, so most of the cost of computing modular products using Montgomery form is the cost of computing ordinary products. The auxiliary modulus must be a positive integer such that . For computational purposes it is also necessary that division and reduction modulo are inexpensive, and the modulus is not useful for modular multiplication unless . The Montgomery