--- title: "Primitive Roots and the Units Modulo n" description: "Ask when the units modulo n are generated by a single element, and settle which n admit one." canonical: https://lightmysky.com/learn/mathematics/primitive-roots-and-the-units-modulo-n-mt_KwTDckkMze source: https://lightmysky.com/learn/mathematics/primitive-roots-and-the-units-modulo-n-mt_KwTDckkMze.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Primitive Roots and the Units Modulo n Ask when the units modulo n are generated by a single element, and settle which n admit one. Subject: Mathematics · Area: Number Theory · Ages 20 to 21 Page: https://lightmysky.com/learn/mathematics/primitive-roots-and-the-units-modulo-n-mt_KwTDckkMze ## Ready when they can - Compute the order of an element modulo n and relate it to the totient - Find a primitive root modulo a small prime and use it to index the other units - State which moduli have primitive roots and give a modulus that does not ## Lesson: Finding a generator for the units Fix n >= 2. A unit modulo n is a remainder coprime to n; phi(n) counts these units. The order of a unit a is the least positive k with a^k congruent to 1 modulo n. Its order divides phi(n). To see this, divide phi(n) by the order. Euler's theorem makes the remainder exponent return 1 too, so minimality forces that remainder to be zero. **Example.** A primitive root is a unit of order phi(n). Its powers reach every unit. Modulo 11, successive powers of 7 give 7, 5, 2, 3, 10, 4, 6, 9, 8, 1. The first return to 1 is at exponent 10. Since phi(11) = 10, 7 is a primitive root. *(drawing: Each entry gives a power of 7 reduced modulo 11. All ten units appear.)* Check coprimality first. Multiply by the base and reduce modulo n until 1 first appears. The candidate is primitive exactly when that exponent equals phi(n). A shorter test sets m = phi(n): a unit is primitive if and only if a^(m/q) differs from 1 modulo n for every prime divisor q of m. Any proper divisor d of m divides m/q for at least one such q. For n >= 2, primitive roots exist exactly for n = 2, 4, p^k or 2p^k, where p is an odd prime and k >= 1. For example, 27 and 54 have the required forms. Powers of 2 greater than 4 do not. To disprove existence directly, show that every unit has order smaller than phi(n). If g is primitive and m = phi(n), exponents 0 through m - 1 index all units once. To solve g^t congruent to b, locate b in this power list. All solutions for t agree modulo m. Multiplication of units adds their exponent indices. For example, modulo 11, 7^8 gives 9, so 7^t is congruent to 9 exactly when t is congruent to 8 modulo 10. If g has order m, then g^r has order m/gcd(m,r). Indeed, (g^r)^k = g^(rk) returns 1 exactly when m divides rk. The least positive k satisfying this is m/gcd(m,r). This lets you find the order of a generator's power without building another full power list. **Recap.** Order is the first positive exponent returning 1. A primitive root has order phi(n), so its powers reach every unit. *The lesson, questions, worked solutions and base flashcards were written for this dataset.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Fermat's Little Theorem and Euler's Theorem](https://lightmysky.com/learn/mathematics/fermats-little-theorem-and-eulers-theorem-mt_7wW4z4Eidx) ## Optional connections - [Groups, Subgroups and Symmetry](https://lightmysky.com/learn/mathematics/groups-subgroups-and-symmetry-mt_HFAhcaGo2L) ## Opens up - [Quadratic Residues and the Law of Reciprocity](https://lightmysky.com/learn/mathematics/quadratic-residues-and-the-law-of-reciprocity-mt_0KS9eTCY4p)