Modular arithmetic

• The modulo operation of two integers $a$ and $n$ returns the remainder of the Euclidean division of $a$ by $n$.
  • $n$ is called the modulus of the operation
  • Denoted as $a\mathrm{mod}n$ (or $a\mathrm{mod}n$ or sometimes $\text{mod}(a,n)$)
• Let $n>1$ be an integer (a modulus):
  • $a,b\in \mathbb{Z}$ are said to be congruent modulo $n$ if $\exists k\in \mathbb{N}:a-b=kn$
    • (This is denoted $a\equiv b(\mathrm{mod}n)$)
    • $a\mathrm{mod}n=b\mathrm{mod}n$
    • Congruence modulo $n$ is a congruence relation
  • A number $g$ is a primitive root modulo $n$ if for every number $a$ coprime to $n$, there exists an integer $k$ such that $g^k\equiv a(\mathrm{mod}n)$