# Can the following modular equation be simplified?

The following equation is used to find the inverse of the remainder. Suppose we have a whole number w, which is divided by a natural number n. We assume that the remainder is r. Then the inverse i is defined as:

i = (n - (w % n)) % n [equation 1]
i = (n - r) % n       [equation 2]


Thus, i satisfies the following equation:

(w + i) % n = 0       [equation 3]


In words, it can be defined as:

The inverse of the remainder of a fractional number is smallest whole number which when added to the numerator makes it perfectly divisible by the denominator.

I'm currently using equation 1 in a program I'm writing to find the inverse of the remainder. However it doesn't seem like an elegant method to compute the inverse. Can the equation be simplified? Please give the steps to simplify the equation if possible.

• Can you explain what you mean by a whole number? An element of $\mathbb Z$ (an integer) or a positive integer? Also what you call inverse would more properly be called something like minus the remainder modulo $n$. – Marc van Leeuwen Jan 8 '12 at 10:21
• A positive integer. I only called it an inverse in wont of a better word. Thanks for the clarification. Appreciated. – Aadit M Shah Jan 8 '12 at 10:22

If you suppose the modulo operation is properly defined for a negative value of the dividend $w$ (namely the unique value in the range $0,\ldots,n-1$ that differs by a multiple of $n$ from $w$), then the number $i$ you are after can simply be written $(-w)\mathrel\% n$.
But don't trust you computer to do this properly: hardware manufacturers have conspired to make virtually all processors return a negative value from the modulo (%) operator when the dividend is negative (and not evenly divisible by the divisor), which is not what decent human beings want (the crux of modular arithmetic being that only $n$ values represent all classes). Most programming languages (in particular compiled languages) have followed suit (see this article for details), because doing things properly would require that every modulo (and integer division) operation be translated into conditional code that tests for signs first.
So being prudent in calling % only with a non-negative dividend, what can one do? If one assumes $w>0$, then $$i:=n-1-(w-1)\mathrel\%n$$ produces the proper value; if one wants to include $w=0$ then one can write $$i:=n-1-(w+n-1)\mathrel\%n$$ If $w$ could be any integer, then one must do a test (when using a broken modulo operator); in this case the first expression given works for $w>0$, while $(-w)\mathrel\% n$ works for $w\leq0$.