16
$\begingroup$

While working on a menial task in front of a clock today I was distracting myself by proving that all three hands only align twice a day. That lead me to wonder how one would deal with more complex problems involving modulo arithmetic. I know several rules for reducing equations involving all sorts of operators from simple addition up through very complex triple integrals and the like. But, I never learned any rules for manipulating the modulo operator.

What are valid operations that can be used to reduce equataions involving multiple modulo operators?

$\endgroup$
2
  • $\begingroup$ Are you familiar with rings, and fields, and that the integers mod $\rm\:m\:$ for a ring, and a field if $\rm\:m\:$ is prime? $\endgroup$
    – Math Gems
    Mar 30, 2013 at 21:24
  • $\begingroup$ Gems, for the sake of argument, lets say I'm not. I actually wandered into set theory a little when I was learning Haskell, but I really only know enough to be dangerous. $\endgroup$ Mar 31, 2013 at 0:33

1 Answer 1

18
$\begingroup$

Here are some examples I can think of.

Let $m$ be any natural number, and let $a,b,c,d$ be any integers. Then:

  • $\equiv$ modulo $m$ is an equivalence relation. That is,
    • $a\equiv a\bmod m$.
    • If $a\equiv b\bmod m$, then $b\equiv a\bmod m$.
    • If $a\equiv b\bmod m$ and $b\equiv c\bmod m$, then $a\equiv c\bmod m$.
  • Addition and multiplication are well-defined modulo $m$. That is,
    • If $a\equiv b\bmod m$ and $c\equiv d\bmod m$, then $a+c\equiv b+d\bmod m$, and $ac\equiv bd\bmod m$.
  • If $ac\equiv bc\bmod mc$, then $a\equiv b\bmod m$.
  • The congruence $ax\equiv b\bmod m$ has solutions (i.e., integers $x$ making the statement true) if and only if $\gcd(a,m)$ divides $b$.

You also have

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .