Home

Let n be a positive integer. There exists a primitive root mod n exactly in the following cases and no others:

1. n = 1, 2, or 4
2. n = p^r where p is an odd prime
3. n = 2p^r where p is an odd prime

Definition

$\phi(n)$ is the number of integers between 0 and n-1 who is coprime with n. $\phi(n):=|{a: 0 \leqslant a<n \wedge(a, n)=1}|$

Law of Quadratic Reciprocity Let p and q be odd primes. Then

\[ \left( \frac { p } { q } \right) \left( \frac { q } { p } \right) = ( - 1 ) ^ { \frac { p - 1 } { 2 } \frac { q - 1 } { 2 } } \iff \begin{cases} (\frac{p}{q})=(\frac{q}{p}) &\text{if either p or q is }1\bmod 4\\ (\frac{p}{q})=-(\frac{q}{p}) &\text{if both p and q are }3\bmod 4 \end{cases} \]

Gauss’s lemma Let p be an odd prime, q be an integer coprime to p. Take the least residues of \( Q=\{q, 2q,\cdots,\frac{p-1}{2} q \} \), i.e. reduce them to integers in \( [0, p-1] \). Let u be the number of members in this set that are greater than p/2. Then

\[ (\frac{q}{p})=-1^u \]

Euler’s Criterion Let p be an odd prime, and a an integer not divisible by p. Then

\[ (\frac{a}{p}) \equiv a^{\frac{p-1}{2}}\mod p \]

Primitive root theorem. Let p be a prime. Then for any d dividing \( p-1 \), there are exactly \( \phi(d) \) elements of order d in \( (\mathbb Z / p \mathbb Z)^\times \). In particular there are \( \phi(p-1) \) primitive roots mod p.

Fundamental Theorem of Algebra. Every polynomial of degree greater than zero with complex coefficients has at least one zero.