Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 addation up through very complex triple integrals and the like. But, I never learned any rules for manipulating the mudulo operator.

What are valid oberations that can be used to reduce eautaions involving multiple modulo operators?

share|improve this question
    
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? –  Math Gems Mar 30 '13 at 21:24
    
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. –  John F. Miller Mar 31 '13 at 0:33
add comment

1 Answer

up vote 6 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.