初等数论与抽象代数

本笔记基于上海交通大学 邢朝平老师 2025-2026 学年春季学期 信息安全数学基础2 课程教学内容进行整理，若有侵权请联系删除。

▶

Notation

定义：Definition (Def)
定理：Theorem (Thm)
证明：Proof (Pf)
推论：Corollary (Cor)
公理：Axiom
引理：Lemma
示例：Example (e.g.)
猜想：Conjecture (Conj) / Hypothesis (Hyp)
不失一般性：Without Loss of Generality (WLG / WLOG)
使得：such that (s.t.)
即：that is (i.e.)
当且仅当：if and only if (iff)

Chapter 1. Divisibility

Divisibility

Def 1.1 Divisibility: Let \(a, b \in \mathbb{Z}\), \(b \ne 0\), if \(\exists q \in \mathbb{Z}\) s.t. \[a = qb\] Then we say that \(b\) devides \(a\) or \(a\) is divisible by \(b\), written as \(b\mid a\), and \(b\) is a divisor of \(a\), or \(a\) is a multiple of \(b\).
Thm 1.2 Properties of divisibility: Let \(a,b,c,d \in \mathbb{Z}\), then
1. \(\forall c \in \mathbb{Z}, b\mid a \implies bc\mid ac\)
2. \(c\mid b,~b\mid a \implies c \mid a\)
3. \(a\mid b,~b\mid a \implies a=\pm b\)
4. \(d\mid a,~d\mid b \implies \forall u,v \in \mathbb{Z},~d \mid (ua+vb)\)
  
  ▶
  Proof
  
  Since \(d\mid a\) and \(d\mid b\), we have \(\exists x,y \in \mathbb{Z}\) s.t. \(a=dx\) and \(b=dy\), thus \(ua+vb=u(dx)+v(dy)=d(ux+vy)\), thus \(d\mid (ua+vb)\).
5. (Cor) \(\forall u,v\in\mathbb{Z},~\gcd(a,b) \mid (ua+vb)\)
Axiom 1.3 Well Ordering Principle (WOP): Let \(S \cap \mathbb{Z}^+ \ne \varnothing\), then
1. There is a least positive integer in \(S\)
2. There is a non-negative integer in \(S\)
Thm 1.4 Long division: Let \(a,b \in \mathbb{Z}, b > 0\), then there exists a unique pair \((q,r)\in\mathbb{Z}^2\), \(0\le r<b\) s.t. \(a=qb+r\). We call \(q\) the quotient and \(r\) the remainder of \(a\) divided by \(b\).
▶
Proof
- Uniqueness: Let \((q_1,r_1)\) and \((q_2,r_2)\) be two pairs satisfying the condition, then \(a=q_1 b + r_1 = q_2 b + r_2\), thus \((q_1-q_2) b = r_2 - r_1\). Since \(0\le r_1, r_2 < b\), we have \(-b < r_2 - r_1 < b\), thus \(q_1=q_2\) and \(r_1=r_2\).
- Existence: Let \(S=\{a-xb: x\in\mathbb{Z}\}\), by WOP, there is a least non-negative integer \(r\) in \(S\), then \(\exists q \in \mathbb{Z}\) s.t. \(r=a-qb\). Suppose \(r\ge b\), then \(r-b=a-(q+1)b \in S\), and \(r-b\ge 0\), contradicting the definition of \(r\). Thus, \(0\le r < b\).

Greatest Common Divisor

