[:primitive element:] • Given an α\alpha within some ring, the order of α\alpha is the minimum NN for which αN=1\alpha^N = 1generalized Euler's theorem guarantees that always NR×N \leq \lvert R^\times \rvert • If the order of α\alpha is this maximum R×\lvert R^\times \rvert, we call α\alpha a primitive element (or primitve root when we are working in a field) • Once you know one primitive element, there's an easy way to find the rest, but idk what that is. Check the book? Something to do with GCD or relative primality or something. • • For pp prime, we know αZ/p\alpha \in \mathbb Z/p is a primitive element iff • for each prime factor cc of p1p-1 we have that α(p1)/c≢1\alpha^{(p-1)/c} \not\equiv 1 mod pp • For PP irreducible and of degree nn, we know α(x)Fq[x]/P\alpha(x) \in \mathbb F_q[x]/P is a primitive element iffα(x)qn11\alpha(x)^{q^n-1} \equiv 1 mod PPbut for each prime factor cc of qn1q^n - 1 we have that α(x)(qn1)/c≢1\alpha(x)^{(q^n-1)/c} \not\equiv 1 • • Facts about order: • If α\alpha has order dd, then αN=1    dN\alpha^N = 1 \iff d \mid N • Corollary: every power αk\alpha^k of α\alpha has an order dividing dd • If α\alpha has order dd and d=efd=ef then αe\alpha^e has order ff • Partial proof: (αe)f=αd=1(\alpha^ e)^f = \alpha^d = 1, so the order of αe\alpha ^e is at most ff • If α1,α2\alpha_1, \alpha_2 have relatively prime respective orders d1,d2d_1, d_2, then α1α2\alpha_1 \alpha_2 has order d1d2d_1 d_2 • • From these facts, we can conclude that every finite field Fq\mathbb F_q has a primitive root α\alpha • Proof is nonobvious • Then α\alpha has order q1q - 1 • Also, there are exactly φ(q1)\varphi(q-1) primitive roots (for φ\varphi the Euler phi function) Referenced by: