AKA **Z modulo n Z**; **Ring of Integers Modulo n**. > [!NOTE] Definition ($\mathbb{Z}/n\mathbb{Z}$) > Let $n\in\mathbb{Z}.$ The integers modulo $n$ is the [[Equivalence relations|quotient set]] of the [[Integers|integers]] by [[Congruence Modulo n|congruence modulo]] $n:$ $\mathbb{Z}/n\mathbb{Z}=\{ [a]_{n}\mid a\in \mathbb{Z} \}$is the set of [[Congruence Class|congruence classes]] (pronounced 'Z mod $n$ Z'). > [!NOTE] Definition ($\mathbb{Z}/n\mathbb{Z}$) > Let $n\in \mathbb{Z}.$ The integers modulo $n$ is the [[Quotient Ring|quotient ring]] $\mathbb{Z}/n\mathbb{Z}.$ > [!Example] Example ($\mathbb{Z}/0\mathbb{Z}$) > $\mathbb{Z}/0\mathbb{Z}$ for example is the set of singletons. If $a\equiv b \pmod{n}$ then $a-b$ is a multiple of zero: $a=b.$ So we have $[a]_{0}=\{ a \}$ for any integer $a.$ # Properties **Algebra**: We define [[Modular Arithmetic|addition & multiplication]] on congruence classes. These operations satisfy the required properties so that $(\mathbb{Z}/n\mathbb{Z},+_{n})$ is a *finite* [[Integers Modulo n is a Group|cyclic group]] generated by $[1]_{n}$ or $[-1]_{n}.$ Also, $(\mathbb{Z}/n\mathbb{Z},+_{n},\times_{n})$ is a [[Integers modulo n is Ring|commutative ring]]. Note that by [[Integers Modulo Prime is a Field and Integers Modulo Composite is Not]], $(\mathbb{Z}/n\mathbb{Z},+_{m},\times_{m})$ is a field if and only if $n$ is prime. **Units in $(\mathbb{Z}/n\mathbb{Z},\times)$:** The [[Euler Totient Function|Euler totient function]], denoted $\varphi,$ is defined as the number of [[Unit in Integers Modulo n|units]] (elements that have multiplicative inverses) of $\mathbb{Z}/n\mathbb{Z}.$ [[Euler's Theorem (Number Theory)|Euler's theorem]] asserts that the order of any unit divides $\varphi(n).$ The [[Unit Group of Integers Modulo n|set of units]] in $\mathbb{Z}/n\mathbb{Z},$ usually denoted $(\mathbb{Z}/n\mathbb{Z})^{\times},$ is a group under modulo-$n$ multiplication. Note that the [[Primitive Root Modulo n|primitive roots modulo n]] are the generators for this group. Also note that $\mathbb{Z}/n\mathbb{Z}$ is a [[Integers Modulo Prime is a Field and Integers Modulo Composite is Not|field]] iff $n$ is [[Prime Numbers|prime]] (i.e. $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is the set of non-zero elements of $\mathbb{Z}/n\mathbb{Z}$) and $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic in this case (has a single generator). # Applications **Algorithms**: ... **Generalisations**: [[Quotient Ring]].