Def 1.5 Greatest Common Divisor (GCD): Let \((a,b)\in\mathbb{Z}^2 \backslash \{(0,0)\}\), a GCD of \((a,b)\) is defined to be a positive integer \(d\) s.t.
1. \(d\mid a,~d\mid b\)
2. \(d'\mid a,~d'\mid b \implies d'\mid d\)
Furthermore, we say \(a\) and \(b\) are co-prime if \(\gcd(a,b)=1\).
Thm 1.6: The GCD of \(a,b\) exists and is unique, denoted by \(\gcd(a,b)\).
▶
Proof
- Uniqueness: Let \(d_1, d_2\) be two GCDs of \((a,b)\), then \(d_1\mid d_2\) and \(d_2\mid d_1\), by Thm 1.2(3), we have \(d_1=\pm d_2\). Since \(d_1, d_2 > 0\), we have \(d_1=d_2\).
- Existence: Consider \(S=\{ua+vb: u,v\in\mathbb{Z}\}\), WLG, we assume \(b\ne 0\), then \(\pm b\in S\), \(S \cap \mathbb{Z}^+ \ne \varnothing\). By WOP, there is a least positive integer \(d\) in \(S\), then \(\exists u_0, v_0 \in \mathbb{Z}\) s.t. \(d=u_0a+v_0b\). We claim that \(d\) is a GCD of \((a,b)\).
  
  \(d\mid a\): Let \(a=qd+r, 0\le r<d\), then \(r=a-qd=a-(qu_0a+qv_0b)=(1-qu_0)a+(-qv_0)b \in S\), this forces \(r=0\) due to minimality of \(d\), thus \(d\mid a\).
  
  \(d\mid b\): Similar to \(d\mid a\).
  
  Let \(d'\) be a common divisor of \(a,b\), then \(d'\mid (u_0a+v_0b)\), thus \(d'\mid d\).
  
  Thus, \(d=\gcd(a,b)\).
Cor 1.7 Bézout’s Identity: \(\forall (a,b)\in\mathbb{Z}^2\backslash \{(0,0)\}\), then \(\exists u,v \in \mathbb{Z}\) s.t. \(\gcd(a,b)=ua+vb\)
Thm 1.8 Properties of GCD: Let \(a,b,c,a_i\in\mathbb{Z}\), then
1. \(m>0 \implies m\cdot \gcd(a,b)=\gcd(ma, mb)\)
2. \(\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1\)
3. \(\gcd(a_i,b)=1, i=1,2,\cdots,t \implies \gcd\left(\prod_{i=1}^t a_i, b\right)=1\)
4. \(c\mid ab,~\gcd(c,b)=1 \implies c\mid a\)
5. \(\forall r\in\mathbb{Z}, \gcd(a,b)=\gcd(a, b+ra)\)
▶
Proof
1. Let \(d=\gcd(a,b), d'=\gcd(ma, mb)\),
  
  \(d\mid a,~d\mid b\), thus \(md\mid ma, md\mid mb\), thus \(md \mid d'\)
  
  \(d'\mid ma,~d'\mid mb\), thus \(\frac{d'}{m}\mid a, \frac{d'}{m}\mid b\), thus \(\frac{d'}{m} \mid d\), thus \(d' \mid md\)
  
  Thus, \(md=d'\)
2. Let \(d=\gcd(a,b)\), then \(\gcd(\frac{a}{d},\frac{b}{d})=\frac{1}{d}\gcd(a,b)=1\)
3. Since Bézout’s Identity, \(\exists u_i,v_i\in\mathbb{Z}\) s.t. \(u_i a_i+v_i b=1\), thus \(\prod_{i=1}^t(u_i a_i + v_i b) = 1 = \prod_{i=1}^t u_i a_i + b \sum_{i=1}^t v_i \prod_{j\ne i} u_j a_j\), thus \(\gcd(\prod_{i=1}^t a_i, b)=1\).
4. Since \(c\mid ab\), \(\exists k\in\mathbb{Z}\) s.t. \(ab=kc\). Since \(\gcd(c,b)=1\), \(\exists u,v\in\mathbb{Z}\) s.t. \(uc+vb=1\), thus \(a=a(uc+vb)=uac+vab=uac+vkc=c(ua+vk)\), thus \(c\mid a\).
5. Let \(d=\gcd(a,b), d'=\gcd(a, b+ra)\),
  
  \(d\mid a,~d\mid b\), thus \(d\mid a, d\mid (b+ra)\), thus \(d\mid d'\)
  
  \(d'\mid a,~d'\mid (b+ra)\), thus \(d'\mid a, d'\mid b\), thus \(d' \mid d\)
  
  Thus, \(d=d'\)

Euclidean Algorithm

Thm 1.9 Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b\), we can compute \(r_2, r_3, \cdots\) by long division: \[ \begin{cases} r_0=q_1r_1+r_2, & 0\le r_2<r_1 \\ r_1=q_2r_2+r_3, & 0\le r_3<r_2 \\ \cdots \\ r_{i-1}=q_ir_i+r_{i+1}, & 0\le r_{i+1}<r_i \\ \cdots \\ r_{n-1}=q_{n}r_n, & r_{n+1}=0 \end{cases} \]

then \(\gcd(r_{i-1},r_i)=\gcd(r_i, r_{i+1})\) for all \(i=1,2,\cdots,n-1\). In particular, \(\gcd(a,b)=\gcd(r_0,r_1)=\cdots=\gcd(r_{n-1},r_n)=r_n\)
- the matrix form of Euclidean Algorithm: \[ \begin{pmatrix}a \\ b\end{pmatrix} =\begin{pmatrix}r_0 \\ r_1\end{pmatrix} =\begin{pmatrix}q_1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}r_1 \\ r_2\end{pmatrix} =\cdots =\begin{pmatrix}q_1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}q_2 & 1 \\ 1 & 0\end{pmatrix}\cdots\begin{pmatrix}q_n & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}r_n \\ 0\end{pmatrix} \]
▶
Proof

By Thm 1.8(5), we have

\[ \begin{aligned} \gcd(r_{i-1},r_i)&=\gcd(q_ir_i+r_{i+1}, r_i) \\ &=\gcd(r_{i+1}, r_i) \\ &=\gcd(r_i, r_{i+1}) \end{aligned} \]
Thm 1.10 Extended Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b, s_0=1, s_1=0, t_0=0, t_1=1\), we can compute \(r_2, r_3, \cdots\) by long division, and compute \(s_i,t_i\) by \[ \begin{cases} s_{i+1}=s_{i-1}-q_is_i \\ t_{i+1}=t_{i-1}-q_it_i \end{cases} \]

then \(r_i=a s_i+b t_i\) for all \(i\ge 0\). In particular, \(\gcd(a,b)=r_n=a s_n+b t_n\).
- the matrix form of Extended Euclidean Algorithm: \[ \begin{pmatrix}s_i & s_{i+1}\\ t_i & t_{i+1}\end{pmatrix}=\begin{pmatrix}s_{i-1} & s_i\\t_{i-1} & t_i\end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & -q_i\end{pmatrix},\quad \begin{pmatrix}s_0 & s_1\\t_0 & t_1\end{pmatrix}=\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix} \]
▶
Proof
We can prove by induction that \(r_i=a s_i+b t_i\) for all \(i\ge 0\).
- Base case:
  
  \(i=0\), \(r_0=a s_0+b t_0=a\cdot 1 + b\cdot 0=a\)
  
  \(i=1\), \(r_1=a s_1+b t_1=a\cdot 0 + b\cdot 1=b\)
- Induction step: Assume \(r_i=a s_i+b t_i\) and \(r_{i-1}=a s_{i-1}+b t_{i-1}\), then \[ \begin{aligned} r_{i+1}&=r_{i-1}-q_i r_i \\ &=(a s_{i-1}+b t_{i-1})-q_i (a s_i+b t_i) \\ &=a (s_{i-1}-q_i s_i)+b (t_{i-1}-q_i t_i) \\ &=a s_{i+1}+b t_{i+1} \end{aligned} \]

Least Common Multiple

Def 1.11 Least Common Multiple (LCM): Let \(a,b\in\mathbb Z^*\), a LCM of \((a,b)\) is defined to be a positive integer \(D\) s.t.
1. \(a\mid D,~b\mid D\)
2. \(a\mid D',~b\mid D'\implies D\mid D'\)
Thm 1.12: The LCM of \(a,b\) exists and is unique, denoted by \(\mathrm{lcm}(a,b)\).
▶
Proof
- Uniqueness: Let \(D_1, D_2\) be two LCMs of \((a,b)\), then \(D_1\mid D_2\) and \(D_2\mid D_1\), by Thm 1.2(3), we have \(D_1=\pm D_2\). Since \(D_1, D_2 > 0\), we have \(D_1=D_2\).
- Existence: Consider \(S=\{x\in\mathbb{Z}^+: a\mid x, b\mid x\}\), since \(|ab|\in S\), \(S\ne \varnothing\). By WOP, there is a least positive integer \(D\) in \(S\), then \(\exists u_0, v_0 \in \mathbb{Z}\) s.t. \(D=u_0a=v_0b\). We claim that \(D\) is a LCM of \((a,b)\).
  
  \(a\mid D\) and \(b\mid D\) is trivial.
  
  Let \(D'\) be a common multiple of \(a,b\), then \(\exists q,r \in \mathbb{Z}\) s.t. \(D'=qD+r\) with \(0\le r<D\). Since \(a\mid D'\) and \(a\mid D\), we have \(a\mid r\), similarly, \(b\mid r\), thus \(r\in S\). This forces \(r=0\) due to minimality of \(D\), thus \(D\mid D'\).
  
  Thus, \(D=\mathrm{lcm}(a,b)\).
Thm 1.13 Properties of LCM: Let \(a,b,c\in\mathbb{Z}^*\), then
1. \(m>0 \implies m\cdot \mathrm{lcm}(a,b)=\mathrm{lcm}(ma, mb)\)
2. \(\gcd(a,b)=1 \iff \mathrm{lcm}(a,b)=|ab|\)
  - \(\forall 1\leq i\neq j\leq t, \gcd(m_i,m_j)=1 \iff \mathrm{lcm}(m_1, m_2, \cdots, m_t) = \prod_{i=1}^t m_i\)
3. \(\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|\)
▶
Proof
1. Let \(D=\mathrm{lcm}(a,b), D'=\mathrm{lcm}(ma, mb)\),
  
  \(a\mid D\) and \(b\mid D\), thus \(ma\mid mD\) and \(mb\mid mD\), thus \(D' \mid mD\)
  
  \(ma\mid D'\) and \(mb\mid D'\), thus \(a\mid \frac{D'}{m}\) and \(b\mid \frac{D'}{m}\), thus \(D\mid \frac{D'}{m}\), thus \(mD \mid D'\)
  
  Thus, \(mD=D'\)
2. WLG, we assume \(a,b>0\). Let \(D=\mathrm{lcm}(a,b)\), prove the \(\implies\) direction as follows:
  
  Because \(a\mid ab, b\mid ab\), we have \(D\mid ab\).
  
  Since \(a\mid D\) and \(b\mid D\), thus \(\exists c\in \mathbb{Z}\) s.t. \(D=ac\), thus \(b\mid ac\), since \(\gcd(a,b)=1\), we have \(b\mid c\), thus \(\exists d\in\mathbb{Z}\) s.t. \(c=db\), thus \(D=ac=dab\), i.e. \(ab\mid D\).
  
  Thus, \(D=|ab|\).
3. WLG, we assume \(a,b>0\). Let \(d=\gcd(a,b)\), then \(\gcd(\frac{a}{d},\frac{b}{d})=1\) by Thm 1.8(2), thus \(\mathrm{lcm}(a,b) = d\cdot \mathrm{lcm}(\frac{a}{d},\frac{b}{d})=d\cdot \frac{a}{d}\cdot \frac{b}{d}=\frac{ab}{d}\), thus \(\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|\).

Prime

Def 1.14 Prime: A positive integer \(p>1\) is called prime if its only positive divisors are \(1\) and \(p\). Otherwise, we call it composite.
Thm 1.15 Equivalent definition of prime: \(p>1\) is a prime \(\iff\) \(\forall a,b\in \mathbb{Z}, p\mid ab \implies p\mid a\) or \(p\mid b\).
▶
Proof
1. (\(\implies\))
  
  Case 1: \(\gcd(p,b)=1\). Since \(p \mid ab\) and \(\gcd(p,b)=1\), by Thm 1.8(4), we have \(p\mid a\).
  
  Case 2: \(\gcd(p,b)>1\). Let \(d=\gcd(p,b)\), so \(d\mid p\) and \(d\mid b\). Since \(p\) is a prime, \(d\) can only be \(1\) or \(p\), thus \(d=p\), thus \(p\mid b\).
2. (\(\impliedby\)) Suppose \(p\) were not a prime, then \(\exists 1<u<p\) s.t. \(u\mid p\), thus \(p=\frac{p}{u}\cdot u \implies p\mid \frac{p}{u}\cdot u \implies p\mid \frac{p}{u}\) or \(p\mid u\), both of which are impossible since \(1<u<p\). Contradiction, thus \(p\) is a prime.
Thm 1.16: There are infinitely many primes.

▶
Proof by Euclid's method

Suppose there are only finitely many primes \(p_1, p_2, \cdots, p_k\), consider \(n=\prod_{i=1}^k p_i + 1\) must be a composite number, then \(\exists p_i\) s.t. \(p_i\mid n\), thus \(p_i\mid (n-\prod_{i=1}^k p_i)\implies p_i\mid 1\), contradiction, thus there are infinitely many primes.

▶
Proof by Saliak's method

Chose \(n>1\), then \(\gcd(n, n+1)=1\). Let \(p_1, p_2\) be a prime divisor of \(n\) and \(n+1\) respectively, then \(p_1\ne p_2\), thus \(n(n+1)\) has at least two distinct prime divisors. Then consider \(n(n+1)(n(n+1)+1)\), it has at least three distinct prime divisors. By induction, we can show that there are infinitely many primes.
Thm 1.17 Fundamental Theorem of Arithmetic: Any positive integer \(n>1\) can be uniquely factorized into a product of primes with \(p_1\le p_2 \le \cdots \le p_m\) \[ n=p_1\cdot p_2 \cdots p_m \]
- Notation: Let \(p\in \mathbb{P}\), \(n\in \mathbb{Z}^+\), \(v_p(n)\) denotes the largest non-negative integer \(k\) s.t. \(p^k\mid n\). Then Thm 1.17 can be restated as \[ n=\prod_{p\in \mathbb{P}} p^{v_p(n)} \]
▶
Proof
- Existence: By induction on \(n\).
  
  Base case: \(n=2\), obviously true.
  
  Induction step: \(n>2\), if \(\frac{n}{p_1} = 1\) for some prime divisor \(p_1\), then \(n=p_1\) is a product of primes. Otherwise, \(\frac{n}{p_1}\in \mathbb{Z}\) and \(1<\frac{n}{p_1}<n\). By induction hypothesis, \(\frac{n}{p_1}\) can be factorized into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) can be factorized into a product of primes.
- Uniqueness: By induction on \(n\).
  
  Base case: \(n=2\), obviously true.
  
  Induction step: \(n>2\), let \(p_1\) be the smallest prime divisor of \(n\), then \(\frac{n}{p_1}\in \mathbb{Z}\) and \(1\leq\frac{n}{p_1}<n\). By induction hypothesis, \(\frac{n}{p_1}\) has a unique factorization into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) has a unique factorization into a product of primes.
Cor 1.18: Let \(m,n\in \mathbb{Z}^+\), then
1. \[\gcd(m,n)=\prod_{p\in \mathbb{P}} p^{\min\{v_p(m), v_p(n)\}}\]
2. \[\mathrm{lcm}(m,n)=\prod_{p\in \mathbb{P}} p^{\max\{v_p(m), v_p(n)\}}\]
Thm 1.19: There are infinitely many primes of the form \(4n+3\).
▶
Proof
- Suppose there are only finitely many primes of the form \(4n+3\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the other primes must be of the form \(4n+1\) or \(2\). Consider the number: \[ N = 4\prod_{i=1}^k p_i - 1 \] then we have \(N \equiv 3 \pmod{4}\). Since \(N\) is of the form \(4n+3\), it must be a composite number.
- Since \(N\) is odd, \(2\nmid N\), suppose \(N\) is a composite number. Thus, any prime divisor of \(N\) must be of the form \(4n+1\) or \(4n+3\).
  
  If all prime divisors of \(N\) are of the form \(4n+1\), then \(N \equiv 1 \pmod{4}\) since \(\prod_{i=1}^t (4n_i+1) \equiv 1 \pmod{4}\), contradiction.
  
  Thus, \(\exists i\in \{1,2,\dots,k\}\) s.t. \(p_i\mid N\), thus \(p_i\mid (4\prod_{i=1}^k p_i - N)\), thus \(p_i\mid 1\), contradiction.
- Thus, \(N\) is a new prime of the form \(4n+3\), contradiction. Thus, there are infinitely many primes of the form \(4n+3\).
Thm 1.20: There are infinitely many primes of the form \(3n+2\).
▶
Proof
- Suppose there are only finitely many primes of the form \(3n+2\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the other primes must be of the form \(3n+1\) or \(3\). Consider the number: \[ N = 3\prod_{i=1}^k p_i - 1 \] then we have \(N \equiv 2 \pmod{3}\). Since \(N\) is of the form \(3n+2\), it must be a composite number.
- Since \(3\nmid N\), thus any prime divisor of \(N\) must be of the form \(3n+1\) or \(3n+2\).
  
  If all prime divisors of \(N\) are of the form \(3n+1\), then \(N \equiv 1 \pmod{3}\) since \(\prod_{i=1}^t (3n_i+1) \equiv 1 \pmod{3}\), contradiction.
  
  Thus, \(\exists i\in \{1,2,\dots,k\}\) s.t. \(p_i\mid N\), thus \(p_i\mid (3\prod_{i=1}^k p_i - N)\), thus \(p_i\mid 1\), contradiction.
- Thus, \(N\) is a new prime of the form \(3n+2\), contradiction. Thus, there are infinitely many primes of the form \(3n+2\).
Thm 1.21: There are infinitely many primes of the form \(4n+1\).
▶
Proof By Quadratic Residue
- Suppose there are only finitely many primes of the form \(4n+1\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Consider the number: \[ N = \left(2\prod_{i=1}^k p_i\right)^2 + 1 = 4\left(\prod_{i=1}^k p_i\right)^2 + 1 \] then we have \(N \equiv 1 \pmod{4}\). Since \(N\) is of the form \(4n+1\), it must be a composite number.
- Let \(p\) be a prime divisor of \(N\), obviously \(p\ne 2\) since \(N\) is odd and \(p\neq p_i\) since \(p_i\nmid N\). Thus, we have \[ \left(2\prod_{i=1}^k p_i\right)^2 \equiv -1 \pmod{p} \] which means \(-1\) is a quadratic residue modulo \(p\)
- Thus \(\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=1\), thus \(p\equiv 1 \pmod{4}\), thus \(p\) is a new prime of the form \(4n+1\), contradiction. Thus, there are infinitely many primes of the form \(4n+1\).

Chapter 2. Congruences

Congruences

Def 2.1 Congruence: Let \(a,b\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), we say \(a\) is congruent to \(b\) modulo \(m\) if \[m\mid (a-b)\] Denoted by \(a\equiv b \pmod m\).
Thm 2.2 Properties of Congruences: Let \(a,b,c,d\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), then
1. \(a\equiv b \pmod m\) and \(c\equiv d \pmod m \implies\)
  - \(a+c\equiv b+d \pmod m\)
  - \(a-c\equiv b-d \pmod m\)
  - \(ac\equiv bd \pmod m\)
2. \(m>\gcd(m,c), ac\equiv bc \pmod m \implies a\equiv b \pmod{\frac{m}{\gcd(m,c)}}\)
▶
Proof
1. We only prove the last one. \(\exists u,v\in \mathbb{Z}\) s.t. \(a-b=um\) and \(c-d=vm\), thus \(ac-bd=ac-ad+ad-bd=a(c-d)+(a-b)d=avm+umd=m(av+ud)\), thus \(ac\equiv bd \pmod m\).
2. Let \(d=\gcd(m,c)\), then \(m\mid(a-b)c \implies \frac{m}{d}\mid (a-b)\frac{c}{d}\), since \(\gcd(\frac{m}{d},\frac{c}{d})=1\), we have \(\frac{m}{d}\mid a-b\), i.e. \(a\equiv b \pmod{\frac{m}{\gcd(m,c)}}\).

Residue Classes

Def 2.3 Residue Class: Let \(r\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), the residue class of \(r\) modulo \(m\) is defined to be \[ \begin{aligned} {[r]}_{m} &=\{x\in \mathbb{Z}: x\equiv r \pmod m\} \\ &=\{r+im: i\in \mathbb{Z}\} \\ & = r+m\mathbb{Z} \end{aligned} \]

If there is no confusion, we simply denote \([r]_m\) by \(\bar{r}\) and even \(r\).
Thm 2.4 Properties of Residue Classes:
1. \(\forall r_1,r_2\in \mathbb{Z}\), we have \([r_1]_m=[r_2]_m\) or \([r_1]_m\cap [r_2]_m=\emptyset\).
2. \(\bigcup_{i=0}^{m-1} [i]_m=\mathbb{Z}\), i.e. \(\{[0]_m,[1]_m,\cdots,[m-1]_m\}\) is a partition of \(\mathbb{Z}\).
▶
Proof
1. if \([r_1]_m\cap [r_2]_m\neq \emptyset\), choose \(r\in [r_1]_m\cap [r_2]_m\), then \(r\equiv r_1 \pmod m, r\equiv r_2 \pmod m\), thus \(r_1\equiv r_2 \pmod m\). So \(\forall x\in [r_1]_m\), we have \(x\equiv r_1 \equiv r_2 \pmod m\), thus \(x\in [r_2]_m\), i.e. \([r_1]_m\subseteq [r_2]_m\). Similarly, we can prove \([r_2]_m\subseteq [r_1]_m\), thus \([r_1]_m=[r_2]_m\).
2. \(\forall 0\leq i<j\leq m-1\), we have \(i\neq j \pmod m\), thus \([i]_m\cap [j]_m=\emptyset\). Then \(\forall x\in \mathbb{Z}\), by the division algorithm, \(\exists q,r\in \mathbb{Z}\) s.t. \(x=qm+r\) and \(0\leq r<m\), thus \(x\in [r]_m\), i.e. \(\bigcup_{i=0}^{m-1} [i]_m=\mathbb{Z}\).
Def 2.5 Complete Residue System: Let \(r_1,r_2,\cdots,r_m\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), if
1. \(\forall i\neq j, [r_i]_m\cap [r_j]_m=\emptyset\)
2. \(\bigcup_{i=1}^m [r_i]_m=\mathbb{Z}\)
then \(\{[r_1]_m,\cdots,[r_m]_m\}\) is called a complete residue system modulo \(m\), denoted by \(\mathbb{Z}_m\).
- In particular, \(\{[0]_m,[1]_m,\cdots,[m-1]_m\}\) is called the canonical complete residue system modulo \(m\).
- If \([r_1]_m,\cdots,[r_m]_m\) is a complete residue system modulo \(m\), then \[ \begin{aligned} \mathbb{Z}_m &=\{[r_1]_m,\cdots,[r_m]_m\} \\ &=\{[0]_m,[1]_m,\cdots,[m-1]_m\} \\ &=\{\bar{0},\bar{1},\cdots,\overline{m-1}\} \\ &=\{0,1,\cdots,m-1\} \end{aligned} \]
Def 2.6 Addition and Multiplication: Define addition \(+\) and multiplication \(\cdot\) on \(\mathbb{Z}_m\) as follows: \(\forall a,b\in \mathbb{Z}\), \[ \begin{aligned} \bar{a}+\bar{b} &=\overline{a+b} \\ \bar{a}\cdot \bar{b} &=\overline{ab} \end{aligned} \]
- Claim: \(+\) and \(\cdot\) defined above are well-defined, i.e. if \(\bar{a}=\bar{a}_1\) and \(\bar{b}=\bar{b}_1\), then \(\overline{a+b}=\overline{a_1+b_1}\) and \(\overline{ab}=\overline{a_1b_1}\).
  
  ▶
  Proof
  
  Since \(\bar{a}=\bar{a}_1\) and \(\bar{b}=\bar{b}_1\), we have \(a\equiv a_1 \pmod m, b\equiv b_1 \pmod m\), thus \(\exists u,v\in \mathbb{Z}\) s.t. \(a-a_1=um\) and \(b-b_1=vm\), thus \((a+b)-(a_1+b_1)=(a-a_1)+(b-b_1)=um+vm=(u+v)m\), thus \(\overline{a+b}=\overline{a_1+b_1}\). Similarly, we can prove \(\overline{ab}=\overline{a_1b_1}\).
- Conclusion: \(\mathbb{Z}_m\) is a commutative ring with zero element \(\bar{0}\) and multiplicative identity element \(\bar{1}\).
Def 2.7 Invertible Element: An element \(\bar{r}\in \mathbb{Z}_m\) is called invertible if there exists \(\bar{r}'\in \mathbb{Z}_m\) s.t. \[\bar{r}\cdot \bar{r}'=\bar{1}\] In this case we call \(\bar{r}'\) the inverse of \(\bar{r}\), denoted by \(\bar{r}^{-1}\).
- Every element \(\bar{r}\in \mathbb{Z}_m\) have the additive inverse \(-\bar{r}=\overline{-r}\) since \(\bar{r}+(-\bar{r})=\overline{r+(-r)}=\bar{0}\), but not every element \(\bar{r}\in \mathbb{Z}_m\) have the multiplicative inverse.
Thm 2.8: Let \(r\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), then \(\bar{r}\in \mathbb{Z}_m\) is multiplicative invertible \(\iff \gcd(r,m)=1\). In this case, the inverse is unique, denoted by \(\bar{r}^{-1}\).
▶
Proof
1. \(\implies\): Since \(\bar{r}\) is invertible, there exists \(\bar{r}'\in \mathbb{Z}_m\) s.t. \(\bar{r}\cdot \bar{r}'=\bar{1}\), thus \(\overline{rr'}=\bar{1}\), thus \(rr'\equiv 1 \pmod m\), thus \(\exists u\in \mathbb{Z}\) s.t. \(rr'-1=um\), thus \(rr'-um=1\), thus \(\gcd(r,m)\mid 1\), thus \(\gcd(r,m)=1\).
2. \(\impliedby\): Since \(\gcd(r,m)=1\), by Bézout’s identity, \(\exists u,v\in \mathbb{Z}\) s.t. \(ur+vm=1\), thus \(ur\equiv 1 \pmod m\), thus \(\overline{ur}=\bar{1}\), thus \(\overline{u}\cdot \bar{r}=\bar{1}\), thus \(\bar{r}\) is invertible and \(\bar{r}^{-1}=\overline{u}\).
  
  Uniqueness: If \(\bar{r}\cdot \bar{u}_1=\bar{1}\) and \(\bar{r}\cdot \bar{u}_2=\bar{1}\), then \(u_1 r\equiv 1 \equiv u_2 r \pmod m\), thus \((u_1-u_2)r\equiv 0 \pmod m\), thus \(m\mid (u_1-u_2)r\). Due to \(\gcd(r,m)=1\), we have \(m\mid u_1-u_2\), thus \(\bar{u}_1=\bar{u}_2\).

Euler Function and Chinese Remainder Theorem

Def 2.9 Euler Function: For \(m\in \mathbb{Z}^+\), the Euler function \(\varphi(m)\) is defined to be the cardinality of invertible elements of the set \[\mathbb{Z}_m^* = \{\bar{r}\in \mathbb{Z}_m: \gcd(r,m)=1\}\] i.e. \(\varphi(m)=|\mathbb{Z}_m^*|\).
- Remark: \(\mathbb{Z}_m^*\) forms a multiplicative group with identity element \(\bar{1}\).
- Example: \(\varphi(1)=1\), \(\varphi(2)=1\), \(\varphi(3)=2\), \(\varphi(4)=2\), \(\varphi(5)=4\), \(\varphi(6)=2\), \(\varphi(7)=6\), \(\varphi(8)=4\), \(\varphi(9)=6\), \(\varphi(10)=4\).
Thm 2.10 Chinese Remainder Theorem: Let \(m_1,m_2,\cdots,m_r\in \mathbb{Z}^+\) be pairwise coprime integers \(\geq 2\), (i.e. \(\forall i\neq j, \gcd(m_i,m_j)=1\)), then \(\forall a_1,a_2,\cdots,a_r\in \mathbb{Z}\), the system of congruences \[ \begin{cases} x\equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \\ \cdots \\ x\equiv a_r \pmod {m_r} \end{cases} \]

has a unique solution modulo \(M=\prod_{i=1}^r m_i\), and the solution \(x=\sum_{i=1}^r a_i M_i y_i\), where \(M_i=\frac{M}{m_i}\) and \(y_i\) is the inverse of \(M_i\) in \(\mathbb{Z}_{m_i}\).
▶
Proof
- Uniqueness: If \(x_1\) and \(x_2\) are two solutions, then \(\forall 1\leq i\leq r, x_1\equiv a_i \equiv x_2 \pmod {m_i}\), thus \(x_1\equiv x_2 \pmod {m_i}\), since \(\gcd(m_i,m_j)=1\) for \(i\neq j\), we have \(x_1\equiv x_2 \pmod M\).
- Existence: Let \(M_i=\frac{M}{m_i}\), so \(\gcd(M_i,m_i)=1\), by Thm 2.8, there exists \(y_i\in \mathbb{Z}\) s.t. \(\overline{M_i}\cdot \overline{y_i}=\bar{1}\) in \(\mathbb{Z}_{m_i}\), thus \(M_i y_i\equiv 1 \pmod {m_i}\) and \(\forall j\neq i, M_i y_i\equiv 0 \pmod {m_j}\). Let \(x=\sum_{i=1}^r a_i M_i y_i\), then \(\forall 1\leq i\leq r, x\equiv a_i M_i y_i \equiv a_i \cdot 1 \equiv a_i \pmod {m_i}\), thus \(x\) is a solution.
Thm 2.11 Properties of Euler Function: Let \(m,n\in \mathbb{Z}^+\), then
1. \(m,n\geq 2, \gcd(m,n)=1 \implies \varphi(mn)=\varphi(m)\varphi(n)\)
2. \(\forall n\geq 2\), if \(n=\prod_{i=1}^k p_i^{r_i}\) with \(r_i\in \mathbb{Z}^+\) and \(p_i\) are distinct primes, then \[ \varphi(n)=\prod_{i=1}^k p_i^{r_i-1}(p_i-1)=n\prod_{p\mid n}(1-\frac{1}{p}) \]
▶
Proof
1. Claim that \(|\mathbb{Z}_{mn}^*|=|\mathbb{Z}_m^*||\mathbb{Z}_n^*|\). Consider the map \[ \begin{aligned} \pi: \mathbb{Z}_{mn}^* &\to \mathbb{Z}_m^* \times \mathbb{Z}_n^* \\ [r]_{mn} &\mapsto ([r]_m, [r]_n) \end{aligned} \]
  
  \(\pi\) is well-defined: \([r_1]_{mn}=[r_2]_{mn} \iff mn\mid (r_1-r_2) \iff m\mid (r_1-r_2)\) and \(n\mid (r_1-r_2) \iff [r_1]_m=[r_2]_m\) and \([r_1]_n=[r_2]_n\).
  
  \(\pi\) is injective: \(\forall ([r_1]_m, [r_2]_n)\in \mathbb{Z}_m^* \times \mathbb{Z}_n^*\), by the Chinese Remainder Theorem, then \(\exists r\in \mathbb{Z}\) s.t. \(r\equiv r_1 \pmod m\) and \(r\equiv r_2 \pmod n\), thus \(\pi([r]_{mn})=([r]_m, [r]_n)=([r_1]_m, [r_2]_n)\).
  
  So, \(\pi\) is a bijection, thus \(|\mathbb{Z}_{mn}^*|=|\mathbb{Z}_m^*||\mathbb{Z}_n^*|\), i.e. \(\varphi(mn)=\varphi(m)\varphi(n)\).
2. First consider \(n=p^r\) where \(p\) is a prime and \(r\in \mathbb{Z}^+\), consider \[ \mathbb{Z}_n \backslash \mathbb{Z}_n^* =\{\overline{0},\overline{1p},\overline{2p},\cdots,\overline{(p^{r-1}-1)p}\} \]
  
  then \(|\mathbb{Z}_n \backslash \mathbb{Z}_n^*|=p^{r-1}\), thus \[ \varphi(n)=|\mathbb{Z}_n^*|=|\mathbb{Z}_n|-|\mathbb{Z}_n \backslash \mathbb{Z}_n^*|=p^r-p^{r-1}=p^r(1-\frac{1}{p}) \]
  
  For general \(n\), let \(p_1,p_2,\cdots,p_k\) be the distinct prime divisors of \(n\), then \(n=\prod_{i=1}^k p_i^{r_i}\), thus \[ \varphi(n)=\prod_{i=1}^k \varphi(p_i^{r_i})=\prod_{i=1}^k p_i^{r_i}(1-\frac{1}{p_i})=n\prod_{p\mid n}(1-\frac{1}{p}) \]
Cor 2.12:
- Let \(p\) be a prime and \(r\in \mathbb{Z}^+\), then \(\varphi(p^r)=p^r-p^{r-1}\).
- \(\varphi(n)=n-1 \iff n\) is a prime.
  ▶
  Proof
  If \(n\) is a prime, then \(\varphi(n)=n-1\).
  
  If \(n\) is not a prime, then \(\exists 1<p<n\) s.t. \(p\mid n\), thus \(\gcd(p,n)=p\neq 1\), thus \(\bar{p}\not\in \mathbb{Z}_n^*\), thus \(\mathbb{Z}_n^* \subseteq \mathbb{Z}_n\backslash \{\bar{0},\bar{p}\}\), thus \(\varphi(n)=|\mathbb{Z}_n^*| \leq |\mathbb{Z}_n\backslash \{\bar{0},\bar{p}\}|=n-2<n-1\).
- Set \(\varphi(1)=1\), then \(\forall n\geq 1, \sum_{d\mid n} \varphi(d)=n\).
  
  ▶
  Proof
  
  Let \(n=\prod_{i=1}^k p_i^{e_i}\) be the canonical factorization, consider \[ \begin{aligned} \sum_{d\mid n} \varphi(d) &=\sum_{0\leq k_i\leq e_i} \varphi(p_1^{k_1}\cdots p_t^{k_t}) \\ &=\sum_{0\leq k_i\leq e_i} \varphi(p_1^{k_1})\cdots \varphi(p_t^{k_t}) \\ &=\prod_{i=1}^k \sum_{0\leq k_i\leq e_i} \varphi(p_i^{k_i}) \\ &=\prod_{i=1}^k\left(\varphi(p_i^0)+\sum_{1\leq k_i\leq e_i} \varphi(p_i^{k_i})\right) \\ &=\prod_{i=1}^k\left(1+\sum_{1\leq k_i\leq e_i} p_i^{k_i}-p_i^{k_i-1}\right) \\ &=\prod_{i=1}^k p_i^{e_i} \\ &=n \end{aligned} \]

Chapter 3. Primitive roots and discrete logarithm

Order

Thm 3.1 Euler’s Theorem: Let \(m\geq 2\), then \(\forall a\in \mathbb{Z}\) with \(\gcd(a,m)=1\), we have \(a^{\varphi(m)}\equiv 1 \pmod m\).
▶
Proof
- Since \(\gcd(a,m)=1\), then \(\bar{a}\in \mathbb{Z}_m^*\), \(\forall \bar{b}\in \mathbb{Z}_m^*\), we claim that \(\overline{ab}\in \mathbb{Z}_m^*\):
  
  Since \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), thus \(\gcd(ab,m)=1\), so \(\overline{ab}\in \mathbb{Z}_m^*\).
- Label all elements of \(\mathbb{Z}_m^*\) as \(\bar{a}_1,\bar{a}_2,\cdots,\bar{a}_{\varphi(m)}\), consider \(\mathbb{Z}'=\{\bar{a}\bar{a}_1,\bar{a}\bar{a}_2,\cdots,\bar{a}\bar{a}_{\varphi(m)}\}\subseteq \mathbb{Z}_m^*\), we claim that \(\mathbb{Z}'=\mathbb{Z}_m^*\)
  
  Since \(\bar{a}\bar{a}_i=\bar{a}\bar{a}_j\) implies \(\bar{a}_i=\bar{a}_j\), thus \(\bar{a}\bar{a}_i\neq \bar{a}\bar{a}_j\) for \(1\leq i<j\leq \varphi(m)\), so \(\mathbb{Z}'\) has \(\varphi(m)\) distinct elements, thus \(\mathbb{Z}'=\mathbb{Z}_m^*\).
- So, \(\prod_{i=1}^{\varphi(m)} \bar{a}_i=\prod_{i=1}^{\varphi(m)} \bar{a}\bar{a}_i=\bar{a}^{\varphi(m)}\prod_{i=1}^{\varphi(m)} \bar{a}_i\), thus \(\bar{a}^{\varphi(m)}=\bar{1}\), i.e. \(a^{\varphi(m)}\equiv 1 \pmod m\).
Thm 3.2 Little Fermat’s Theorem: If \(p\in \mathbb{P}\), then \(\forall a\in \mathbb{Z}\), \[ a^p\equiv a \pmod p \]
▶
Proof
- Case 1: \(p\mid a\), then \(a^p\equiv 0 \equiv a \pmod p\).
- Case 2: \(p\nmid a\), then \(\gcd(a,p)=1\) and \(a\in \mathbb{Z}_p^*\), by Thm 3.1, \(a^{\varphi(p)}=a^{p-1}\equiv 1 \pmod p\), thus \(a^p\equiv a \pmod p\).
Def 3.3 Order: Let \(m\geq 2\), \(\bar{a}\in \mathbb{Z}_m^*\), the order of \(\bar{a}\) is defined to be the least positive integer \(k\) satisfying \[ a^k\equiv 1 \pmod m \]
- Notation: Denote the order of \(\bar{a}\) by \(\mathrm{ord}_m(\bar{a})\).
▶
Proof
- Existence: Since \(\mathbb{Z}_m^*\) is finite, there exist \(i,j\) with \(0\leq i<j\leq \varphi(m)\) such that \(\bar{a}^i=\bar{a}^j\), thus \(\bar{a}^{j-i}=\bar{1}\), so there exists a positive integer \(k\) such that \(\bar{a}^k=\bar{1}\).
- Uniqueness: Let \(S=\{k\in \mathbb{Z}^+: a^k\equiv 1 \pmod m\}\), thus \(S\) contains positive integer. By WOP, there exists a least positive integer \(k_0\in S\), thus \(\mathrm{ord}_m(\bar{a})=k_0\).
Thm 3.4 Properties of order: Let \(m\geq 2\), \(\bar{a}\in \mathbb{Z}_m^*\), then
1. \(a^l\equiv 1 \pmod m \iff \mathrm{ord}_m(a)\mid l\).
  - In particular, \(\mathrm{ord}_m(a)\mid \varphi(m)\).
2. \(\mathrm{ord}_m(a)=k \implies\mathrm{ord}_m(a^l)=\frac{k}{\gcd(k,l)}\).
3. \(\gcd(\mathrm{ord}_m(a),\mathrm{ord}_m(b))=1 \implies \mathrm{ord}_m(ab)=\mathrm{ord}_m(a)\cdot \mathrm{ord}_m(b)\).
▶
Proof
1. Let \(k=\mathrm{ord}_m(a)\)
  
  \(\implies\): Write \(l=kq+r\) with \(0\leq r<k\), thus \(1\equiv a^l=a^{kq+r}=(a^k)^qa^r\equiv a^r \pmod m\), thus \(r=0\), so \(k\mid l\).
  
  \(\impliedby\): Let \(l=kq\), then \(a^l=(a^k)^q\equiv 1 \pmod m\).
2. Proof of 2
  
  Consider \((a^l)^\frac{k}{\gcd(k,l)}=(a^k)^\frac{l}{\gcd(k,l)}\equiv 1 \pmod m\), thus \(\mathrm{ord}_m(a^l)\mid \frac{k}{\gcd(k,l)}\).
  
  Let \(r=\mathrm{ord}_m(a^l)\), then \((a^{l})^r\equiv 1 \pmod m\), thus \(k\mid lr\). Since \(\frac{k}{\gcd(k,l)} \mid \frac{l}{\gcd(k,l)}r\) and \(\gcd(\frac{k}{\gcd(k,l)}, \frac{l}{\gcd(k,l)})=1\), we have \(\frac{k}{\gcd(k,l)}\mid r = \mathrm{ord}_m(a^l)\).
  
  So \(\mathrm{ord}_m(a^l)=\frac{k}{\gcd(k,l)}\).
3. Let \(u=\mathrm{ord}_m(a)\), \(v=\mathrm{ord}_m(b)\), \(w=\mathrm{ord}_m(ab)\)
  
  Since \((ab)^{uv}=(a^u)^v(b^v)^u\equiv 1 \pmod m\), thus \(w\mid uv\).
  
  Since \((ab)^w\equiv 1 \pmod m\), thus \(1\equiv ((ab)^{wu}=(a^u)^w(b^w)^u\equiv b^{wu} \pmod m\), thus \(v\mid wu\), so \(v\mid w\) since \(\gcd(u,v)=1\). Similarly, \(u\mid w\), so \(uv\mid w\).
  
  So \(\mathrm{ord}_m(ab) = w = uv = \mathrm{ord}_m(a)\cdot \mathrm{ord}_m(b)\).

Primitive root

Def 3.5 Primitive root: Let \(m\geq 2\), \(g\) is called a primitive root modulo \(m\) if \[\mathrm{ord}_m(g)=\varphi(m)\] I.e. \(g\) is a generator of the multiplicative cyclic group \(\mathbb{Z}_m^*\).
Thm 3.6: Let \(g\) be a primitive root modulo \(m\), then
1. \(\mathbb{Z}_m^*=\langle\bar{g}\rangle=\{\bar{1},\bar{g},\bar{g}^2,\cdots,\bar{g}^{\varphi(m)-1}\}\) is a cyclic group.
2. There are \(\varphi(\varphi(m))\) primitive roots modulo \(m\), and they are \(\{g^l: 1\leq l\leq \varphi(m), \gcd(\varphi(m),l)=1\}\).
▶
Proof
1. Obviously, \(\{\bar{1},\bar{g},\bar{g}^2,\cdots,\bar{g}^{\varphi(m)-1}\}\subseteq \mathbb{Z}_m^*\). we claim that \(\{\bar{1},\bar{g},\bar{g}^2,\cdots,\bar{g}^{\varphi(m)-1}\}\) has \(\varphi(m)\) distinct elements, thus \(\{\bar{1},\bar{g},\bar{g}^2,\cdots,\bar{g}^{\varphi(m)-1}\}=\mathbb{Z}_m^*\).
  
  If \(\bar{g}^i=\bar{g}^j\) with \(0\leq i<j\leq \varphi(m)-1\), then \(\bar{g}^{j-i}=\bar{1}\), thus \(\mathrm{ord}_m(g)\mid j-i\), so \(\varphi(m)\mid j-i\), which is impossible since \(0<j-i<\varphi(m)\).
2. \(g^l\) is a primitive root modulo \(m \iff \mathrm{ord}_m(g^l)=\frac{\varphi(m)}{\gcd(\varphi(m),l)}=\varphi(m) \iff \gcd(\varphi(m),l)=1\), thus all primitive roots modulo \(m\) are \(\{g^l: 1\leq l\leq \varphi(m), \gcd(\varphi(m),l)=1\}\), and the total number of them is \(\varphi(\varphi(m))\).
Thm 3.7: If \(p\in \mathbb{P}\), then there exists primitive root modulo \(p\).
- Recap: A field \(F\) is a commutative ring with identity in which every nonzero element is invertible.
  - Fact 1: \(\mathbb{Z}_p\) is a field.
  - Fact 2: A polynomial of degree \(n\) over a field \(F\) has at most \(n\) roots in \(F\).
- Goal: Find a \(g\in \mathbb{Z}_p^*\) s.t. \(\mathrm{ord}_p(g)=p-1\).
▶
Proof
- Let \(\varphi(p)=p-1\) has canonical factorization \[p-1=\prod_{i=1}^k p_i^{e_i}\] with \(e_i\geq 1\) and \(p_i\in \mathbb{P}\) are pairwise distinct. So the sub-goal is to find \(g_i\in \mathbb{Z}_p^*\) s.t. \(\mathrm{ord}_p(g_i)=p_i^{e_i}\) for \(1\leq i\leq k\), then \(g=\prod_{i=1}^k g_i\) is a primitive root modulo \(p\) since \(\gcd(p_i^{e_i},p_j^{e_j})=1\) for \(1\leq i<j\leq k\).
- Consider the equation \[x^{p-1} -1\equiv 0 \pmod p\] which has \(\varphi(p)=p-1\) roots and all roots are \(\mathbb{Z}_p^*\).
- Since \(x^{p-1}-1=(x^{p_i^{e_i}})^{\frac{p-1}{p_i^{e_i}}}-1=(x^{p_i^{e_i}}-1)\cdot(\cdots)\), thus \(x^{p_i^{e_i}}-1\) is a factor of \(x^{p-1}-1\), and there are \(p_i^{e_i}\) roots in \(\mathbb{Z}_p^*\).
- Consider \(x^{p_i^{e_i-1}}-1\) has at most \(p_i^{e_i-1}\) roots, thus \(\exists g_i\in \mathbb{Z}_p^*\) satisfying \(g_i\) is a root of \(x^{p_i^{e_i}}-1\) but not a root of \(x^{p_i^{e_i-1}}-1\), we claim that \(\mathrm{ord}_p(g_i)=p_i^{e_i}\).
  
  Since \(g_i\) is a root of \(x^{p_i^{e_i}}-1\), thus \(\mathrm{ord}_p(g_i)\mid p_i^{e_i}\).
  
  Since \(g_i\) is not a root of \(x^{p_i^{e_i-1}}-1\), suppose \(\mathrm{ord}_p(g_i)=p_i^r\) with \(r\leq e_i-1\), then \(g_i^{p_i^{e_i-1}}=(g_i^{p_i^r})^{p_i^{e_i-1-r}}\equiv 1 \pmod p\), thus \(g_i\) is a root of \(x^{p_i^{e_i-1}}-1\), which is a contradiction, so \(r=e_i\), i.e. \(\mathrm{ord}_p(g_i)=p_i^{e_i}\).
- Thus, \(\mathrm{ord}_p(g)=\mathrm{ord}_p(\prod_{i=1}^k g_i)=\prod_{i=1}^k \mathrm{ord}_p(g_i)=\prod_{i=1}^k p_i^{e_i}=p-1\), so \(g\) is a primitive root modulo \(p\).
▶
Proof method 2
\(\forall d\mid p-1\), let \(\pi(d) = \{\bar{a}\in \mathbb{Z}_p^*: \mathrm{ord}_p(a)=d\}\), we claim that \(\pi(p-1)\) is not empty by showing that \(\pi(d)\) has \(\varphi(d)\) elements.
- Due to the definition of \(\pi(d)\), we have \(\bigcup_{d\mid p-1} \pi(d)=\mathbb{Z}_p^*\), and \(\pi(d_1)\cap \pi(d_2)=\emptyset\) for \(d_1\neq d_2\) with \(d_1,d_2\mid p-1\). So \(\sum_{d\mid p-1} |\pi(d)| = |\mathbb{Z}_p^*| = p-1\)
- Claim that \(\sum_{d\mid p-1} \varphi(d) = p-1\):
  
  Consider the set \(S=\{\frac{1}{n}, \frac{2}{n}, \cdots, \frac{n}{n}\}\), obviously \(|S|=n\) and every element in \(S\) can be written as \(\frac{a}{d}\) with \(d\mid n\) and \(\gcd(a,d)=1\).
  
  Thus, we can partition \(S\) into \(\bigcup_{d\mid n} S_d\) where \(S_d=\{\frac{a}{d}: 1\leq a\leq d, \gcd(a,d)=1\}\), so \(|S_d|=\varphi(d)\), thus \(\sum_{d\mid n} \varphi(d) = |S|=n\).
- Claim that \(|\pi(d)| = \varphi(d)\) for all \(d\mid p-1\):
  
  If \(\pi(d) = \emptyset\), then \(|\pi(d)| = 0 \le \varphi(d)\), done.
  
  If \(\pi(d) \neq \emptyset\), then \(\exists a \in \pi(d)\) s.t. \(\mathrm{ord}_p(a) = d\). Consider the set \(S = \{1, a, a^2, \dots, a^{d-1}\}\):
  
  Since \(\mathrm{ord}_p(a) = d\), the elements in \(S\) are distinct modulo \(p\).
  
  Since \(a^d \equiv 1 \pmod p\), each element in \(S\) is a root of \(x^d - 1 \equiv 0 \pmod p\). And by Fact 2, \(x^d - 1\) has at most \(d\) roots in \(\mathbb{Z}_p\). Thus \(S\) is exactly the set of all roots of \(x^d - 1 \equiv 0 \pmod p\).
  
  Since \(\forall x \in \pi(d)\), \(x\) is a root of \(x^d - 1 \equiv 0 \pmod p\), so \(\pi(d)\subseteq S\).
  
  Due to Thm 3.4(2), \(\mathrm{ord}_p(a^k) = \frac{d}{\gcd(k, d)}\), thus \(a^k \in \pi(d) \implies \mathrm{ord}_p(a^k) = d \iff \gcd(k, d) = 1\).
  
  Thus, \(|\pi(d)| = \varphi(d)\).
  
  Since \(\sum_{d\mid p-1} |\pi(d)| = \sum_{d\mid p-1} \varphi(d) = p-1\) and \(\forall d\mid p-1, |\pi(d)| \le \varphi(d)\), we have \(|\pi(d)| = \varphi(d)\) for all \(d\mid p-1\).
- In particular, \(|\pi(p-1)| = \varphi(p-1) > 0\), so there exists a primitive root modulo \(p\).
Algorithm 3.8: Find all primitive roots modulo \(p\) for odd prime \(p\in \mathbb{P}\).
1. Factor \(\varphi(p)=p-1\) into its prime factorization \(\prod_{i=1}^k p_i^{e_i}\).
2. Find a primitive root:
  - For each \(1\leq i\leq k\), find \(g_i\in \mathbb{Z}_p^*\) s.t. \(\mathrm{ord}_p(g_i)=p_i^{e_i}\). Let \(g=\prod_{i=1}^k g_i\), then \(g\) is a primitive root modulo \(p\).
    - i.e. Find \(g_i\) s.t. \(g_i^{p_i^{e_i}}\equiv 1 \pmod p\) and \(\forall 0\leq r\leq p_i^{e_i-1}-1, g_i^r\not\equiv 1 \pmod p\).
  - Or search \(2\leq a\leq p-1\) until find \(a\) s.t. \(\forall 1\leq i\leq k, a^{\frac{p-1}{p_i}}\not\equiv 1 \pmod p\), then \(a\) is a primitive root modulo \(p\).
3. Find all primitive roots:
  - For each \(1\leq l\leq \varphi(p)\) with \(\gcd(\varphi(p),l)=1\), \(g^l\) is a primitive root modulo \(p\).
  - Thus, all \(\varphi(\varphi(p))\) primitive roots modulo \(p\) are \(G = \{g^l: 1\leq l\leq \varphi(p), \gcd(\varphi(p),l)=1\} = \{g^l \in \mathbb{Z}_p^* \mid l \in \mathbb{Z}_{p-1}^*\}\).
▶
Table of primitive roots

\(p\) Primitive roots modulo \(p\)

2 1

3 2

5 2, 3

7 3, 5

11 2, 6, 7, 8

13 2, 6, 7, 11

17 3, 5, 6, 7, 10, 11, 12, 14

19 2, 3, 10, 13, 14, 15, 16, 17
Thm 3.9: There exists primitive root modulo \(p^k\) for odd prime \(p\) and \(k\geq 1\), and there exists primitive root modulo \(2^k\) for \(k=1,2\).
▶
Proof
Let \(g\) be a primitive root modulo \(p\), then \(\mathrm{ord}_p(g)=\varphi(p)=p-1\).
- For \(k=1\), show in Thm 3.7, done.
- For \(k=2\):
  
  If \(\mathrm{ord}_{p^2}(g)=\varphi(p^2)=p(p-1)\), done.
  
  If \(\mathrm{ord}_{p^2}(g)<\varphi(p^2)\)
  
  Claim that \(\mathrm{ord}_{p}(g) \mid \mathrm{ord}_{p^2}(g) \mid \varphi(p^2)\), so \(p-1 \mid \mathrm{ord}_{p^2}(g) \mid p(p-1) \implies \mathrm{ord}_{p^2}(g)=p-1\):
  
  Due to Thm 3.4(1), \(\mathrm{ord}_{p^2}(g)\mid \varphi(p^2)\).
  
  Since \(g^{\mathrm{ord}_{p^2}(g)}\equiv 1 \pmod{p^2} \implies g^{\mathrm{ord}_{p^2}(g)}\equiv 1 \pmod p\), thus \(\mathrm{ord}_p(g)\mid \mathrm{ord}_{p^2}(g)\).
  
  Consider \(g+p\), we claim that \(\mathrm{ord}_{p^2}(g+p)=p(p-1)\):
  
  Since \(g+p\equiv g \pmod p\), thus \(\mathrm{ord}_p(g+p)=\mathrm{ord}_p(g)=p-1\), thus similarly we have \(p-1 \mid \mathrm{ord}_{p^2}(g+p) \mid p(p-1)\)
  
  Thus we claim that \(\mathrm{ord}_{p^2}(g+p)=p(p-1)\) by \(\mathrm{ord}_{p^2}(g+p) \neq p-1\): \[ \begin{aligned} (g+p)^{p-1} &= \sum_{i=0}^{p-1} \binom{p-1}{i} g^i p^{p-1-i} \\ &\equiv g^{p-1} + p(p-1)g^{p-2} \pmod{p^2} \\ &\equiv 1 - p g^{p-2} \pmod{p^2} \\ &\not\equiv 1 \pmod{p^2} \end{aligned} \]
  
  So \(\mathrm{ord}_{p^2}(g+p)=p(p-1)\), thus \(g+p\) is a primitive root modulo \(p^2\).
  
  Thus, \(g_1=\begin{cases} g & \mathrm{ord}_{p^2}(g)=p(p-1) \\ g+p & \mathrm{ord}_{p^2}(g)=p-1 \end{cases}\) is a primitive root modulo \(p^2\).
- For \(k\geq 3\), let \(g_1\) be a primitive root modulo \(p^2\), we claim that \(g_1\) is a primitive root modulo \(p^k\) for all \(k\geq 3\):
  
  Since \(p(p-1) = \mathrm{ord}_{p^2}(g_1) \mid \mathrm{ord}_{p^k}(g_1) \mid \varphi(p^k)=p^{k-1}(p-1)\), thus \(\mathrm{ord}_{p^k}(g_1)=p^t(p-1)\) for some \(1\leq t\leq k-1\).
  
  Suppose \(t \leq k-2\), then \(g_1^{p^{k-2}(p-1)}\equiv (g_1^{p^t(p-1)})^{p^{k-2-t}}\equiv 1 \pmod{p^k}\).
  
  Since \(g_1^{p-1} \equiv g^{p-1} \equiv 1 \pmod p\), thus \(\exists a \in \mathbb{Z}\) s.t. \(g_1^{p-1} = 1 + ap\) and \(\gcd(a,p)=1\)
  
  If \(\gcd(a,p)\neq 1\), then \(p\mid a\), thus \(g_1^{p-1} \equiv 1 \pmod{p^2}\), which is a contradiction since \(\mathrm{ord}_{p^2}(g_1)=p(p-1)\).
  
  Then we have: (Line 3 uses the fact that \(p\) is odd prime, so for \(i\geq 2\), \(\binom{p^{k-2}}{i} (ap)^i \equiv 0 \pmod {p^k}\)) \[ \begin{aligned} g_1^{p^{k-2}(p-1)} &= (1 + ap)^{p^{k-2}} = \sum_{i=0}^{p^{k-2}} \binom{p^{k-2}}{i} (ap)^i \\ &= 1 + p^{k-2} ap + \binom{p^{k-2}}{2} (ap)^2 + \cdots \\ &\equiv 1 + ap^{k-1} \pmod{p^k} \\ &\not\equiv 1 \pmod{p^k} \end{aligned} \]
  
  So causes a contradiction, thus \(t=k-1\), so \(\mathrm{ord}_{p^k}(g_1)=p^{k-1}(p-1)\), so \(g_1\) is a primitive root modulo \(p^k\) for all \(k\geq 3\).
Thm 3.10: There exists primitive root modulo \(2\cdot p^k\) for odd prime \(p\) and \(k\geq 1\).
▶
Proof
Let \(g\) be a primitive root modulo \(p^k\)
- Case 1: \(g\) is odd, claim that \(\mathrm{ord}_{2p^k}(g)=\varphi(2p^k)\):
  
  Since \(g^l\equiv 1 \pmod{2p^k} \implies g^l\equiv 1 \pmod{p^k}\), we have \(\mathrm{ord}_{p^k}(g) \mid \mathrm{ord}_{2p^k}(g)\).
  
  Since \(\gcd(g,p^k)=1\) and \(g\) is odd, we have \(\gcd(g,2p^k)=1\), thus \(\mathrm{ord}_{2p^k}(g)\mid \varphi(2p^k)\).
  
  Since \(\varphi(2p^k)=\varphi(2)\cdot \varphi(p^k)=\varphi(p^k) = \mathrm{ord}_{p^k}(g)\), thus \(\mathrm{ord}_{2p^k}(g)=\varphi(2p^k)\), so \(g\) is a primitive root modulo \(2p^k\).
- Case 2: \(g\) is even, then \(g+p^k\) is a primitive root modulo \(p^k\) and is odd. By case 1, \(\mathrm{ord}_{2p^k}(g+p^k)=\varphi(2p^k)\).
Thm 3.11: For \(m\geq 3\), there exists primitive root modulo \(m \iff m\) is of the form \(2,4,p^k,2p^k\) for odd prime \(p\) and \(k\geq 1\).
▶
Proof
- \(\implies\): Assume that \(m\) has the standard factorization \(m=\prod_{i=1}^r p_i^{e_i}\) with \(e_i\geq 1\), then \(\varphi(m) = \prod_{i=1}^r p_i^{e_i-1}(p_i-1)\). Let \(g\) be a primitive root modulo \(m\), then \(\mathrm{ord}_m(g)=\varphi(m)\)
  
  Let \(t = \mathrm{lcm}(\varphi(p_1^{e_1}), \varphi(p_2^{e_2}), \cdots, \varphi(p_r^{e_r}))\), thus \(t\leq \varphi(m)\) and \(\varphi(p_i^{e_i})\mid t\) for \(1\leq i\leq r\), so we have \[ \begin{aligned} &g^t = g^{k\cdot\varphi(p_i^{e_i})}\equiv 1 \pmod{p_i^{e_i}} \\ \implies &p_i^{e_i}\mid g^t-1 \\ \implies &m = \prod_{i=1}^r p_i^{e_i}\mid g^t-1 \\ \implies &g^t\equiv 1 \pmod m \\ \implies &\mathrm{ord}_m(g)\mid t \\ \implies &\varphi(m)\leq t \end{aligned} \]
  
  So \(\varphi(m)=t\), i.e. \(\mathrm{lcm}(\varphi(p_1^{e_1}), \varphi(p_2^{e_2}), \cdots, \varphi(p_r^{e_r})) = \prod_{i=1}^r \varphi(p_i^{e_i})\), so \(\gcd(\varphi(p_i^{e_i}), \varphi(p_j^{e_j}))=1\) for \(1\leq i<j\leq r\), i.e. \(\gcd(p_i^{e_i-1}(p_i-1), p_j^{e_j-1}(p_j-1))=1\). Thus \(m=2^a p^b\) for some \(a,b\geq 0\) and \(p\in \mathbb{P}\) is odd.
  
  Case 1: \(b\geq 1\), then \(\gcd(\varphi(2^a), \varphi(p^b))=\gcd(2^{a-1}, p^{b-1}(p-1))=1\), thus \(a\leq 1\) since \(2\mid p-1\), so \(m=p^b\) or \(2p^b\).
  
  Case 2: \(b=0\), \(m=2^a\), \(\mathrm{ord}_{m}(g)=\varphi(m)=2^{a-1}\), so \(g^{2^{a-2}} \not\equiv 1 \pmod{2^a}\). Since \(\gcd(g,2^a)=1\), thus \(g\) is odd. Let \(g=2k+1\) for some \(k\in \mathbb{Z}\), claim that \(a\leq 2\): Suppose \(a\geq 3\), then: \[ \begin{aligned} g^{2^{a-2}} &= (2k+1)^{2^{a-2}} = \sum_{i=0}^{2^{a-2}} \binom{2^{a-2}}{i} (2k)^i \\ &= 1 + 2^{a-1} k + \frac{2^{a-2} (2^{a-2}-1) (2k)^2}{2} + \frac{2^{a-2} (2^{a-2}-1) (2^{a-2}-2) (2k)^3}{6} + \cdots \\ &\equiv 1 + 2^{a-1} k + 2^{a-3} (2^{a-2}-1) (2k)^2 \pmod{2^a} \\ &= 1 + 2^{a-1}(k + k^2(2^{a-2}-1)) \pmod{2^a} \end{aligned} \] Since \(a\geq 3\), we have \((k+ k^2(2^{a-2}-1)) = k^2\cdot 2^{a-2} - k(k-1)\) is even, thus \(g^{2^{a-2}} \equiv 1 \pmod{2^a}\), which is a contradiction, so \(a\leq 2\).
- \(\impliedby\):
  
  \(m=2\): \(g=1\) is a primitive root modulo \(2\).
  
  \(m=4\): \(g=3\) is a primitive root modulo \(4\).
  
  \(m=p^k\) for odd prime \(p\) and \(k\geq 1\): Show in Thm 3.9
  
  \(m=2p^k\) for odd prime \(p\) and \(k\geq 1\): Show in Thm 3.10
Algorithm 3.12: Find all primitive roots modulo \(n\).
1. If \(n\) is not of the form \(2,4,p^k,2p^k\) for odd prime \(p\) and \(k\geq 1\), then there is no primitive root modulo \(n\), done.
  - If \(n=2\), \(g=1\)
  - If \(n=4\), \(g=3\)
2. Let \(g\) be a primitive root modulo \(p\) and \(G = \{g^l \in \mathbb{Z}_p^* \mid l \in \mathbb{Z}_{p-1}^*\}\) be the set of all primitive roots modulo \(p\).
  1. \(G_1 = \{g+ap \mid g \in G, a \in \mathbb{Z}_p, ap \not\equiv g^p-g \pmod{p^2}\}\) is the set of all primitive roots modulo \(p^2\).
  2. \(G_2 = \{g+ap^2 \mid g \in G_1, a \in \mathbb{Z}_{p^{k-2}}\}\) is the set of all primitive roots modulo \(p^k\) for \(k\geq 3\).
  3. \(G_3 = \{g \mid g \in G_2, 2\nmid g\} \cup \{g+p^k \mid g \in G_2, 2\mid g\}\) is the set of all primitive roots modulo \(2p^k\).
▶
Proof of 2
1. \(G_1\) is the set of all primitive roots modulo \(p^2\):
  
  If \(g_1\) is a primitive root modulo \(p^2\), then \(g_1\) is a primitive root modulo \(p\), so \(g_1 = g + ap\) for some \(g \in G\) and \(a \in \mathbb{Z}_p\).
  
  If \(g_1\) is not a primitive root modulo \(p\), then \(g_1^d\equiv 1 \pmod p\) for some \(d\mid p-1\) with \(d<p-1\), thus \((g_1^d)^p = (1+kp)^p \equiv 1 \pmod{p^2}\) with \(dp < p(p-1)\), so \(g_1\) is not a primitive root modulo \(p^2\), which is a contradiction.
  
  Suppose \(g_1=g+ap\) is a primitive root modulo \(p^2\), then we have \[ \begin{aligned} g_1^{p-1} &= (g+ap)^{p-1} = \sum_{i=0}^{p-1} \binom{p-1}{i} g^i (ap)^{p-1-i} \\ &\equiv g^{p-1} + ap(p-1)g^{p-2} \pmod{p^2} \\ &\equiv g^{p-1} - ap g^{p-2} \pmod{p^2} \\ &\not\equiv 1 \pmod{p^2} \\ \end{aligned} \] Thus \[ apg^{p-1} \not\equiv g^p-g \pmod{p^2} \] Since \(g\) is a primitive root modulo \(p\), thus \(g^{p-1}\equiv 1 \pmod p\), so \(apg^{p-1} \equiv ap(1+kp) \equiv ap \pmod{p^2}\), thus \[ ap \not\equiv g^p-g \pmod{p^2} \iff a \not\equiv \frac{g^p-g}{p} \pmod p \] I.e. there is a unique \(a\) not satisfying the condition, so there are \(p-1\) choices for \(a\) for each \(g\in G\).
  
  So \(G_1\) has totally \((p-1)\varphi(\varphi(p))\) distinct elements, and they are all primitive roots modulo \(p^2\). \[ \begin{aligned} &g+ap\equiv g'+a'p \pmod{p^2}\\ \implies &g+ap\equiv g'+a'p \pmod p \\ \implies &g\equiv g' \pmod p \\ \implies &g=g' \\ \implies &ap\equiv a'p \pmod{p^2} \\ \implies &a\equiv a' \pmod p \\ \implies &a=a' \end{aligned} \]
  
  Since \(\varphi(\varphi(p^2))=(p-1)\varphi(\varphi(p))=(p-1)|G|=|G_1|\), \(G_1\) is the set of all primitive roots modulo \(p^2\).
2. \(G_2\) is the set of all primitive roots modulo \(p^k\) for \(k\geq 3\):
  
  If \(g_2\) is a primitive root modulo \(p^k\), then \(g_2\) is a primitive root modulo \(p^2\), so \(g_2 = g + ap^2\) for some \(g \in G_1\) and \(a \in \mathbb{Z}_{p^{k-2}}\).
  
  Suppose \(g_2=g+ap^2\) is a primitive root modulo \(p^k\), then we have \[ \begin{aligned} g_2^{p^{k-2}(p-1)} &= (g+ap^2)^{p^{k-2}(p-1)} \\ &= \sum_{i=0}^{p^{k-2}(p-1)} \binom{p^{k-2}(p-1)}{i} g^i (ap^2)^{p^{k-2}(p-1)-i} \\ &\equiv g^{p^{k-2}(p-1)} \pmod{p^k} \\ &\not\equiv 1 \pmod{p^k} \end{aligned} \] Since \(g\) is a primitive root modulo \(p^2\), we have \(g^{p-1} \not\equiv 1 \pmod{p^2}\), so \(g^{p^{k-2}(p-1)} \not\equiv 1 \pmod{p^k}\) for all \(k\geq 3\), thus the formula above always holds.
  
  So \(G_2\) has totally \(|\mathbb{Z}_{p^{k-2}}||G_1|\) distinct elements. Since \(\varphi(\varphi(p^k))=p^{k-2}\varphi(\varphi(p^2))=|G_2|\), \(G_2\) is the set of all primitive roots modulo \(p^k\) for all \(k\geq 3\).
3. \(G_3\) is the set of all primitive roots modulo \(2p^k\):
  
  Due to the proof of Thm 3.9, the primitive roots modulo \(2p^k\) are of the form \(g\) or \(g+p^k\) for some \(g \in G_2\).
  
  Since \(\varphi(\varphi(2p^k))=\varphi(\varphi(p^k))=|G_2|=|G_3|\), \(G_3\) is the set of all primitive roots modulo \(2p^k\).
Cor 3.13: For odd prime \(p\) and \(\forall k \geq 2\)
1. \(\mathrm{ord}_{p^k}(g)=\varphi(p^k) \implies \mathrm{ord}_{p^{k+1}}(g)=\varphi(p^{k+1})\).
2. \(\mathrm{ord}_{p^{k}}(g)=\varphi(p^{k}) \implies \mathrm{ord}_{p^{k-1}}(g)=\varphi(p^{k-1})\).
▶
Proof
1. Since \(\mathrm{ord}_{p^k}(g)=\varphi(p^k)\), thus \(g^{\varphi(p^{k-1})}\not\equiv 1 \pmod{p^k}\) and \(g^{\varphi(p^{k-1})}\equiv 1 \pmod{p^{k-1}}\), thus \(g^{\varphi(p^{k-1})}=1+ap^{k-1}\) with \(\gcd(a,p)=1\). Since \(p^{k-1}(p-1) = \mathrm{ord}_{p^k}(g) \mid \mathrm{ord}_{p^{k+1}}(g) \mid \varphi(p^{k+1})=p^{k}(p-1)\), we have \(\mathrm{ord}_{p^{k+1}}(g)=p^{k-1}(p-1)\) or \(p^{k}(p-1)\). Since \[ \begin{aligned} g^{p^{k-1}(p-1)} &= g^{\varphi(p^{k-1})p} \\ &= (1+ap^{k-1})^{p} \\ &\equiv 1 + ap^{k} \pmod{p^{k+1}} \\ &\not\equiv 1 \pmod{p^{k+1}} \end{aligned} \] So \(\mathrm{ord}_{p^{k+1}}(g)\neq \varphi(p^{k})=p^{k-1}(p-1)\), thus \(\mathrm{ord}_{p^{k+1}}(g)=\varphi(p^{k+1})\).
2. Suppose \(\mathrm{ord}_{p^{k-1}}(g)=d\), then \(d\mid \varphi(p^{k-1})\) and \(g^d\equiv 1 \pmod{p^{k-1}}\), thus \(g^d=1+ap^{k-1}\) for some \(a\in \mathbb{Z}\), then we have \[ (g^d)^p = (1+ap^{k-1})^p \equiv 1 \pmod{p^{k}} \] So \(\mathrm{ord}_{p^{k}}(g) \mid pd\), thus \(\varphi(p^{k})\mid pd\), thus \(\varphi(p^{k-1})\mid d\), so \(\mathrm{ord}_{p^{k-1}}(g)=d=\varphi(p^{k-1})\).

\(p\)	Primitive roots modulo \(p\)
2	1
3	2
5	2, 3
7	3, 5
11	2, 6, 7, 8
13	2, 6, 7, 11
17	3, 5, 6, 7, 10, 11, 12, 14
19	2, 3, 10, 13, 14, 15, 16, 17

Discrete Logarithm

Def 3.14 Discrete Logarithm: Let \(g\) be a primitive root modulo \(m\), then discrete logarithm of \(a\) modulo \(m\) with \(\gcd(a,m)=1\) is defined to be an integer \(x\) satisfying \[ g^x \equiv a \pmod m \]

Denoted by \(x = \log_g a \pmod{\varphi(m)}\).
Thm 3.15 Properties of Discrete Logarithms: Let \(g\) be a primitive root modulo \(m\), then for \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), we have
1. \(\log_g 1 \equiv 0 \pmod{\varphi(m)}\).
2. \(\log_g g \equiv 1 \pmod{\varphi(m)}\).
3. \(\log_g (ab) \equiv \log_g a + \log_g b \pmod{\varphi(m)}\).
4. \(\log_g a^n \equiv n \cdot \log_g a \pmod{\varphi(m)}\).
Thm 3.16: Let \(g\) be a primitive root modulo \(m\), then \(\log_g a \equiv \log_g b \pmod{\varphi(m)} \iff a \equiv b \pmod m\).
▶
Proof
- \(\implies\): Since \(g^{\log_g a} \equiv a \pmod m\) and \(g^{\log_g b} \equiv b \pmod m\), thus \(a \equiv g^{\log_g a} \equiv g^{\log_g b} \equiv b \pmod m\).
- \(\impliedby\): Since \(a \equiv b \pmod m\), thus \(g^{\log_g a} \equiv g^{\log_g b} \pmod m\), thus \(\mathrm{ord}_m(g)\mid (\log_g a - \log_g b)\), so \(\log_g a \equiv \log_g b \pmod{\varphi(m)}\).
Thm 3.17: Let \(g\) be a primitive root modulo \(m\), then the equation \(x^b \equiv a \pmod m\) has a solution \(\iff \gcd(b, \varphi(m)) \mid \log_g a\).
▶
Proof
- \(\impliedby\): Since \(\gcd(b, \varphi(m)) \mid \log_g a\), thus \(\exists u,v\in \mathbb{Z}\) s.t. \(ub + v\varphi(m) = \log_g a\), thus \(g^{ub} \equiv g^{ub + v\varphi(m)} \equiv g^{\log_g a} \equiv a \pmod m\), so \(x=g^u\) is a solution to the equation.
- \(\implies\): Since \(g\) is a primitive root modulo \(m\), thus \(x=g^k\) and \(a=g^l\) for some \(1\leq k,l \leq \varphi(m)\), thus the equation is equivalent to \(g^{kb} \equiv g^l \pmod m\), thus \(kb \equiv l \pmod{\varphi(m)}\), let \(d=\gcd(b, \varphi(m))\), then \(k \equiv \frac{l}{d} \cdot \left(\frac{b}{d}\right)^{-1} \pmod{\frac{\varphi(m)}{d}}\), this requires \(\frac{l}{d} \in \mathbb{Z}\), so \(d \mid l\), i.e. \(\gcd(b, \varphi(m)) \mid \log_g a\).
- Thus, the solution to the equation is \(x = g^{\frac{l}{d} \cdot \left(\frac{b}{d}\right)^{-1} + t\cdot \frac{\varphi(m)}{d}}\) for \(t=0,1,\cdots,d-1\).

Chapter 4. Quadratic Residues

Quadratic Residues

Def 4.1 Quadratic Residue: Let \(p\) be an odd prime, then \(a\in\mathbb{Z}\) with \(\gcd(a,p)=1\) is called a quadratic residue (QR) modulo \(p\) if the congruence \[ x^2 \equiv a \pmod p \]

has a solution. Otherwise \(a\) is called a quadratic non-residue (QNR) modulo \(p\).
Thm 4.2 Property of QR:
1. Let \(g\) be a primitive root modulo \(p\), then \(a\) is a QR modulo \(p \iff a=g^{2k} \pmod p\) for some integer \(k\).
  ▶
  Proof of 1
  \(\implies\): Assume \(a=QR\), then \(\exists b\in\mathbb{Z}\) s.t. \(b^2 \equiv a \pmod p\). Let \(b \equiv g^k \pmod p\) for some integer \(k\), then \(a \equiv b^2 \equiv g^{2k} \pmod p\).
  
  \(\impliedby\): Assume \(a \equiv g^{2k} \pmod p\) for some integer \(k\), then \(g^k\) is a solution to \(x^2 \equiv a \pmod p\), so \(a\) is a QR.
2. \(a = QR, b = QR \implies ab = QR\).
3. \(a = QNR, b = QNR \implies ab = QR\).
4. \(a = QR, b = QNR \implies ab = QNR\).
5. The number of \(QR\) / \(QNR\) modulo \(p\) is \(\frac{p-1}{2}\).
  ▶
  Proof of 5
  Since there are \(p-1\) non-zero elements in \(\mathbb{Z}_p^*\), consider \(x\in\mathbb{Z}_p^*\), then \((p-x)^2 \equiv p^2 - 2px + x^2 \equiv x^2 \pmod p\).
  
  Consider \(x^2\) for \(x\in\{1, 2, \cdots, \frac{p-1}{2}\}\), claim that \(\forall 1\leq x < y \leq \frac{p-1}{2}, x^2 \not\equiv y^2 \pmod p\).
  
  If \(x^2 \equiv y^2 \pmod p\), then \(y^2 - x^2 \equiv (y-x)(y+x) \equiv 0 \pmod p\), thus \(p \mid y-x\) or \(p \mid y+x\).
  
  Since \(1\leq x < y \leq \frac{p-1}{2}\), \(y+x < \frac{p-1}{2} + \frac{p-1}{2} = p-1 < p\) and \(y-x < p\), thus \(p \nmid x+y\) and \(p \nmid x-y\), contradiction.
  
  Thus \(x^2\) for \(x\in\{1, 2, \cdots, \frac{p-1}{2}\}\) are \(\frac{p-1}{2}\) distinct \(QR\) modulo \(p\), and the remaining \(\frac{p-1}{2}\) non-zero elements are \(QNR\) modulo \(p\).

Legendre Symbol

Def 4.3 Legendre Symbol: Let \(p\) be an odd prime, then for any \(a\in\mathbb{Z}\), the Legendre symbol \(\left(\frac{a}{p}\right)\) is defined as \[ \left(\frac{a}{p}\right) = \begin{cases} 0 ,& p \mid a \\ 1 ,& a \text{ is a QR modulo } p \\ -1 ,& a \text{ is a QNR modulo } p \end{cases} \]
Thm 4.4: The number of solutions to \(x^2 \equiv a \pmod p\) is \(1 + \left(\frac{a}{p}\right)\).
▶
Proof
1. Case 1: \(p \mid a\), then \(x^2 \equiv a \equiv 0 \pmod p\) has exactly one solution \(x \equiv 0 \pmod p\). Thus \(1 = 1 + \left(\frac{a}{p}\right)\), done.
2. Case 2: \(a\) is a QR modulo \(p\), then \(a \equiv g^{2k} \pmod p\) for some \(k\in\mathbb{Z}\). Then \(x^2 \equiv g^{2k} \pmod p\), so \(x \equiv \pm g^k \pmod p\) are two distinct solutions to \(x^2 \equiv a \pmod p\). Thus \(2 = 1 + \left(\frac{a}{p}\right)\), done.
3. Case 3: \(a\) is a QNR modulo \(p\), then there are no solutions to \(x^2 \equiv a \pmod p\). Thus \(0 = 1 + \left(\frac{a}{p}\right)\), done.
Thm 4.5 Euler’s Criterion: Let \(p\) be an odd prime, then \[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \]
▶
Proof
1. Case 1: \(p \mid a\), then \(a=kp\) for some \(k\in\mathbb{Z}\). Then \(\left(\frac{a}{p}\right) \equiv 0 \equiv (kp)^{\frac{p-1}{2}} \pmod p\), done.
2. Case 2: \(a\) is a QR modulo \(p\), then \(a \equiv g^{2k} \pmod p\) for some \(k\in\mathbb{Z}\). Then \(\left(\frac{a}{p}\right) \equiv 1 \equiv (g^{2k})^{\frac{p-1}{2}} \equiv g^{(p-1)k} \pmod p\), done.
3. Case 3: \(a\) is a QNR modulo \(p\), then \((a^{\frac{p-1}{2}})^2 \equiv a^{p-1} \equiv 1 \pmod p\), i.e. \(a^{\frac{p-1}{2}}\) is a solution to \(x^2 \equiv 1 \pmod p\), thus \(a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p\). Let \(a\equiv g^k \pmod p\) with odd \(k\), then \[ \mathrm{ord}_p(a) = \mathrm{ord}_p(g^k) = \frac{\mathrm{ord}_p(g)}{\gcd(\mathrm{ord}_p(g), k)} = \frac{p-1}{\gcd(p-1, k)} \] Suppose \(a^{\frac{p-1}{2}} \equiv 1 \pmod p\), then \(\frac{p-1}{\gcd(p-1, k)} \mid \frac{p-1}{2}\), i.e. \(\exists t\in\mathbb{Z}\) s.t. \(\frac{p-1}{\gcd(p-1, k)} \cdot t = \frac{p-1}{2}\), thus \(\gcd(p-1, k) = 2t\), which contradicts the fact that \(k\) is odd. Thus \(a^{\frac{p-1}{2}} \equiv -1 \pmod p\), done.
Thm 4.6 Properties of Legendre Symbol: Let \(p\) be an odd prime, then for any \(a, m, n\in\mathbb{Z}\), we have
1. \(\left(\frac{mn}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)\)
2. \(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 ,& p \equiv 1 \pmod 4 \\ -1 ,& p \equiv 3 \pmod 4 \end{cases}\)
3. \(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 ,& p \equiv 1, 7 \pmod 8 \\ -1 ,& p \equiv 3, 5 \pmod 8 \end{cases}\)
4. \(\sum_{a\in\mathbb{Z}_p} \left(\frac{a}{p}\right) = 0\).
▶
Proof
1. By Euler’s Criterion, \(\left(\frac{mn}{p}\right) \equiv (mn)^{\frac{p-1}{2}} \equiv m^{\frac{p-1}{2}} n^{\frac{p-1}{2}} \equiv \left(\frac{m}{p}\right)\left(\frac{n}{p}\right) \pmod p\). Since \(\left(\frac{mn}{p}\right), \left(\frac{m}{p}\right), \left(\frac{n}{p}\right) \in \{-1, 0, 1\}\), we have \(\left(\frac{mn}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)\), done.
2. By Euler’s Criterion, \(\left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}} \pmod p\). Since \(\left(\frac{-1}{p}\right), (-1)^{\frac{p-1}{2}} \in \{-1, 1\}\), we have \(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\). If \(p \equiv 1 \pmod 4\), then \(\frac{p-1}{2}\) is even, thus \(\left(\frac{-1}{p}\right) = 1\). If \(p \equiv 3 \pmod 4\), then \(\frac{p-1}{2}\) is odd, thus \(\left(\frac{-1}{p}\right) = -1\), done.
3. Consider \(S = 2\cdot 4\cdot 6\cdots (p-1) = 2^{\frac{p-1}{2}} \cdot 1\cdot 2\cdot 3\cdots \frac{p-1}{2} \equiv 2^{\frac{p-1}{2}} \cdot \left(\frac{p-1}{2}\right)! \pmod p\).
  
  Case 1: \(p \equiv 1 \pmod 4\): \[ \begin{aligned} S &\equiv 2\cdot 4\cdot 6\cdots (p-1) \\ &= 2\cdot 4\cdots \frac{p-1}{2} \cdot \frac{p+3}{2} \cdot \frac{p+7}{2} \cdots (p-1) \\ &\equiv 2\cdot 4\cdots \frac{p-1}{2} \cdot (\frac{p+3}{2}-p) \cdot (\frac{p+7}{2}-p) \cdots (p-1-p) \pmod p \\ &\equiv 2\cdot 4\cdots \frac{p-1}{2} \cdot (-\frac{p-3}{2}) \cdot (-\frac{p-7}{2}) \cdots (-1) \pmod p \\ &\equiv (-1)^{\frac{p-1}{4}} \cdot (\frac{p-1}{2})! \pmod p \\ \end{aligned} \] Thus \(2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{4}} \pmod p\), i.e. \(\left(\frac{2}{p}\right) = (-1)^{\frac{p-1}{4}}\). If \(p \equiv 1 \pmod 8\), then \(\frac{p-1}{4}\) is even, thus \(\left(\frac{2}{p}\right) = 1\). If \(p \equiv 5 \pmod 8\), then \(\frac{p-1}{4}\) is odd, thus \(\left(\frac{2}{p}\right) = -1\), done.
  
  Case 2: \(p \equiv 3 \pmod 4\): \[ \begin{aligned} S &\equiv 2\cdot 4\cdot 6\cdots (p-1) \\ &= 2\cdot 4\cdots \frac{p-3}{2} \cdot \frac{p+1}{2} \cdot \frac{p+5}{2} \cdots (p-1) \\ &\equiv 2\cdot 4\cdots \frac{p-3}{2} \cdot (\frac{p+1}{2}-p) \cdot (\frac{p+5}{2}-p) \cdots (p-1-p) \pmod p \\ &\equiv 2\cdot 4\cdots \frac{p-3}{2} \cdot (-\frac{p-1}{2}) \cdot (-\frac{p-5}{2}) \cdots (-1) \pmod p \\ &\equiv (-1)^{\frac{p+1}{4}} \cdot (\frac{p-1}{2})! \pmod p \\ \end{aligned} \] Thus \(2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p+1}{4}} \pmod p\), i.e. \(\left(\frac{2}{p}\right) = (-1)^{\frac{p+1}{4}}\). If \(p \equiv 3 \pmod 8\), then \(\frac{p+1}{4}\) is odd, thus \(\left(\frac{2}{p}\right) = -1\). If \(p \equiv 7 \pmod 8\), then \(\frac{p+1}{4}\) is even, thus \(\left(\frac{2}{p}\right) = 1\), done.
  
  Thus, combine the two cases, we have \(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\), done.
4. Since \(\left(\frac{0}{p}\right) = 0\), \(\left(\frac{a}{p}\right) = 1\) for \(\frac{p-1}{2}\) \(QR\) and \(\left(\frac{a}{p}\right) = -1\) for \(\frac{p-1}{2}\) \(QNR\), we have \(\sum_{a\in\mathbb{Z}_p} \left(\frac{a}{p}\right) = 0 + \frac{p-1}{2} \cdot 1 + \frac{p-1}{2} \cdot (-1) = 0\), done.

Jacobi Symbol

Def 4.7 Jacobi Symbol: Let \(m\geq 3\) be an odd integer, assume that \(m\) has the standard factorization \(m = \prod_{i=1}^r p_i^{e_i}\) with \(p_i\) are distinct odd primes and \(e_i \geq 1\), then for any \(a\in\mathbb{Z}\), the Jacobi symbol \(\left(\frac{a}{m}\right)\) is defined as \[ \left(\frac{a}{m}\right) = \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i} \]
Thm 4.8 Properties of Jacobi Symbol: Let \(m,n\geq 3\) be odd integers, then for any \(a, b\in\mathbb{Z}\), we have
1. \(\left(\frac{a}{m}\right) = 0 \iff \gcd(a, m) > 1\).
2. \(\left(\frac{ab}{m}\right) = \left(\frac{a}{m}\right)\left(\frac{b}{m}\right)\).
3. \(\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)\).
4. \(\left(\frac{n^2}{m}\right) = \left(\frac{n}{m^2}\right) = 1 \iff \gcd(n, m) = 1\).
5. \(\left(\frac{-1}{m}\right) = (-1)^{\frac{m-1}{2}}\).
6. \(\left(\frac{2}{m}\right) = (-1)^{\frac{m^2-1}{8}}\).
▶
Proof
1. Let \(m = \prod_{i=1}^r p_i^{e_i}\) be the standard factorization of \(m\), then
  
  \(\implies\): Assume \(\left(\frac{a}{m}\right) = 0\), then \(\exists i\in\{1, 2, \cdots, r\}\) s.t. \(\left(\frac{a}{p_i}\right) = 0\), thus \(p_i \mid a\), so \(p_i \mid \gcd(a, m)\), thus \(\gcd(a, m) > 1\), done.
  
  \(\impliedby\): Assume \(\gcd(a, m) > 1\), then \(\exists i\in\{1, 2, \cdots, r\}\) s.t. \(p_i \mid a\), thus \(\left(\frac{a}{p_i}\right) = 0\), so \(\left(\frac{a}{m}\right) = 0\), done.
2. We have \[ \begin{aligned} \left(\frac{ab}{m}\right) &= \prod_{i=1}^r \left(\frac{ab}{p_i}\right)^{e_i} \\ &= \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i} \cdot \prod_{i=1}^r \left(\frac{b}{p_i}\right)^{e_i} \\ &= \left(\frac{a}{m}\right)\left(\frac{b}{m}\right) \end{aligned} \]
3. Let \(m=\prod_{i=1}^r p_i^{e_i}\) and \(n=\prod_{i=1}^r p_i^{f_i}\) with \(e_i, f_i \geq 0\), then \[ \begin{aligned} \left(\frac{a}{mn}\right) &= \left(\frac{a}{\prod_{i=1}^r p_i^{e_i+f_i}}\right) = \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i+f_i} \\ &= \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i} \cdot \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{f_i} \\ &= \left(\frac{a}{m}\right)\left(\frac{a}{n}\right) \end{aligned} \]
4. Follows from (1), (2) and (3).
5. Proof of 5:
  
  Method 1: Let \(m = \prod_{i=1}^r p_i^{e_i}\) be the standard factorization of \(m\), then \[ \begin{aligned} \left(\frac{-1}{m}\right) &= \prod_{i=1}^r \left(\frac{-1}{p_i}\right)^{e_i} \\ &= \prod_{i=1}^r (-1)^{\frac{p_i-1}{2} e_i} \\ &= (-1)^{\sum_{i=1}^r \frac{p_i-1}{2} e_i} \overset{?}{=} (-1)^{\frac{m-1}{2}} \end{aligned} \] Claim that \(\sum_{i=1}^r \frac{p_i-1}{2} e_i \equiv \frac{m-1}{2} \pmod 2\).
  
  Method 2: We can prove by induction on \(m\):
  
  If \(m=3\), done.
  
  Assume the claim holds for all odd integers \(\leq m\), then consider \(m+2 = pk\) for some odd prime \(p\) and odd integer \(k\geq 1\). Then \[ \begin{aligned} \left(\frac{-1}{m+2}\right) &= \left(\frac{-1}{pk}\right) = \left(\frac{-1}{p}\right)\left(\frac{-1}{k}\right) \\ &= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{k-1}{2}} \\ &= (-1)^{\frac{p-1}{2} + \frac{k-1}{2}} \end{aligned} \] It is sufficient to prove \(\frac{p-1}{2} + \frac{k-1}{2} \equiv \frac{pk-1}{2} \pmod 2\). Let \(p = 2u + 1\) and \(k = 2v + 1\), then \[ \begin{aligned} &\frac{p-1}{2} + \frac{k-1}{2} - \frac{pk-1}{2} \\ =& \frac{p+k-pk-1}{2} \\ =& \frac{-(p-1)(k-1)}{2} \\ =& -2uv \equiv 0 \pmod 2 \end{aligned} \] Thus \(\frac{p-1}{2} + \frac{k-1}{2} \equiv \frac{pk-1}{2} \pmod 2\), done.
6. Similar to (5), we can prove by induction on \(m\):
  
  If \(m=3\), done.
  
  Assume the claim holds for all odd integers \(\leq m\), then consider \(m+2 = pk\) for some odd prime \(p\) and odd integer \(k\geq 1\). Then \[ \begin{aligned} \left(\frac{2}{m+2}\right) &= \left(\frac{2}{pk}\right) = \left(\frac{2}{p}\right)\left(\frac{2}{k}\right) \\ &= (-1)^{\frac{p^2-1}{8}} \cdot (-1)^{\frac{k^2-1}{8}} \\ &= (-1)^{\frac{p^2-1}{8} + \frac{k^2-1}{8}} \end{aligned} \] It is sufficient to prove \(\frac{p^2-1}{8} + \frac{k^2-1}{8} \equiv \frac{(pk)^2-1}{8} \pmod 2\). Let \(p = 2u + 1\) and \(k = 2v + 1\), then \[ \begin{aligned} &\frac{p^2-1}{8} + \frac{k^2-1}{8} - \frac{(pk)^2-1}{8} \\ =& \frac{p^2+k^2-(pk)^2-1}{8} \\ =& \frac{-(p^2-1)(k^2-1)}{8} \\ =& \frac{-(4u(u+1))(4v(v+1))}{8} \\ =& -2u(u+1)v(v+1) \equiv 0 \pmod 2 \end{aligned} \] Thus \(\frac{p^2-1}{8} + \frac{k^2-1}{8} \equiv \frac{(pk)^2-1}{8} \pmod 2\), done.

Quadratic Reciprocity

Thm 4.6 Law of Quadratic Reciprocity: Let \(m,n\) be odd integers with \(\gcd(m, n) = 1\), then \[ \left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}} \]

Equivalently, \(\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right) \cdot (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}\)
▶
Example
1. Since \[ \begin{aligned} \left(\frac{3}{17}\right) &= \left(\frac{17}{3}\right) \cdot (-1)^{\frac{3-1}{2} \cdot \frac{17-1}{2}} \\ &= \left(\frac{2}{3}\right) \cdot 1 \\ &= -1 \end{aligned} \] Thus \(3\) is a NQR modulo \(17\).
2. Since \[ \begin{aligned} \left(\frac{6}{17}\right) &= \left(\frac{2}{17}\right) \cdot \left(\frac{3}{17}\right) \\ &= (-1)^{\frac{17^2-1}{8}} \cdot (-1) \\ &= -1 \end{aligned} \] Thus \(6\) is a NQR modulo \(17\).

Chapter 5. Polynomials

▶

Recap of Ring and Field

A ring is a set \(R\) equipped with \(+\) and \(\cdot\) operations such that \((R, +)\) is an abelian group, \((R, \cdot)\) is a semigroup, and \(\cdot\) distributes over \(+\).
A field is a commutative ring with identity in which every non-zero element is a unit, i.e. every non-zero element has a multiplicative inverse. In particular, a field is an integral domain.
- \(\mathbb{Q}\): the field of rational numbers.
- \(\mathbb{R}\): the field of real numbers.
- \(\mathbb{C}\): the field of complex numbers.
- \(\mathbb{Z}_p\): the field of integers modulo a prime \(p\).

Polynomials

Def 5.1 Polynomial: A polynomial over a field \(F\) has the form \[ f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0,\quad a_i \in F \]
- If \(a_n \neq 0\), then \(n\) is called the degree of \(f(x)\) and is denoted \(\deg(f)\), and \(a_n\) is called the leading coefficient of \(f(x)\). If \(a_n=1\), then \(f\) is called monic. (首一的)
- An element \(a \in F\) is called a constant polynomial. The degree of the zero polynomial is defined to be \(-\infty\), others degree is defined to be \(0\), i.e. \[ \deg(a) = \begin{cases} 0 & a \neq 0 \\ -\infty & a = 0 \end{cases} \]
Def 5.2 Addition and Multiplication: Let \(f(x)=a_0 + a_1 x + \cdots + a_n x^n\) and \(g(x)=b_0 + b_1 x + \cdots + b_m x^m\) be two polynomials.
- The sum of \(f(x)\) and \(g(x)\) is defined as \[ (f + g)(x) = f(x) + g(x) = \sum_{i=0}^{\max(n, m)} (a_i + b_i) x^i \]
- The product of \(f(x)\) and \(g(x)\) is defined as \[ (f \cdot g)(x) = f(x) \cdot g(x) = c_0 + c_1 x + \cdots + c_{n+m} x^{n+m} \]
Thm 5.3 Properties of Degree: Let \(f(x), g(x)\) be two polynomials. Then
1. \(\deg(f + g) \leq \max(\deg(f), \deg(g))\).
2. \(\deg(f \cdot g) = \deg(f) + \deg(g)\).
3. \(\deg(a \cdot f) = \deg(f)\) if \(a \in F \setminus \{0\}\).
Def 5.4 Polynomial Ring: The polynomial ring over field \(F\) is defined as \[ F[x] = \left\{\sum_{i=0}^n a_i x^i : n \geq 0, a_i \in F\right\} \]

Indeed \((F[x], +, \cdot)\) forms a commutative ring with additive identity \(0\) and multiplicative identity \(1\). Furthermore, \(F[x]\) is an integral domain.
Thm 5.5: The unit group of \(F[x]\) is \(F^* = F \setminus \{0\}\).
- Notation: The unit group of a ring \(R\) is the set of all invertible elements in \(R\), denoted by \(R^*\).
▶
Proof
- Let \(f\in F[x]\) be a unit. Then \(\exists g \in F[x]\) s.t. \(f \cdot g = 1\). By Thm 5.3, \(\deg(f) + \deg(g) = \deg(f\cdot g) = \deg(1) = 0\). Thus \(\deg(f) = \deg(g) = 0\), which means \(f, g \in F^*\).
- Conversely, if \(f \in F^*\), then \(f^{-1} \in F^*\) and \(f \cdot f^{-1} = 1\).

Divisibility

Def 5.6 Divisibility: A polynomial \(f\) is divisible by a polynomial \(g\) if \[ \exists h \in F[x] \text{ s.t. } f = g \cdot h \]

Then we say \(g\) divides \(f\), denoted \(g \mid f\).
Thm 5.7 Property of Divisibility: Let \(f, g, h, u, v \in F[x]\).
1. \(g\mid f \implies \forall h\in F[x]\setminus\{0\}, gh \mid fh\)
2. \(g\mid f, f\mid h \implies g\mid h\)
3. \(g\mid f, f\mid g \implies f = a g\) for some \(a \in F^*\)
4. \(f\mid u, f\mid v \implies \forall a, b \in F[x], f\mid (au + bv)\)
Axiom 5.8: Let \(S\subseteq\mathbb{Z}^+ \cup \{0, -\infty\}\)
1. If \(S\neq \emptyset\), \(S\) contains the smallest number (including \(-\infty\)).
2. If \(S\) contains a non-negative integer, then \(S\) contains the smallest non-negative integer.
3. If \(S\) contains a positive integer, then \(S\) contains the smallest positive integer.
Thm 5.9: Let \(f, g \in F[x]\) with \(g \neq 0\). Then there exist unique pair of polynomials \(q, r \in F[x]\) satisfying \[ f = q \cdot g + r, \quad \deg(r) < \deg(g) \]
▶
Proof
- Uniqueness: Assume taht \((q_1, r_1), (q_2, r_2)\) are two pairs of polynomials satisfying \(\begin{cases} f = q_1 \cdot g + r_1 \\ f = q_2 \cdot g + r_2 \end{cases}\). Then \((q_1 - q_2) \cdot g = r_2 - r_1\), so we have \[ \begin{aligned} &\deg((q_1 - q_2) \cdot g) = \deg(q_1 - q_2) + \deg(g) \\ &\deg(r_2 - r_1) \leq \max\{\deg(r_1), \deg(r_2)\} < \deg(g) \end{aligned} \] Then \(\deg(q_1 - q_2) < 0 \implies \deg(q_1 - q_2) = -\infty \implies q_1 = q_2 \implies r_1 = r_2\). Thus the two pairs are the same.
- Existence: Consider the set \(S = \{\deg(f - h \cdot g) : h \in F[x]\}\), thus \(S\neq\emptyset\). By Axiom 5.8, \(S\) contains the smallest number \(t\) (including \(-\infty\)), thus \(\exists q \in F[x]\) s.t. \(\deg(f - q \cdot g) = t\). Let \(r = f - q \cdot g\), thus \(\deg(r) = t\). Claim that \(\deg(r) < \deg(g)\):
  
  Suppose \(\deg(r) \geq \deg(g)\), then write \[ \begin{aligned} r(x) &= r_n x^n + r_{n-1} x^{n-1} + \cdots + r_0 \quad (r_n \neq 0) \\ g(x) &= g_m x^m + g_{m-1} x^{m-1} + \cdots + g_0 \quad (g_m \neq 0) \end{aligned} \] Let \(u(x) = r(x) - r_n g_m^{-1} x^{n-m} g(x)\), then \(\deg(u) \leq n-1 < n = \deg(r) = t\), thus \(r(x) = u(x) + r_n g_m^{-1} x^{n-m} g(x) = f(x) - q(x) \cdot g(x)\), thus \(u(x) = f(x) - (q(x) + r_n g_m^{-1} x^{n-m}) \cdot g(x)\), which means \(\deg(u) \in S\) and \(\deg(u) < t\), contradicting the definition of \(t\).

Greatest Common Divisor

Def 5.10 GCD: Let \(f, g \in F[x]\) and \((f,g)\neq (0,0)\), then a greatest common divisor (GCD) of \(f\) and \(g\) is defined to be the monic polynomial \(d\) satisfying
1. \(d \mid f, d \mid g\).
2. \(d_1 \mid f, d_1 \mid g \implies d_1 \mid d\).
Thm 5.11: The GCD of \(f, g\) exists and is unique, denoted by \(\gcd(f,g)\).
▶
Proof
- Uniqueness: Assume that \(d_1, d_2\) are two GCDs of \(f, g\). Then \(d_1 \mid d_2\) and \(d_2 \mid d_1\), thus \(\exists a,b \in F[x]\) s.t. \(d_1 = a d_2\) and \(d_2 = b d_1\), thus \(d_1 = a b d_1 \implies d_1 (1 - a b) = 0 \implies ab = 1 \implies a, b \in F^*\). So \(a=b=1\), thus \(d_1 = d_2\).
- Existence: Consider the set \(S = \{\deg(uf + vg) : u, v \in F[x], (u,v) \neq (0,0)\}\), thus \(S\neq\emptyset\). By Axiom 5.8, \(S\) contains the smallest non-negative integer \(t\), thus \(\exists a, b \in F[x]\) s.t. \(\deg(af + bg) = t\). Let \(d = af + bg\), thus \(\deg(d) = t\). WLOG, we assume that \(d\) is monic, otherwise we can divide it by its leading coefficient. Claim that \(d=\gcd(f,g)\):
  
  Let \(f=q\cdot d + r\) with \(\deg(r) < \deg(d)\), then \[ \begin{aligned} r &= f - q \cdot d \\ &= f - q \cdot (af + bg) \\ &= (1 - qa)f + (-qb)g \end{aligned} \] Thus \(\deg(r) \in S \implies \deg(r) = -\infty \implies r=0 \implies d \mid f\). Similarly, \(d \mid g\).
  
  If \(d_1 \mid f, d_1 \mid g\), then \(d_1 \mid (af + bg)\), i.e. \(d_1 \mid d\).
Def 5.12 Coprime: Two polynomials \(f, g \in F[x]\) are said to be coprime if \(\gcd(f,g) = 1\).
Cor 5.13 Bézout’s Identity: Let \(f, g \in F[x]\) with \((f,g) \neq (0,0)\), then \(\exists u, v \in F[x]\) s.t. \(uf + vg = \gcd(f,g)\).
Thm 5.14 Properties of GCD: Let \(f, g, h, f_i \in F[x]\), then
1. \(a(x)\) is monic \(\implies \gcd(af, ag) = a \cdot \gcd(f,g)\)
2. \(\gcd\left(\frac{f}{\gcd(f,g)}, \frac{g}{\gcd(f,g)}\right) = 1\)
3. \(\gcd(f_i,g)=1, i=1,2,\cdots,t \implies \gcd\left(\prod_{i=1}^t f_i, g\right)=1\)
4. \(h\mid fg,~\gcd(h,g)=1 \implies h\mid f\)
5. \(\forall r\in F[x], \gcd(f,g)=\gcd(f, g+rf)\)

Euclidean Algorithm

Thm 5.15 Euclidean Algorithm: Give \(f, g \in F[x]\) with \(g \neq 0\), let \(r_0=f, r_1=g\), we can compute \(r_2, r_3, \cdots\) by long division: \[ \begin{cases} r_0 = q_1 \cdot r_1 + r_2, & 0 \leq \deg(r_2) < \deg(r_1) \\ r_1 = q_2 \cdot r_2 + r_3, & 0 \leq \deg(r_3) < \deg(r_2) \\ \cdots \\ r_{n-2} = q_{n-1} \cdot r_{n-1} + r_n, & 0 \leq \deg(r_n) < \deg(r_{n-1}) \\ r_{n-1} = q_n \cdot r_n, & \deg(r_{n+1}) = -\infty \text{ (i.e. } r_{n+1} = 0\text{)} \end{cases} \]
Thm 5.16: By the Euclidean Algorithm given above, \(\gcd(r_i, r_{i+1}) = \gcd(r_{i+1}, r_{i+2})\) for \(i=0,1,\cdots,n-2\).
- In particular, \(\gcd(f,g) = u^{-1} r_n\), where \(u\) is the leading coefficient of \(r_n\).
Thm 5.17 Extended Euclidean Algorithm: Given \(f, g \in F[x]\) with \(g \neq 0\), let \(r_0=f, r_1=g, s_0=1, s_1=0, t_0=0, t_1=1\), we can compute \(r_2, r_3, \cdots\) by long division, and compute \(s_i,t_i\) by \[ \begin{cases} s_{i+1}=s_{i-1}-q_is_i \\ t_{i+1}=t_{i-1}-q_it_i \end{cases} \]
Thm 5.17: By the Extended Euclidean Algorithm given above, \(r_i=f s_i+g t_i\) for \(i=0,1,\cdots,n\).
- In particular, \(\gcd(f,g) = u^{-1} r_n= u^{-1} (f s_n + g t_n)\), where \(u\) is the leading coefficient of \(r_n\).

Least Common Multiple

