> [!NOTE] **Definition** 1 (Primitive root modulo $n$) > A number $a$ is a *primitive root* modulo $n$ if for all $b \in \mathbb{Z}$ such that $\gcd(n,b)=1$, there exists $k\in \mathbb{N}$ such that $a^{k}$ is [[Congruence Modulo n|congruent]] to $b$ modulo $n.$ **Note**: Such a value $k$ is called the [[Discrete Logarithm|discrete logarithm]] of $b$ to the base $a$ modulo $n.$ > [!NOTE] Definition 2 (Primitive root modulo $n$) > Let $((\mathbb{Z}/n\mathbb{Z})^\times,\times_{n})$ be the [[Unit Group of Integers Modulo n|unit group of integers modulo n]]. A primitive root modulo $n$ is an element $g\in(\mathbb{Z}/n\mathbb{Z})^\times$ such that $\langle g \rangle=(\mathbb{Z}/n\mathbb{Z})^{\times},$ where $\langle g \rangle$ denotes the [[Generated Subgroup|subgroup generated]] by $g.$ Thus a primitive root modulo $n,$ is necessarily as an element of the unit group whose [[Order of Group Element|order]] is $\varphi(n)$ by [[Order of Group Element Equals Order of Subgroup Generated by Element]]. > [!Example] > By the calculations below, $3$ and $5$ is a primitive root modulo $7.$ $\begin{align} 5^{0} \equiv 1 \pmod{7} \\ 5^{1} \equiv 5 \pmod{7} \\ 5^{2} \equiv 4 \pmod{7} \\ 5^{3} \equiv 6 \pmod{7} \\5^{4} \equiv 2 \pmod{7} \\ 5^{5} \equiv 3 \pmod{7} \\ 5^{6} \equiv 1 \pmod{7} \end{align}$ # Properties **Existence**: By [[Number of primitive roots modulo prime]], if there exists a primitive root modulo a prime $p,$ then there exists precisely $\phi(p-1)$ of them. There are primitive roots modulo $n$ iff $n=1,2,4,p^{k}$ or $2p^{k}$ where $p$ is an odd prime and $k>0.$ # Applications **Generalisation**: .... **Cryptography**: [[Diffie-Hellman Key Exchange]] based on [[Diffie-Hellman Problem]];