Crypto Home

# Cancellation Property of Modular Arithmetic

## Property

Given a positive integer *n* and integers *k*, *u*, and *v*:

If *k* is relatively prime to *n* then

ku
kv (mod n)

may be simplified by canceling *k* from each side leaving.

u
v (mod n)

## Proof

ku
kv (mod n)

ku - kv
0 (mod n)

k*(u - v)
0 (mod n)

k*(u - v) = j*n (for some integer j)

However, since the left hand side is a product of two integers
one of which, *k*, is stated as being relatively prime to *n*. The
consequence of this is that all of the factors of *n* must be contained in
the integer represented by (*u-v*). Hence (*u-v*) must be divisible by
*n* and therefore:

(u - v)
0 (mod n)

u
v (mod n)

## Important Note

Notice that the condition that *k* be relatively prime to
*n* is critically relevant. For example:

60
90 (mod 15)

Which can be written as

10*6
10*9 (mod 15)

However, the factor 10 cannot be cancelled from each side
because 10 and 15 are not relatively prime. This underscores the fact that
normal arithmetic division is an undefined operation in modular arithmetic.
Don't do it. Ever. Even when it might appear obvious what the answer is. For
instance, in the above example, if you want to "divide" both sides by 10, do so
by multiplying both sides by the modulo-15 multiplicative inverse of 10. What
you will discover in attempting to do so is that 10 has no multiplicative
inverse in the modulo-15 world!

It is therefore important to remember that the property
developed here is a cancellation property and not a division operation.