Rules for algebra equations involving modulo operations
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$ 21 Answer
$\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
- 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)
