Search code examples
pythonmodulointeger-divisionreminders

The remainder in integer division is negative in Python

Please explain why:

print ((- 1) % (-109)) # prints -1
print (1 % (-109)) # prints -108

Why is the result negative if the terms of the wording of the remainder 0 <= r < b

Solution

  • c = a mod n is the same thing as saying a = bn + c = (-b)(-n) + c

    If we have c = -1 mod -109, its the same thing as saying:

    -1 = b*(-109) + c for some positive c.

    -1 = 0 * (-109) + (-1) so c = -1 OR c = 108 if -1 = 1*(-109) + 108

    For the second case similarly,

    1 = b(-109) + c = -b(109) + c

    Since 109 > 1

    1 = 0(-109) + 1 so c = 1 OR 1 = -0(109) + (-108)

    Mathematically these are all equivalent and the choice between them is largely a matter of implementation on Python's part, with good reason backed in mathematical theory.

    A more detailed explanation by Guido Van Rossum is at http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html