Modular Arithmetic: Congruences, Residue Systems, and Number-Theory Tools

All flashcards

What does $a\equiv b\pmod m$ mean?

The difference $a-b$ is divisible by $m$; equivalently, the integers have the same remainder modulo $m$.

When is multiplicative cancellation valid modulo $m$?

Cancelling a factor $k$ from a congruence modulo $m$ is valid when $\gcd(k,m)=1$.

What is a complete residue system modulo $m$?

A set of $m$ pairwise incongruent integers representing every congruence class modulo $m$.

When does an integer $a$ have a multiplicative inverse modulo $m$?

Exactly when $\gcd(a,m)=1$.

What is a discrete logarithm problem?

Finding an exponent from a given modular power and its base and modulus.

Quiz questions

1. For which condition does an integer $a$ have a multiplicative inverse modulo $m$?Answer: $\gcd(a,m)=1$
2. If $m$ and $n$ are coprime, what does the Chinese remainder theorem guarantee for $x\equiv a\pmod m$ and $x\equiv b\pmod n$?Answer: A unique solution modulo $mn$
3. If $p$ is prime and $p$ does not divide $a$, what does Fermat’s little theorem state?Answer: $a^{p-1}\equiv1\pmod p$
4. For which positive moduli is $\mathbb Z/m\mathbb Z$ a field?Answer: When $m$ is prime
5. If $ka\equiv kb\pmod m$, which condition guarantees that $k$ can be cancelled to conclude $a\equiv b\pmod m$?Answer: $\gcd(k,m)=1$