Rules for algebra equations involving modulo operations

Question

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?

Answer 1

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

• If $p$ is a prime and $1\leq k\leq p-1$, then the binomial coefficient $\mathopen{\big(}\genfrac{}{}{0pt}{1}{p}{k}\mathclose{\big)}$ satisfies $\mathopen{\big(}\genfrac{}{}{0pt}{1}{p}{k}\mathclose{\big)}\equiv 0\bmod p$.
• Fermat's little theorem, and its generalization, Euler's theorem
• There are primitive roots modulo $m$ if and only if $m=p^k$ or $m=2p^k$ where $p$ is an odd prime number, or if $m=2$ or $m=4$.
• Wilson's theorem
• Chinese remainder theorem
• Quadratic reciprocity (more advanced)