Def 5.18 LCM: Let \(f, g \in F[x]\) with \((f,g) \neq (0,0)\), then a least common multiple (LCM) of \(f\) and \(g\) is defined to be the monic polynomial \(D\) satisfying
1. \(f \mid D, g \mid D\).
2. \(\forall D' \in F[x], f \mid D', g \mid D' \implies D \mid D'\).
Thm 5.19: The LCM of \(f, g\) exists and is unique, denoted by \(\mathrm{lcm}(f,g)\).
▶
Proof
- Uniqueness: Assume that \(D_1, D_2\) are two LCMs of \(f, g\). Then \(D_1 \mid D_2\) and \(D_2 \mid D_1\), thus \(\exists a,b \in F[x]\) s.t. \(D_1 = a D_2\) and \(D_2 = b D_1\), thus \(D_1 = a b D_1 \implies D_1 (1 - a b) = 0 \implies ab = 1 \implies a, b \in F^*\). So \(a=b=1\), thus \(D_1 = D_2\).
- Existence: Consider the set \(S = \{\deg(u): f \mid u, g \mid u\}\), thus \(fg \in S\), so \(S\neq\emptyset\). By Axiom 5.8, \(S\) contains the smallest non-negative integer \(t\), thus \(\exists D \in F[x]\) s.t. \(\deg(D) = t\) and \(f \mid D, g \mid D\). WLOG, we assume that \(D\) is monic, otherwise we can divide it by its leading coefficient. Claim that \(D=\mathrm{lcm}(f,g)\):
  
  If \(D' \in F[x]\) satisfies \(f \mid D', g \mid D'\), then \(\deg(D') \in S\), thus \(\deg(D') \geq t = \deg(D)\), let \(D' = q \cdot D + r\) with \(\deg(r) < \deg(D)\), then \(r = D' - q \cdot D\), thus \(f \mid r, g \mid r\), thus \(\deg(r) \in S\), thus \(\deg(r) = -\infty\), thus \(r=0\), thus \(D \mid D'\).
Thm 5.20 Properties of LCM: Let \(f, g, h, f_i \in F[x]\), then
1. \(a(x)\) is monic \(\implies \mathrm{lcm}(af, ag) = a \cdot \mathrm{lcm}(f,g)\)
2. \(\gcd(f,g)=1\) and \(f,g\) are monic \(\implies \mathrm{lcm}(f,g) = f \cdot g\)
3. \(f,g\) are monic \(\implies \gcd(f,g) \cdot \mathrm{lcm}(f,g) = f \cdot g\)
  ▶
  Proof of 3
  Let \(d = \gcd(f,g)\), then \(\gcd\left(\frac{f}{d}, \frac{g}{d}\right) = 1\), thus we have: \[ \frac{\mathrm{lcm}(f,g)}{d} = \mathrm{lcm}\left(\frac{f}{d}, \frac{g}{d}\right) = \frac{f}{d} \cdot \frac{g}{d} \]
  
  Thus \(\gcd(f,g) \cdot \mathrm{lcm}(f,g) = d \cdot d \cdot \mathrm{lcm}\left(\frac{f}{d}, \frac{g}{d}\right) = f \cdot g\).

Irreducible Polynomials

Def 5.21 Irreducible Polynomial: A non-constant polynomial \(f\) is called irreducible if \(f\) is only divisible by \(a\) or \(af\) for some \(a \in F^*\).
Thm 5.22: \(f\) is irreducible \(\iff (f\mid ab \implies f\mid a \text{ or } f\mid b)\).
▶
Proof
- \(\implies\):
  
  If \(f\mid a\), done.
  
  If \(f\nmid a\), then \(\gcd(f,a) = 1\), thus \(f\mid b\), done.
- \(\impliedby\): Suppose \(f\) were not irreducible, then \(f=g\cdot h\) with \(1\leq \deg(g), \deg(h) < \deg(f)\), thus \(f\mid g\cdot h \implies f\mid g \text{ or } f\mid h\), thus \(\deg(f) \leq \deg(g)\) or \(\deg(f) \leq \deg(h)\), contradiction.
Lemma 5.23: \(\forall f \in F[x]\) with \(\deg(f) \geq 1, \exists p \in F[x]\) s.t. \(p\mid f\) and \(p\) is irreducible.
▶
Proof
- Consider the set \(S = \{\deg(u): u\mid f, \deg(u) \geq 1\}\), thus \(f \in S\), so \(S\neq\emptyset\). By Axiom 5.8, \(S\) contains the smallest positive integer \(t\), thus \(\exists p \in F[x]\) s.t. \(\deg(p) = t\) and \(p \mid f\). Claim that \(p\) is irreducible: Assume that \(q\mid p\), then \(\deg(q) \leq \deg(p)\)
  
  If \(q\in F^*\), then \(p\) is irreducible.
  
  If \(q\notin F^*\), then \(\deg(q) \geq 1\), thus \(q\mid p, p\mid f \implies q\mid f\), thus \(\deg(q) \in S\), thus \(\deg(q) \geq t \implies \deg(q) = \deg(p)\). Let \(p = q \cdot r\), then \(\deg(r) = \deg(p) - \deg(q) = 0\), thus \(r \in F^*\) and \(q=r^{-1} p\), thus \(p\) is irreducible.
Thm 5.24: There are infinitely many monic irreducible polynomials in \(F[x]\).
Thm 5.25: Every non-zero polynomial \(f\) can be uniquely factorized into a product of \(a\in F^*\) and monic irreducible polynomials \(p_i\), i.e. \[ f(x) = a \cdot p_1(x) \cdot p_2(x) \cdots p_t(x) \]
- Notation: Let \(p\) be an irreducible polynomial, if \(p^k \mid f\) and \(p^{k+1} \nmid f\), then we denote \(v_p(f) = k\) and call it the exponent of \(p\) in \(f\).
Thm 5.26: Let \(f, g \in F[x]\) be two non-zero polynomials, \(p\) be monic irreducible polynomial, then
1. \[f = a \cdot \prod_{p} p^{v_p(f)}\]
2. \[\gcd(f,g) = \prod_{p} p^{\min\{v_p(f), v_p(g)\}}\]
3. \[\mathrm{lcm}(f,g) = \prod_{p} p^{\max\{v_p(f), v_p(g)\}}\]

Congruence

Congruence and Residue Classes

Def 5.27 Congruence: Let \(m \in F[x]\) with \(\deg(m) \geq 1\), then two polynomials \(a,b \in F[x]\) are said to be congruent modulo \(m\) if \[ m(x) \mid a(x) - b(x) \]

Denoted by \(a(x)\equiv b(x) \pmod{m(x)}\).
Thm 5.28 Properties of Congruence:
1. \(a\equiv b \pmod m\) and \(c\equiv d \pmod m \implies\)
  - \(a+c\equiv b+d \pmod m\)
  - \(a-c\equiv b-d \pmod m\)
  - \(ac\equiv bd \pmod m\)
2. \(m>\gcd(m,c), ac\equiv bc \pmod m \implies a\equiv b \pmod{\frac{m}{\gcd(m,c)}}\)
Def 5.29 Residue Class: Let \(r,m\in F[x]\), the residue class of \(r\) modulo \(m\) is defined to be \[ [r]_m = \{a \in F[x]: a \equiv r \pmod{m}\} \]

If there is no confusion, we denote \([r]_m\) by \(\bar{r}\) for simplicity.
Lemma 5.30:
1. \(\forall r_1,r_2\in F[x]\), we have \([r_1]_m=[r_2]_m\) or \([r_1]_m\cap [r_2]_m=\emptyset\).
2. \(F[x] = \bigcup_{r\in F[x]} [r]_m = \overset{\centerdot}{\bigcup}_{\deg(r)<\deg(m)} [r]_m\).
  - Notation: \(\overset{\centerdot}{\bigcup}\) means the union of disjoint sets.
  ▶
  Proof of 2
  For any \(f \in F[x]\), let \(f = q \cdot m + r\) with \(\deg(r) < \deg(m)\), then \(f \equiv r \pmod m\), thus \(f \in [r]_m\), thus \(F[x] \subseteq \bigcup_{\deg(r)<\deg(m)} [r]_m\). Since \(\forall r, [r]_m \subseteq F[x]\), we have \(\bigcup_{\deg(r)<\deg(m)} [r]_m \subseteq F[x]\). Thus \(F[x] = \bigcup_{\deg(r)<\deg(m)} [r]_m\).
  
  Let \(r_1 \neq r_2\) with \(\deg(r_1), \deg(r_2) < \deg(m)\). Thus \(r_1 - r_2 \neq 0\) and \(\deg(r_1 - r_2) < \deg(m)\), thus \(m \nmid (r_1 - r_2)\), i.e. \(r_1 \not\equiv r_2 \pmod m\). By Lemma 5.30(1), we have \([r_1]_m \cap [r_2]_m = \emptyset\), thus the union is disjoint.
Def 5.31 Complete Residue System: \(F[x]/(mF[x])\) is the set of all residue classes modulo \(m\), i.e. \[ F[x]/(mF[x]) = \{\bar{r}: \deg(r) < \deg(m)\} = \left\{\overline{\sum_{i=0}^{\deg(m)-1} a_i x^i} : a_i \in F\right\} \]

If there is no confusion, we denote \(F[x]/(mF[x])\) by \(F[x]/(m)\) for simplicity.
▶
Example
1. \(m(x)=x\), then \(\deg(m) = 1\), thus \[ F[x]/(m) = F[x]/(x) = \{\bar{r}: \deg(r) < 1\} = \{\bar{a}: a \in F\} \cong F \]
2. \(m(x)=x^2+1\), then \(\deg(m) = 2\), thus \[ F[x]/(m) = \{\bar{r}: \deg(r) < 2\} = \{\overline{a + bx}: a,b \in F\} \cong F^2 \]
Def 5.32 Addition and Multiplication: Define addition \(+\) and multiplication \(\cdot\) on \(F[x]/(m)\) by \[ \begin{aligned} \bar{r}_1 + \bar{r}_2 &= \overline{r_1 + r_2} \\ \bar{r}_1 \cdot \bar{r}_2 &= \overline{r_1 \cdot r_2} \end{aligned} \]
Thm 5.33: Under the above addition and multiplication, \(F[x]/(m)\) forms a commutative ring with the additive identity \(\bar{0}\) and the multiplicative identity \(\bar{1}\).
Def 5.34 Invertible Element: A polynomial \(a\in F[x]\) is called invertible modulo \(m\) if \(\exists b\in F[x]\) s.t. \[ a\cdot b \equiv 1 \pmod m \]

I.e. \(a\) is a unit in the commutative ring \(F[x]/(m)\), and \(b\) is called the inverse of \(a\) modulo \(m\), denoted by \(a^{-1}\).
Thm 5.35 Properties of Invertible: \(a\) is invertible modulo \(m \iff \gcd(a,m) = 1\).
▶
Proof
- \(\implies\): If \(a\) is invertible modulo \(m\), then \(\exists b\in F[x]\) s.t. \(a\cdot b \equiv 1 \pmod m\), thus \(\exists u\in F[x]\) s.t. \(a\cdot b - 1 = u \cdot m\), thus \(a\cdot b - u \cdot m = 1\), thus \(\gcd(a,m) = 1\).
- \(\impliedby\): By Bézout’s Identity, \(\exists u,v\in F[x]\) s.t. \(a\cdot u + m \cdot v = 1\), thus \(a\cdot u \equiv 1 \pmod m\), thus \(a\) is invertible modulo \(m\) and \(u\) is the inverse of \(a\) modulo \(m\).
Def 5.36 Unit Group: The unit group of the ring \(F[x]/(m)\) is denoted by \[ (F[x]/(m))^* = \{\bar{r} \in F[x]/(m) : \gcd(r,m) = 1\} \]

Euler Function and Chinese Remainder Theorem

Def 5.37 Euler Function: The Euler function \(\Phi_p(m)\) is defined to be the number of invertible elements in the ring \(\mathbb{Z}_p[x]/(m)\) with \(\deg(m) \geq 1\), i.e. \[ \Phi_p(m) = |(\mathbb{Z}_p[x]/(m))^*| = \#\{\bar{r} \in \mathbb{Z}_p[x]/(m) : \gcd(r,m) = 1\} \]
- When \(\deg(\alpha) = 0\), we define \(\forall \alpha \in \mathbb{Z}_p^*, \Phi_p(\alpha) \triangleq 1\).
▶
Example
1. To compute \(\Phi_2(x)\), consider the ring \[ \mathbb{Z}_2[x]/(x) = \{\bar{r}: \deg(r) < 1\} = \{\bar{a}: a \in \mathbb{Z}_2\} = \{\bar{0}, \bar{1}\} \] Thus \[ (\mathbb{Z}_2[x]/(x))^* = \{\bar{1}\} \] Thus \(\Phi_2(x) = 1\).
2. To compute \(\Phi_2(x^3)\), consider the ring \[ \mathbb{Z}_2[x]/(x^3) = \{\bar{r}: \deg(r) < 3\} = \{\overline{a + bx + cx^2}: a,b,c \in \mathbb{Z}_2\} \] Thus \[ \begin{aligned} (\mathbb{Z}_2[x]/(x^3))^* &= \{\bar{r} \in \mathbb{Z}_2[x]/(x^3) : \gcd(r,x^3) = 1\} \\ &= \{\overline{1 + bx + cx^2}: b,c \in \mathbb{Z}_2\} \end{aligned} \] Thus \(\Phi_2(x^3) = 4\).
Thm 5.38 Chinese Remainder Theorem: Let \(m_1, m_2, \cdots, m_t\) be pairwise coprime polynomials in \(F[x]\) with \(\deg(m_i) \geq 1\), then \(\forall a_1,a_2,\cdots,a_t\in F[x]\), the system of congruences \[ \begin{cases} x\equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \\ \cdots \\ x\equiv a_t \pmod {m_t} \end{cases} \]

has a unique solution \(x\in F[x]/(M)\) with \(M=\prod_{i=1}^t m_i\).
Thm 5.39 Properties of Euler Function: Let \(m,n,d\in \mathbb{Z}_p[x]\)
1. If \(\gcd(m,n) = 1\), then \[ \Phi_p(mn) = \Phi_p(m) \cdot \Phi_p(n) \]
2. If \(q(x)\) is an irreducible polynomial, then \[ \begin{aligned} \Phi_p(q^n) &= p^{(n-1)\deg(q)} (p^{\deg(q)} - 1) \\ &= p^{n\deg(q)} \left(1 - \frac{1}{p^{\deg(q)}}\right) \end{aligned} \]
  - In particular, \(q\) irreducible \(\implies \Phi_p(q) = p^{\deg(q)} - 1\).
3. For any polynomial \(m\), we have \[ \Phi_p(m) = p^{\deg(m)} \prod_{q\mid m, \atop q \text{ monic irreducible}} \left(1 - \frac{1}{p^{\deg(q)}}\right) \]
  - In prticular, \(\deg(m) = 1 \implies \Phi_p(m) = p - 1\).
▶
Proof
1. If \(m\in \mathbb{Z}_p^*\), then \(\Phi_p(mn) = \Phi_p(n) = \Phi_p(m) \cdot \Phi_p(n)\) since \(\Phi_p(m) = 1\). So we just need to consider the case when \(\deg(m) \geq 1\) and \(\deg(n) \geq 1\):
  
  Since \(\begin{cases}\Phi_p(mn) = |(\mathbb{Z}_p[x]/(mn))^*| \\ \Phi_p(m)\Phi_p(n) = |(\mathbb{Z}_p[x]/(m))^* \times (\mathbb{Z}_p[x]/(n))^*| \end{cases}\), it is sufficient to show that there is a bijection between \((\mathbb{Z}_p[x]/(mn))^*\) and \((\mathbb{Z}_p[x]/(m))^* \times (\mathbb{Z}_p[x]/(n))^*\).
  
  Consider the map: \[ \begin{aligned} \varphi: (\mathbb{Z}_p[x]/(mn))^* &\to (\mathbb{Z}_p[x]/(m))^* \times (\mathbb{Z}_p[x]/(n))^* \\ [r]_{mn} &\mapsto ([r]_m, [r]_n) \end{aligned} \] It is easy to prove that \(\varphi\) is well-defined and is a ring isomorphism, thus \(\varphi\) is a bijection, thus \(\Phi_p(mn) = \Phi_p(m) \cdot \Phi_p(n)\).
2. Consider the set \[ \begin{aligned} S &= (\mathbb{Z}_p[x]/(q^n)) \backslash (\mathbb{Z}_p[x]/(q^n))^* = \{\bar{r} \in \mathbb{Z}_p[x]/(q^n) : \gcd(r,q^n) \neq 1\} \\ &= \{\overline{uq}: u \in \mathbb{Z}_p[x]\} \\ &= \{\overline{uq}: \deg(uq) < \deg(q^n)\} \\ &= \{\overline{uq}: \deg(u) < (n-1)\deg(q)\} \\ &= \{\overline{\sum_{i=0}^{(n-1)\deg(q)-1} u_i x^i q}: u_i \in \mathbb{Z}_p\} \end{aligned} \] Thus \(|S| = p^{(n-1)\deg(q)}\), thus \[ \begin{aligned} \Phi_p(q^n) &= |\mathbb{Z}_p[x]/(q^n)| - |S| \\ &= p^{n\deg(q)} - p^{(n-1)\deg(q)} \\ &= p^{n\deg(q)} \left(1 - \frac{1}{p^{\deg(q)}}\right) \end{aligned} \]
3. Let \(m = \alpha \cdot \prod_{i=1}^t q_i^{e_i}\) be the standard factorization of \(m\), \(\alpha \in \mathbb{Z}_p^*\) is the leading coefficient of \(m\), \(q_i\) are monic irreducible polynomials, then \[ \begin{aligned} \Phi_p(m) &= \prod_{i=1}^t \Phi_p(q_i^{e_i}) \\ &= \prod_{i=1}^t p^{e_i \deg(q_i)} \left(1 - \frac{1}{p^{\deg(q_i)}}\right) \\ &= p^{\deg(m)} \prod_{i=1}^t \left(1 - \frac{1}{p^{\deg(q_i)}}\right) \\ \end{aligned} \]
Thm 5.40: \[\sum_{d\mid m, \atop d \text{ monic}} \Phi_p(d) = p^{\deg(m)}\]
▶
Proof
- Let \(m = \alpha \cdot \prod_{i=1}^t q_i^{e_i}\) be the standard factorization of \(m\), \(\alpha \in \mathbb{Z}_p^*\) is the leading coefficient of \(m\), \(q_i\) are monic irreducible polynomials, then \(d = \prod_{i=1}^t q_i^{k_i}, 0 \leq k_i \leq e_i\) is a monic divisor of \(m\), thus \[ \begin{aligned} \sum_{d\mid m, \atop d \text{ monic}} \Phi_p(d) &= \sum_{0\leq k_i \leq e_i} \Phi_p\left(\prod_{i=1}^t q_i^{k_i}\right) \\ &= \sum_{0\leq k_i \leq e_i} \prod_{i=1}^t \Phi_p(q_i^{k_i}) \\ &= \prod_{i=1}^t \left(\sum_{k_i=0}^{e_i} \Phi_p(q_i^{k_i})\right) \\ &= \prod_{i=1}^t \left(\sum_{k_i=0}^{e_i} \left(p^{k_i \deg(q_i)} - p^{(k_i-1) \deg(q_i)}\right)\right) \\ &= \prod_{i=1}^t \left(p^{e_i \deg(q_i)}\right) \\ &= p^{\deg(m)} \end{aligned} \]

Primitive Elements

Thm 5.41: \(\gcd(a,m) = 1 \implies a^{\Phi_p(m)} \equiv 1 \pmod m\)
▶
Proof
- Let \(l = \Phi_p(m)\), then we can label the elements of \((\mathbb{Z}_p[x]/(m))^*\) by \(\{\bar{r}_1, \bar{r}_2, \cdots, \bar{r}_l\}\) with \(\bar{r}_1 = \bar{a}\). Consider the set \(S = \{\bar{a} \cdot \bar{r}_1, \bar{a} \cdot \bar{r}_2, \cdots, \bar{a} \cdot \bar{r}_l\}\), then \(S = (\mathbb{Z}_p[x]/(m))^*\), thus \(\prod_{i=1}^l \bar{r}_i = \prod_{i=1}^l (\bar{a} \cdot \bar{r}_i) = \bar{a}^l \cdot \prod_{i=1}^l \bar{r}_i\), thus \(\bar{a}^l = 1\), thus \(a^{\Phi_p(m)} \equiv 1 \pmod m\).
Def 5.42 Order: Let \(a\in F[x]\) be a non-zero polynomial with \(\gcd(a,m) = 1\), the order of \(a\) modulo \(m\) is defined to be the smallest positive integer \(k\) s.t. \[ a^k \equiv 1 \pmod m \]

Denoted by \(\mathrm{ord}_m(a)\).
Thm 5.43 Properties of Order:
1. \(a^l \equiv 1 \pmod m \implies \mathrm{ord}_m(a) \mid l\)
2. \(\mathrm{ord}_m(a^t) = \frac{\mathrm{ord}_m(a)}{\gcd(\mathrm{ord}_m(a), t)}\)
3. \(\gcd(\mathrm{ord}_m(a), \mathrm{ord}_m(b)) = 1 \implies \mathrm{ord}_m(ab) = \mathrm{ord}_m(a) \cdot \mathrm{ord}_m(b)\)
Def 5.44 Primitive Element: An element \(g \in F[x]\) with \(\gcd(g,m) = 1\) is called a primitive element modulo \(m\) if \[ \mathrm{ord}_m(g) = \Phi_p(m) \]
Thm 5.45: Let \(m \in \mathbb{Z}_p[x]\) with \(\deg(m) \geq 1\), if there exists a primitive element modulo \(m\), then there are exactly \(\varphi(\Phi_p(m))\) primitive elements modulo \(m\).
▶
Proof
- Let \(g\) be a primitive element modulo \(m\), then \((\mathbb{Z}_p[x]/(m))^* = \{\bar{g}^0, \bar{g}^1, \cdots, \bar{g}^{\Phi_p(m)-1}\}\), thus \(\bar{g}^k\) is a primitive element modulo \(m \iff \mathrm{ord}_m(\bar{g}^k) = \frac{\Phi_p(m)}{\gcd(\Phi_p(m), k)} = \Phi_p(m) \iff \gcd(\Phi_p(m), k) = 1\), thus there are exactly \(\varphi(\Phi_p(m))\) primitive elements modulo \(m\).
Thm 5.46: \(\mathbb{Z}_p[x]/(q)\) is a field \(\iff q\) is irreducible.
▶
Proof
- \(\impliedby\): Let \(u\in \mathbb{Z}_p[x]/q\) with \(u \neq 0\). and \(\deg(u) < \deg(q)\), since \(q\) is irreducible, we have \(\gcd(u,q) = 1\), then by the Bézout’s Identity, \(\exists a,b\in \mathbb{Z}_p[x]\) s.t. \(a\cdot u + b \cdot q = 1\), thus \(a\cdot u \equiv 1 \pmod q\), thus \(u\) is a unit in \(\mathbb{Z}_p[x]/(q)\), thus \(\mathbb{Z}_p[x]/(q)\) is a field.
- \(\implies\): Suppose not, thus \(q\) is reducible, then \(\exists u,v \in \mathbb{Z}_p[x]\) with \(1 \leq \deg(u), \deg(v) < \deg(q)\) s.t. \(u\cdot v = q\), thus \(\bar{u} \cdot \bar{v} = \bar{0}\), thus \(\bar{u}\) is a zero divisor in \(\mathbb{Z}_p[x]/(q)\), thus \(\mathbb{Z}_p[x]/(q)\) is not a field, contradiction.
Thm 5.47: If \(q\in \mathbb{Z}_p[x]\) is irreducible, then there exists a primitive element modulo \(q\).
▶
Proof structure
1. Factorize \(\Phi_p(q) = p^{\deg(q)} - 1 = \prod_{i=1}^t p_i^{e_i}\)
2. Find \(g_i\) s.t. \(\mathrm{ord}_q(g_i) = p_i^{e_i}\) for each \(i\).
3. Let \(g = \prod_{i=1}^t g_i\), then it is a primitive element modulo \(q\).
Thm 5.48: If \(q\in \mathbb{Z}_p[x]\) is irreducible and \(k \geq 2\), then there exists a primitive element modulo \(q^k \iff\)
- \(p\neq 2\), \(k=2\) and \(\deg(q) = 1\), or
- \(p=2\), \(2\leq k \leq 3\) and \(\deg(q) = 1\).
▶
Proof
- \(\impliedby\):
  
  \(k=2\): Let \(g\in \mathbb{Z}_p[x]\) be a primitive element modulo \(q\), then \(\mathrm{ord}_q(g) = \Phi_p(q) = p^{\deg(q)} - 1 = p - 1\). Then we have: \[ \begin{aligned} & g^{\mathrm{ord}_{q^2}(g)} \equiv 1 \pmod{q^2} \\ \implies & g^{\mathrm{ord}_{q^2}(g)} \equiv 1 \pmod{q} \\ \implies & p - 1 = \Phi_p(q) \mid \mathrm{ord}_{q^2}(g) \mid \Phi_p(q^2) = p(p - 1) \\ \end{aligned} \]
  
  Thus if \(\mathrm{ord}_{q^2}(g) = p(p - 1)\), then \(g\) is a primitive element modulo \(q^2\).
  
  Else if \(\mathrm{ord}_{q^2}(g) = p - 1\), then consider the element \(g + q\), we have \(\mathrm{ord}_{q^2}(g + q) = p-1\) or \(p(p-1)\). Suppose \(\mathrm{ord}_{q^2}(g + q) = p - 1\), then we have: \[ \begin{aligned} (g + q)^{p - 1} &= g^{p - 1} + \binom{p - 1}{1} g^{p - 2} q + \cdots + \binom{p - 1}{p - 2} g q^{p - 2} + q^{p - 1} \\ &\equiv g^{p - 1} + (p-1)g^{p - 2} q \\ &\equiv 1 - g^{p - 2} q \not\equiv 1 \pmod{q^2} \end{aligned} \] Thus contradiction, so \(\mathrm{ord}_{q^2}(g + q) = p(p - 1)\), thus \(g + q\) is a primitive element modulo \(q^2\).
  
  \(k=3\): Let \(g\in \mathbb{Z}_2[x]\) be a primitive element modulo \(q^2\), then \[ \begin{aligned} 2 = p(p-1) = \mathrm{ord}_{q^2}(g) \mid \mathrm{ord}_{q^3}(g) \mid \Phi_2(q^3) = p^2(p-1) = 4 \end{aligned} \] Thus \(\mathrm{ord}_{q^3}(g) = 2\) or \(4\). Suppose \(\mathrm{ord}_{q^3}(g) = 2\), thus \[ \begin{aligned} & g^2 \equiv 1 \pmod{q^3} \\ \implies & q^3 \mid g^2 - 1 = (g - 1)^2 \\ \implies & q^2 \mid g - 1 \end{aligned} \] Thus \(\mathrm{ord}_{q^2}(g) = 1\), contradiction, thus \(\mathrm{ord}_{q^3}(g) = 4\), thus \(g\) is a primitive element modulo \(q^3\).
- \(\implies\): We have \(\Phi_p(q^k) = (p^d - 1) \cdot p^{(k-1)d}\) with \(d = \deg(q)\). Let \(g\) be a primitive element modulo \(q^k\), then \(\mathrm{ord}_{q^k}(g) = \Phi_p(q^k)\). Let \(t = \lceil \log_p(k)\rceil\), then \(p^t \geq k\). Since \(\gcd(g, q^k) = 1 \implies \gcd(g, q) = 1\), we have \[ \begin{aligned} & g^{\Phi_p(q)} \equiv 1 \pmod q \\ \implies & q \mid g^{\Phi_p(q)} - 1 \\ \implies & q^k \mid q^{p^t} \mid (g^{\Phi_p(q)} - 1)^{p^t} = g^{\Phi_p(q) \cdot p^t} - 1 \\ \implies & g^{\Phi_p(q) \cdot p^t} \equiv 1 \pmod{q^k} \\ \implies & (p^d - 1)p^{(k-1)d} = \Phi_p(q^k) = \mathrm{ord}_{q^k}(g) \mid \Phi_p(q)p^t = (p^d - 1)p^t \\ \implies & p^{(k-1)d} \mid p^t \\ \implies & (k-1)d \leq t \end{aligned} \]
  
  If \(p\neq 2\), then \((k-1)d \leq t = \lceil \log_p(k) \rceil \leq \lceil \ln(k) \rceil \leq \lceil k-1 \rceil = k-1\), thus \(d = 1\), thus \(\lceil \log_p(k) \rceil = k-1\), thus \(k=2\).
  
  If \(p=2\):
  
  If \(d\geq 2\), then \(2k-2 \leq (k-1) \leq \lceil \log_2(k) \rceil\). Since linearly \(2k-2\) grows faster than \(\lceil \log_2(k) \rceil\) and \(k=2\) not satisfies the inequality, contradiction, thus \(d=1\).
  
  If \(d=1\), then \(k-1 \leq \lceil \log_2(k) \rceil\). Since linearly \(k-1\) grows faster than \(\lceil \log_2(k) \rceil\) and \(k=4\) not satisfies the inequality, contradiction, thus \(k \leq 3\).
  
  Thus we have:
  
  \(p\neq 2\), \(k=2\) and \(\deg(q) = 1\), or
  
  \(p=2\), \(2\leq k \leq 3\) and \(\deg(q) = 1\).
Thm 5.49: Let \(m(x) \in \mathbb{Z}_p[x]\) have the standard factorization \(m(x) = \alpha \prod_{i=1}^n q_i^{e_i}(x)\). There exists a primitive element modulo \(m(x) \iff\)
1. \(\prod_{i=1}^n \Phi_p(q_i^{e_i}) = \mathrm{lcm}\{\Phi_p(q_1^{e_1}), \dots, \Phi_p(q_n^{e_n})\}\). I.e. \(\forall 1 \leq i \leq j \leq n\), \(\gcd(\Phi_p(q_i^{e_i}), \Phi_p(q_j^{e_j})) = 1\).
2. \(\forall 1 \leq i \leq n\), there exists a primitive element modulo \(q_i^{e_i}\). I.e. satisfies the condition in Thm 5.48.
▶
Proof
- By the Chinese Remainder Theorem for rings, we have the isomorphism of groups of units: \[ (\mathbb{Z}_p[x]/(m(x)))^* \cong (\mathbb{Z}_p[x]/(q_1^{e_1}(x)))^* \times \dots \times (\mathbb{Z}_p[x]/(q_n^{e_n}(x)))^* \] Let \(G = (\mathbb{Z}_p[x]/(m(x)))^*\) and \(G_i = (\mathbb{Z}_p[x]/(q_i^{e_i}(x)))^*\).
- Then we have:
  
  \(\qquad\) A primitive element modulo \(m(x)\) exists
  
  \(\iff G\) is a cyclic group
  
  \(\iff G_1 \times \dots \times G_n\) is cyclic
  
  \(\iff \forall 1 \leq i \leq n, G_i\) is cyclic and their orders \(|G_i| = \Phi_p(q_i^{e_i})\) are pairwise coprime
  
  \(\iff \forall 1 \leq i \leq n\), there exists a primitive element modulo \(q_i^{e_i}\) and \(\forall 1 \leq i \leq j \leq n\), \(\gcd(\Phi_p(q_i^{e_i}), \Phi_p(q_j^{e_j})) = 1\).
Thm 5.50: There exists a primitive element modulo \(m(x) \iff\)
- \(p \neq 2\):
  - \(m(x)\) is irreducible;
  - \(m(x) = \alpha(x-\beta)^2\) for some \(\alpha\in \mathbb{Z}_p^*\), \(\beta \in \mathbb{Z}_p\);
- \(p = 2\): \(m(x) = \alpha(x-\beta)^e \prod q_i(x)\) for some \(\alpha \in \mathbb{Z}_2^*\), \(\beta \in \mathbb{Z}_2\), satisfying:
  - \(0 \leq e \leq 3\);
  - \(\forall 1 \leq i < j \leq n\), \(\gcd(\deg(q_i), \deg(q_j)) = 1\);
  - \(x-\beta, q_i\) are distinct monic irreducible polynomials.
▶
Proof
- \(p\neq 2\):
  
  \(m(x)\) is irreducible: Proof by Thm 5.46 and Thm 5.47.
  
  \(m(x) = \alpha(x-\beta)^2\): Proof by Thm 5.48.
- \(p=2\):
  
  \(m(x) = \alpha\): \(\alpha = 1 \in \mathbb{Z}_2^*\), thus \(\Phi_2(m) = 1\), thus \(1\) is a primitive element modulo \(m\).
  
  \(m(x) = \alpha(x-\beta)\): Proof by Thm 5.46 and Thm 5.47.
  
  \(m(x) = \alpha(x-\beta)^2\) or \(m(x) = \alpha(x-\beta)^3\): Proof by Thm 5.48.
  
  \(m(x) = \alpha(x-\beta)^e \prod q_i(x)\): \(\deg(q_i)\) are pairwise coprime, since \(\gcd(2^a-1, 2^b-1) = 2^{\gcd(a,b)}-1\), thus \(\Phi_2(q_i) = 2^{\deg(q_i)} - 1\) are pairwise coprime. Since \(e \leq 3\), thus \(\Phi_2((x-\beta)^e) = 2^{e-1} \in \{1, 2, 4\}\) and is coprime to \(\Phi_2(q_i)\). Thus by Thm 5.49, there exists a primitive element modulo \(m\).

Lagrange interpolation

Roots

Def 5.51 Root: An element \(r \in F\) is called a root of \(f \in F[x]\) if \[ f(r) = 0 \]
Lemma 5.52: An element \(r \in F\) is a root of \(f \in F[x] \iff (x-r) | f(x)\)
▶
Proof
- \(\implies\): Write \(f(x) = q(x)(x-r) + r_0\) with \(\deg(r_0) < \deg(x-r) = 1\), then \(r_0 \in F\), thus \(0 = f(r) = r_0\), thus \(f(x) = q(x)(x-r)\), thus \((x-r) | f(x)\).
- \(\impliedby\): If \((x-r) | f(x)\), then \(f(x) = q(x)(x-r)\), thus \(f(r) = 0\), thus \(r\) is a root of \(f\).
Def 5.53 Derivative: If \(f(x) = a_0 + a_1x + \cdots + a_nx^n\), then the derivative \(f'\) of \(f\) is defined by \[ f' = a_1 + 2a_2x + \cdots + na_nx^{n-1} \]
Def 5.54 Multiplicity of Root: Let \(r \in F\) be a root of \(f \in F[x]\). If \(k\) is a positive integer s.t. \((x-r)^k | f\) but \((x-r)^{k+1} \nmid f\), then \(k\) is called the multiplicity of root \(r\).
- If \(k \ge 2\), the \(r\) is called a multiple root. Otherwise, it is called a simple root.
Thm 5.55 Property of Multiple Roots: An element \(r \in F\) is a multiple root of \(f \in F[x] \iff r\) is a common root of \(f\) and \(f'\).
Thm 5.56: Let \(F\) be a field and \(f \in F[x]\) with \(n := \deg(f) \ge 1\). Then \(F\) contains at most \(n\) distinct roots of \(f\).
▶
Proof
- We prove by induction on \(n\). If \(n=1\), then \(f(x) = a_1x + a_0\) with \(a_1 \neq 0\), thus \(f\) has exactly one root, thus the statement holds.
- Assume that the statement holds for any polynomial with degree less than \(n\).
  
  If \(f\) has no root, then the statement holds.
  
  Otherwise, let \(r\) be a root of \(f\), then by Lemma 5.52, we have \(f(x) = (x-r)g(x)\) with \(\deg(g) = n-1\), thus any root of \(f\) is either \(r\) or a root of \(g\), thus the number of distinct roots of \(f\) is at most \((n-1) + 1 = n\), thus the statement holds.

Lagrange Interpolation

Thm 5.57: The set \(F[x]_{<n} = \{f \in F[x] : \deg(f) < n\}\) forms a vector space over \(F\) with \(\dim(F[x]_{<n}) = n\). And It has a canonical basis \(\{1, x, \cdots, x^{n-1}\}\) and a lagrange basis \(\{L_i(x) = \prod_{j \ne i}(x-a_j)\}_{i=1}^n\), where \(a_1, \cdots, a_n\) are \(n\) distinct elements of \(F\).
▶
Proof of lagrange basis
- It is sufficient to show that they are linearly independent. Suppose \(\sum_{i=1}^n \lambda_i L_i(x) = 0\) for some \(\lambda_i \in F\), then \(\forall k\), we have \[ 0 = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(a_k - a_j) = \lambda_k \prod_{j \ne k}(a_k - a_j), \quad \prod_{j \ne k}(a_k - a_j) \neq 0 \] Since in the sum, when \(i \neq k\), the term \(\prod_{j \ne i}(a_k - a_j) = 0\), only when \(i = k\), the term \(\prod_{j \ne i}(a_k - a_j) = \prod_{j \ne k}(a_k - a_j) \neq 0\). Thus \(\forall k, \lambda_k = 0\), thus they are linearly independent.
Thm 5.58 Lagrange Interpolation: For \(n > 0\), let \(a_1, \cdots, a_n\) be \(n\) distinct elements of \(F\), and let \(b_1, \cdots, b_n\) be \(n\) arbitrary elements of \(F\). Then there exists a unique polynomial \(f \in F[x]\) with \(\deg(f) \le n-1\) s.t. \[ f(a_i) = b_i, \quad i=1,2,\cdots,n \]

Furthermore, this polynomial \(f\) is given by \[ f(x) = \sum_{i=1}^n \prod_{j \ne i} \frac{(x-a_j)}{(a_i-a_j)} b_i \]
▶
Proof method 1
- Let \(f(x) = \sum_{i=0}^{n-1} \lambda_i x^i\) satisfy \(f(a_i) = b_i\) for each \(i\). Then we have \[ \begin{pmatrix} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1} \end{pmatrix} \begin{pmatrix} \lambda_0 \\ \lambda_1 \\ \lambda_2 \\ \vdots \\ \lambda_{n-1} \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_n \end{pmatrix} \] Since the coefficient matrix is a Vandermonde matrix with distinct \(a_i\), it is invertible, thus there exists a unique solution \(\lambda_i\), thus there exists a unique polynomial \(f\) with \(\deg(f) \le n-1\) s.t. \(f(a_i) = b_i\) for each \(i\).
▶
Proof method 2
- Let \(f(x) = \sum_{i=1}^n \lambda_i L_i(x) = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(x-a_j)\) satisfy \(f(a_i) = b_i\) for each \(i\). Then we have \[ b_k = f(a_k) = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(a_k - a_j) = \lambda_k \prod_{j \ne k}(a_k - a_j) \] Thus \(\lambda_k = \frac{b_k}{\prod_{j \ne k}(a_k - a_j)}\), thus there exists a unique polynomial \(f=\sum_{i=1}^n \prod_{j \ne i} \frac{(x-a_j)}{(a_i-a_j)} b_i\) with \(\deg(f) \le n-1\) s.t. \(f(a_i) = b_i\) for each \(i\).

Chapter 6. Finite fields

Fields

Def 6.1 Field: A field is a communicative ring with the multiplicative identity \(1\) in which every nonzero element is invertible.
- Examples: \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\)
- Cor:
  - \(\mathbb{Z}/(p)\) is a field \(\iff p\) is a prime.
  - \(F[x]/(q(x))\) is a field \(\iff q(x)\) is irreducible.
Def 6.2 Characteristic: The characteristic of a field \(F\) is defined by the smallest positive integer \(p\) s.t. \[ p \cdot 1 = \underbrace{1 + \cdots + 1}_p = 0 \]

Denote the characteristic of a field \(F\) by \(\mathrm{char}(F)\). If there is no such \(p\), then \(\mathrm{char}(F) = 0\).
Thm 6.3: The characteristic of a field \(F\) is either \(0\) or a prime.
▶
Proof
- Suppose \(\mathrm{char}(F) = m > 0\) is a composite number. Then there exist \(1 < a, b < m\) such that \(m = ab\). Then \[ 0 = m \cdot 1 = (ab) \cdot 1 = (a \cdot 1)(b \cdot 1) \implies a \cdot 1 = 0 \text{ or } b \cdot 1 = 0 \] Thus contradicts the minimality of \(m\). Therefore, \(\mathrm{char}(F)\) must be a prime.
Def 6.4 Subfield and Field extension: Let \(E\) be a field and \(F \subseteq E\). If \(F\) is a field under the same addition and multiplication as \(E\), then \(E/F\) is called a field extension and \(F\) is called a subfield of \(E\).
Thm 6.5: If \(E/F\) is a field extension, then \(E\) can be viewed as a vector space over \(F\) with
- Vector addition：the addition of \(F\).
- Scalar multiplication：\(\forall \lambda \in F, \alpha \in F \implies \lambda \cdot \alpha\) is multiplication in \(F\).
Def 6.6 Prime field: The prime field of a field \(F\) is the smallest subfield of \(F\) containing \(1\).
Thm 6.7: The prime field of a field \(F\) is either \(\mathbb{Q}\) or \(\mathbb{Z}_p\) for a prime \(p\).
Def 6.8 Extension degree: If \(E/F\) is a field extension, then the extension degree of \(E/F\) is defined to be the dimension \(\dim_F E\), denoted by \([E : F]\). The extension \(E/F\) is called finite if \([E : F]\) is finite, otherwise \(E/F\) is called infinite.

▶
Example

\[ [\mathbb{C},\mathbb{Q}] = +\infty, \quad [\mathbb{C},\mathbb{R}] = 2 \]
Thm 6.9 Properties of Extension Degrees: Let \(E/F, F/K\) be field extension. Then
- \([E : K] = [E : F][F : K]\)
- \(E/K\) is a finite extension \(\iff\) Both \(E/F\) and \(F/K\) and finite extensions.
Def 6.10 Ring generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subring of \(E\) containing both \(F\) and \(\alpha\) is called the ring generated by \(\alpha\) over \(F\), denoted by \(F[\alpha]\). \[ F[\alpha] = \{f(\alpha) : f \in F[x]\} \]
Def 6.11 Field generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subfield of \(E\) containing both \(F\) and \(\alpha\) is called the field generated by \(\alpha\) over \(F\), denoted by \(F(\alpha)\). \[ F(\alpha) = \{\frac{f(\alpha)}{g(\alpha)} : f, g \in F[x], g(\alpha) \ne 0\} \]
Thm 6.12: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then \[ F(\theta) = F[\theta] = \left\{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\right\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\} \]

Furthermore, \([F(\theta) : F] = d\).
▶
Proof
1. \(F[θ]=\{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\}\):
  
  \(\forall f(\theta) \in F[\theta]\), since we can write \(f(x) = m(x)q(x) + r(x)\) with \(\deg(r) < \deg(m) = d\), thus \(f(\theta) = 0 \cdot q(\theta) + r(\theta) = r(\theta) \in \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\}\), thus \(F[\theta] \subseteq \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\} \subseteq \{f(\theta) : f \in F[x]\} = F[\theta]\).
  
  Thus \(F[\theta] = \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\}\) = \(\{f(\theta) : f \in F[x], \deg(f) \le d-1\}\).
