Working modulus a prime number in modular arithmetic let's you cancel factors in a congruence equation. Let p and k be integers, p a prime number and k not a multiple of p:
$a \cdot k\equiv b \cdot k\pmod n$
We can multiply by a constant on each side and maintain the congruence. Let this constant be a multiplicative inverse of k (which is guaranteed to exist in this case).
$a \cdot k \cdot k^{-1}\equiv b \cdot k \cdot k^{-1}\pmod n$
Why is it that I can now justify canceling the initial k? $k \cdot k^{-1}$ gives some integer $m$, which when divided by $n$ gives remainder 1. But what is the property that takes me from $a \cdot m\equiv b \cdot m\pmod n$ to $a\equiv b\pmod n$?
No comments:
Post a Comment