2. \(F(\theta) = F[\theta]\):
  
  Obviously, \(F[\theta] \subseteq F(\theta)\). It is sufficient to show that \(F[\theta]\) is a field. Consider nonzero element \(r(\theta) \in F[\theta]\).
  
  \(\forall r(x) = \sum_{i=0}^{d-1} a_i\theta^i \neq 0\), we have not all \(a_i\) are zero. Thus \(\gcd(r(x), m(x)) = 1\), then by Bézout’s identity, there exist \(u,v \in F[x]\) s.t. \(u(x)r(x) + v(x)m(x) = 1\). Thus \(u(\theta)r(\theta) = 1\) since \(m(\theta) = 0\), thus \(r(\theta)\) is a unit. Therefore, \(F[\theta]\) is a field, thus \(F[\theta] = F(\theta)\).
3. \([F(\theta) : F] = d\): Since \(\{1, \theta, \ldots, \theta^{d-1}\}\) is a basis of \(F(\theta)\) over \(F\), we have \([F(\theta) : F] = d\).
Thm 6.13: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then \[ F[x]/(m) \simeq F(\theta) = F[\theta] \]
▶
Proof
- The first isomorphism theorem: Let \(R, S\) be rings and \(\pi : R \to S\) be a ring homomorphism. Then \(\ker(\pi) = \{r \in R : \pi(r) = 0\}\) is an ideal of \(R\) and \(\mathrm{Im}(\pi) = \{\pi(r) : r \in R\}\) is a subring of \(S\). Moreover, \(R/\ker(\pi) \simeq \mathrm{Im}(\pi)\).
- Consider the homomorphism \[ \begin{aligned} \pi : F[x] &\to F(\theta) \\ f(x) &\mapsto f(\theta) \end{aligned} \] Then \(\pi\) is a ring homomorphism and \(\ker(\pi) = \{f(x) \in F[x] : \pi(f) = f(\theta) = 0\} = \{f(x) \in F[x] : m(x) \mid f(x)\} = (m) = m(x)F[x]\). Thus by the first isomorphism theorem, we have \[ F[x]/(m) \simeq \mathrm{Im}(\pi) = F[\theta] = F(\theta) \]
▶
Example
1. \(x^2+1 \in \mathbb{R}[x]\) is irreducible, \(i\) is a root of \(x^2+1\). Thus \[ \mathbb{R}[x]/(x^2+1) \simeq \mathbb{R}[i] = \{a+bi : a,b \in \mathbb{R}\} = \mathbb{C} \]
2. \(x^2+x+1 \in \mathbb{Z}_2[x]\) is irreducible, since \(0,1\) are not roots. Let \(\theta\) be a root of \(x^2+x+1\). Then \[ \mathbb{Z}_2[x]/(x^2+x+1) \simeq \mathbb{Z}_2[\theta] = \{0, 1, \theta, 1+\theta\} \] Since \(\theta(\theta+1) = \theta^2 + \theta = -1 \equiv 1\), we have \(\theta^{-1} = \theta + 1\).

Finite fields

Def 6.14 Finite field: A field with finitely many elements is called a finite field or Galois field.
Thm 6.15 Properties of finite fields: Let \(F\) be a finite field of \(q\) elements, then
1. \(\mathrm{char}(F)\) is a prime \(p\).
2. \(\forall a, b \in F, (a+b)^p = a^p + b^p\).
3. \(\forall a \in F, a^q = a\).
▶
Proof
1. Since \(F\) is a field, \(\mathrm{char}(F)\) is either \(0\) or a prime. If \(\mathrm{char}(F) = 0\), then the prime field of \(F\) is \(\mathbb{Q}\), which is infinite. Thus \(\mathrm{char}(F)\) must be a prime \(p\).
2. \(\forall a, b \in F\), we have \[ (a+b)^p = \sum_{i=0}^p \binom{p}{i} a^i b^{p-i} = a^p + b^p \] since \(p \mid \binom{p}{i} = \frac{p!}{i!(p-i)!}\) for \(1 \le i \le p-1\).|
3. If \(a = 0\), done. If \(a \ne 0\), label \(q-1\) elements of \(F^*\) as \(F^* = \{a_1, a_2, \ldots, a_{q-1}\}\). Then \(\forall i, a_i^{q-1} = 1\), thus \(a_i^q = a_i\). Thus \(\forall a \in F, a^q = a\).
Thm 6.16 Structure of finite fields: Let \(F\) be a finite field of \(q\) elements, then
1. \(q = p^n\) for some prime \(p\) and integer \(n \ge 1\).
2. \(F^* = F \setminus \{0\}\) is a cyclic group of order \(p^n-1\).
▶
Proof
1. Since \(\mathrm{char}(F) = p\) is a prime, the prime field of \(F\) is \(\mathbb{Z}_p\). Thus \(F/\mathbb{Z}_p\) is a field extension. Since \(F\) is finite, \([F : \mathbb{Z}_p] = n < +\infty\). Thus \(|F| = p^n\).
2. Since \(F^*\) is a finite subgroup of the multiplicative group of a field, \(F^*\) is cyclic.
Thm 6.17: There exists a finite field of \(q\) elements \(\iff q = p^n\) for some prime \(p\) and integer \(n \ge 1\).
▶
Proof
- \(\implies\): has been proved in Thm 6.16.
- \(\impliedby\): Let \(m(x) \in \mathbb{Z}_p[x]\) be an irreducible polynomial with \(\deg(m) = n\). Then \(\mathbb{Z}_p[x]/(m) = \{\sum_{i=0}^{n-1} a_i x^i : a_i \in \mathbb{Z}_p\}\) is a field with \(p^n\) elements.
Def 6.18 Algebraically closed field: A field \(\Omega\) is called algebraically closed if \(\forall f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\) has at least one root in \(\Omega\).
Thm 6.19 Property of algebraically closed fields: A field \(\Omega\) is algebraically closed \(\iff \forall f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\), \(f(x)\) has all roots in \(\Omega\).
▶
Proof
- \(\implies\): Let \(f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\). We will show that \(f(x)\) has all roots in \(\Omega\) by induction on \(\deg(f)\).
  
  If \(\deg(f) = 1\), then \(f(x)\) has a root in \(\Omega\) since \(\Omega\) is algebraically closed.
  
  If \(\deg(f) > 1\), then \(f(x)\) has a root \(\alpha\) in \(\Omega\). Thus \(f(x) = (x-\alpha)g(x)\) for some \(g(x) \in \Omega[x]\) with \(\deg(g) = \deg(f)-1\). By the induction hypothesis, \(g(x)\) has all roots in \(\Omega\). Thus \(f(x)\) has all roots in \(\Omega\).
- \(\impliedby\): Obvious.
Thm 6.20: For any field \(F\), there exists an algebraically closed field \(\Omega\) containing \(F\).
Thm 6.21: Let \(p\) be a prime and let \(n \ge 1\), then there exists a unique finite field of \(p^n\) elements.
- Notation: We denote the unique finite field of \(q\) elements by \(\mathbb{F}_q\) or \(\mathrm{GF}_q\).
▶
Proof
- Existence: has been proved in Thm 6.17.
- Uniqueness: Let \(E, F\) be two finite fields with \(q=p^n\) elements. Then \(\forall a \in E, a^q = a\), i.e. \(a\) is a root of \(x^q - x\), thus \(E = \{a : a^q = a\} \in \Omega\). Similarly, \(F = \{a : a^q = a\} \in \Omega\). Thus \(E = F\).
▶
Example
- \(x^3 + x + 1 \in \mathbb{Z}_2[x]\) and \(x^3 + x^2 + 1 \in \mathbb{Z}_2[x]\) are irreducible. Let \(\alpha\) be a root of \(x^3 + x + 1\) and \(\beta\) be a root of \(x^3 + x^2 + 1\). Then \(\mathbb{Z}_2[x]/(x^3 + x + 1) \simeq \mathbb{Z}_2(\alpha)\) and \(\mathbb{Z}_2[x]/(x^3 + x^2 + 1) \simeq \mathbb{Z}_2(\beta)\) are two finite fields with \(8\) elements. By the uniqueness, we have \(\mathbb{Z}_2(\alpha) = \mathbb{Z}_2(\beta) = \mathbb{F}_8\).
Thm 6.22: \(\mathbb{F}_{p^n}\) is a field extension of \(\mathbb{F}_{p^k} \iff k \mid n\).
▶
Proof
- \(\implies\): Let \(E = \mathbb{F}_{p^n}\) and \(F = \mathbb{F}_{p^k}\). Then \([E : F] = \frac{[E : \mathbb{Z}_p]}{[F : \mathbb{Z}_p]} = \frac{n}{k}\). Since \([E : F]\) is an integer, we have \(k \mid n\).
- \(\impliedby\): Let \(m = \frac{n}{k}\). Then \(\mathbb{F}_{p^n}\) is a field extension of \(\mathbb{F}_{p^k}\) with extension degree \(m\).
Alg 6.23: Construction of finite fields of \(p^n\) elements:
1. Find a monic irreducible polynomial \(m(x)\) with \(\deg(m) = n\) over \(\mathbb{Z}_p\).
2. Find a root \(\theta\) of \(m(x)\) in an algebraically closed field \(\Omega\) containing \(\mathbb{Z}_p\).
3. Then \(\mathbb{Z}_p[x]/(m) \simeq \mathbb{Z}_p(\theta) = \{\sum_{i=0}^{n-1} a_i \theta^i : a_i \in \mathbb{Z}_p\}\) is a finite field with \(p^n\) elements.
▶
Example
- To construct a finite field of \(16\) elements, find an irreducible polynomial of degree \(4\) over \(\mathbb{Z}_2\).
  
  The only irreducible polynomial of degree \(2\) over \(\mathbb{Z}_2\) is \(x^2+x+1\).
  
  All irreducible polynomial of degree \(4\) over \(\mathbb{Z}_2\) are \(x^4+x^3+x^2+x+1, x^4+x^3+1, x^4+x+1\). We choose \(m(x) = x^4+x+1\) to construct \(\mathbb{F}_{16}\).
- Let \(\theta\) be a root of \(m(x)\), thus we have \[ \mathbb{F}_{16} = \mathbb{Z}_2[x]/(m) \simeq \mathbb{Z}_2(\theta) = \{a_0 + a_1\theta + a_2\theta^2 + a_3\theta^3 : a_i \in \mathbb{Z}_2\} \]
- And we have if \(\theta\) is a root of \(m(x)\), then \(\theta^{2^n}\) is also a root of \(m(x)\).
  
  Since \(m(\theta) = \theta^4 + \theta + 1 = 0\), thus \(\theta^4 = \theta + 1\).
  
  \(m(\theta^2) = (\theta^2)^4 + \theta^2 + 1 = (\theta^4)^2 + \theta^2 + 1 = (\theta^4 + \theta + 1)^2 = 0\). Thus \(\theta^2\) is a root of \(m(x)\).
  
  \(m(\theta^4) = m(\theta + 1) = (\theta+1)^4 + (\theta+1) + 1 = \theta^4 + \theta + 1 = 0\). Thus \(\theta^4\) is a root of \(m(x)\).
  
  \(m(\theta^8) = m((\theta^4)^2) = m((\theta+1)^2) = m(\theta^2 + 1) = (\theta^2+1)^4 + (\theta^2 + 1) + 1 = 0\). Thus \(\theta^8\) is a root of \(m(x)\).
  
  Since \(\theta^{16} = \theta\), we have \(m(\theta^{2^n}) = 0\) for all \(n \ge 0\). Thus \(\{\theta, \theta^2, \theta^4 = \theta + 1, \theta^8 = \theta^2 + 1\}\) are all distinct roots of \(m(x)\).
Thm 6.24: Let \(F_q\) be a finite field of \(q=p^k\) elements, and let \(I_q(d)=\#\{g \in F_q[x] : \deg(g) = d,\text{ irr, monic}\}\) be the number of monic irreducible polynomials with \(\deg(g) = d\) over \(F_q\). Then
1. Let \(n \ge 1 \in \mathbb{Z}\), then \[ x^{q^n} - x = \prod_{d \mid n} \prod_{g \in F_q[x], \text{ monic, irr} \atop \deg(g) = d} g(x) \]
2. We have the following identity, which can help us to compute \(I_q(d)\): \[ q^n = \sum_{d \mid n} d \cdot I_q(d) \]
3. By the Möbius inversion formula, we have \[ I_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) q^{\frac{n}{d}} \] where \(\mu(d)\) is the Möbius function defined by \[ \mu(d) = \begin{cases} 1 & d = 1 \\ (-1)^k & d = \prod_{i=1}^k p_i \text{ for distinct primes } p_i \\ 0 & \exists p \text{ s.t. } p^2 \mid d \end{cases} \]

SJTU Notes > 数学

#SJTU #抽代 #数论

初等数论与抽象代数

https://youyeyejie.github.io/_posts/初等数论与抽象代数/

作者

youyeyejie

发布于

2026年4月16日

更新于

2026年5月31日

现代密码学Ⅱ 上一篇

VSCode Snippets 设置与使用下一篇