初等数论与抽象代数

本笔记基于上海交通大学 邢朝平老师 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+1}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+1}\\t_{i+1}\end{pmatrix}=\begin{pmatrix}s_{i-1} & s_i\\t_{i-1} & t_i\end{pmatrix}\begin{pmatrix}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 \(d\cdot \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}\) 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\), 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<\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=4n_1+3, p_2=4n_2+3, \cdots, p_k=4n_k+3\),
    • Case 1: \(k\) is odd, then \(\prod_{i=1}^k p_i+4=\prod_{i=1}^k (4n_i+3)+4=4m+3\) for some \(m\in \mathbb{Z}\), thus \(\exists p_i\) s.t. \(p_i\mid (\prod_{i=1}^k p_i+4)\), thus \(p_i\mid 4\), contradiction since \(p_i>3\).
    • Case 2: \(k\) is even, then \(\prod_{i=1}^k p_i+2=\prod_{i=1}^k (4n_i+3)+2=4m+3\) for some \(m\in \mathbb{Z}\), thus \(\exists p_i\) s.t. \(p_i\mid (\prod_{i=1}^k p_i+2)\), thus \(p_i\mid 2\), contradiction since \(p_i>3\).
  • Thus, there are infinitely many primes of the form \(4n+3\).

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 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_j y_j\equiv 0 \pmod {m_i}\). 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{p},\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^* \subsetneq \mathbb{Z}_n\backslash \{\bar{0},\bar{p}\}\), thus \(\varphi(n)=|\mathbb{Z}_n^*|<|\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 \(\bar{a}\bar{b}\in \mathbb{Z}_m^*\):
    • Since \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), thus \(\gcd(ab,m)=1\), so \(\bar{a}\bar{b}\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)}\).
     • Suppose \((a^{l})^r\equiv 1 \pmod m\), thus \(k\mid lr\), so \(\frac{k}{\gcd(k,l)}\mid r\), thus \(\frac{k}{\gcd(k,l)}\leq r\).
     • 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\).
     • Suppose \((ab)^r\equiv 1 \pmod m\), thus \(1\equiv (ab)^ru=(a^u)^r(b^r)^u\equiv b^ru \pmod m\), thus \(v\mid ru\), so \(v\mid r\) since \(\gcd(u,v)=1\). Similarly, \(u\mid r\), so \(uv\leq r\).
     • So \(\mathrm{ord}_m(ab)=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 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\).

• Thm 3.8: 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 4 uses the fact that \(p\) is odd, so \(p\mid \binom{p^{k-2}}{i}\) for \(i\geq 2\)) \[ \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\).

• Cor 3.9: 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,2p^k)=1\), we have \(\mathrm{ord}_{2p^k}(g)\mid \varphi(2p^k)\).
    • Since \(\varphi(2p^k)=\varphi(2)\cdot \varphi(p^k)=\varphi(p^k)\) and \(\mathrm{ord}_{p^k}(g)=\varphi(p^k)\), 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)\).

• Algorithm 3.10: 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.10: 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\), claim that \(a\leq 2\): Otherwise, \(a\geq 3\), \(\varphi(g)=2^{a-1}\), thus \(g\) is odd. Let \(g=2k+1\) for some \(k\in \mathbb{Z}\), consider \(g^{2^{a-2}} \not\equiv 1 \pmod{2^a}\): \[ \begin{aligned} g^{2^{a-2}} &= (2k+1)^{2^{a-2}} = \sum_{i=0}^{2^{a-2}} \binom{2^{a-2}}{i} (2k)^i \\ &\equiv 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 \pmod{2^a} \\ &\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} \\ &\not\equiv 1 \pmod{2^a} \end{aligned} \] 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.8
    • \(m=2p^k\) for odd prime \(p\) and \(k\geq 1\): Show in Cor 3.9

• Algorithm 3.11: 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\), 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} \\ \iff ap &\equiv apg^{p-1} \not\equiv g^{p}-g \pmod{p^2} \\ \iff ap &\not\equiv g^p - g \pmod {p^2} \\ \iff a &\not\equiv \frac{g^p - g}{p} \pmod p \end{aligned} \]

       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^2\), 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.12: 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_1) \mid \mathrm{ord}_{p^{k+1}}(g_1) \mid \varphi(p^{k+1})=p^{k}(p-1)\), we have \(\mathrm{ord}_{p^{k+1}}(g)=p^t(p-1)\) for some \(t\in \{k-1,k\}\). \[ \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}} \mid pd\), thus \(\varphi(p^{k})\mid pd\), thus \(\varphi(p^{k-1})\mid d\), so \(d=\mathrm{ord}_{p^{k-1}}(g)=\varphi(p^{k-1})\).

Discrete Logarithm

• Def 3.13 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.14 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)}\).

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 \(x^2 - y^2 \equiv (x-y)(x+y) \equiv 0 \pmod p\), thus \(p \mid x-y\) or \(p \mid x+y\).
       • Since \(1\leq x < y \leq \frac{p-1}{2}\), \(x+y \leq \frac{p-1}{2} + \frac{p-1}{2} = p-1 < p\) and \(x-y < 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^{k(p-1)} \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.

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\):
       1. If \(m=3\), done.
       2. 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\):
     1. If \(m=3\), done.
     2. 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 \(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

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 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

  • Consier 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\equiv b \pmod{m}\).

• 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 identity 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 Cyclotomic Polynomial (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)\), thus we assume that \(\deg(m) \geq 1, \deg(n) \geq 1\).
     • Since \(\Phi_p(mn) = |(\mathbb{Z}_p[x]/(mn))^*|\) and \(\Phi_p(m)\Phi_p(n) = |(\mathbb{Z}_p[x]/(m))^* \times (\mathbb{Z}_p[x]/(n))^*|\), 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}^l u_i x^i) q}: l < (n-1)\deg(q), u_i \in \mathbb{Z}_p\} \\ &= \{\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]/(m)\) is a field \(\iff m\) is irreducible.

  ▶

  Proof

  • \(\impliedby\): Let \(u\in \mathbb{Z}_p[x]/m\) with \(u \neq 0\). and \(\deg(u) < \deg(m)\), since \(m\) is irreducible, we have \(\gcd(u,m) = 1\), then by the Bézout’s Identity, \(\exists a,b\in \mathbb{Z}_p[x]\) s.t. \(a\cdot u + b \cdot m = 1\), thus \(a\cdot u \equiv 1 \pmod m\), thus \(u\) is a unit in \(\mathbb{Z}_p[x]/(m)\), thus \(\mathbb{Z}_p[x]/(m)\) is a field.
  • \(\implies\): Suppose not, thus \(m\) is reducible, then \(\exists u,v \in \mathbb{Z}_p[x]\) with \(1 \leq \deg(u), \deg(v) < \deg(m)\) s.t. \(u\cdot v = m\), thus \(\bar{u} \cdot \bar{v} = \bar{0}\), thus \(\bar{u}\) is a zero divisor in \(\mathbb{Z}_p[x]/(m)\), thus \(\mathbb{Z}_p[x]/(m)\) is not a field, contradiction.

• Thm 5.47: If \(q\) 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\)

  1. \(p\neq 2\), \(k=2\) and \(\deg(q) = 1\), or
  2. \(p=2\), \(2\leq k \leq 3\) and \(\deg(q) = 1\).
  ▶

  Proof

  • \(\impliedby\):
    1. \(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\).
    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:
      1. \(p\neq 2\), \(k=2\) and \(\deg(q) = 1\), or
      2. \(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 is a primitive element modulo \(m(x)\) only if \(\prod_{i=1}^n \Phi_p(q_i^{e_i}) = \mathrm{lcm}\{\Phi_p(q_1^{e_i}), \dots, \Phi_p(q_n^{e_n})\}\), i.e. \(\forall 1 \leq i \neq j \leq n\), \(\gcd(\Phi_p(q_i^{e_i}), \Phi_p(q_j^{e_j})) = 1\).

• Thm 5.50: There is a primitive element modulo \(m(x) \iff\)

  • \(p \neq 2\), \(m(x)\) is irreducible or \(m(x) = \alpha(x-\beta)^2\) for some \(\alpha\in \mathbb{Z}_p^*\), \(\beta \in \mathbb{Z}_p\); or
  • \(p = 2\), \(m(x) = \alpha(x-\beta)^e \prod q_i(x)\) with \(\forall 1 \leq i < j \leq n\), \(\gcd(\deg(q_i), \deg(q_j)) = 1\), where \(0 \leq e \leq 3\), \(\alpha \in \mathbb{Z}_2^*\), \(\beta \in \mathbb{Z}_2\), and \(x-\beta, q_i\) are distinct monic irreducible polynomials.

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.49, 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 \(\{\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 \prod_{j \ne i}(x-a_j) = 0\) for some \(\lambda_i \in F\), then \(\forall k\), we have \[ 0 = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(a_i - a_j) = \lambda_k \prod_{j \ne k}(a_k - a_j) \] 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 \prod_{j \ne i}(x-a_j)\) satisfy \(f(a_i) = b_i\) for each \(i\). Then we have \[ \begin{aligned} 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) \end{aligned} \] 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}/(m)\) is a field \(\iff m\) is a prime.
    • \(F[x]/(m(x))\) is a field \(\iff m(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 Smallest subring: 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 denoted by \(F[\alpha]\). \[ F[\alpha] = \{f(\alpha) : f \in F[x]\} \]

• Def 6.11 Smallest subfield: 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 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)\) be an irreducible polynomial with \(\deg(m) = d\) over \(F\) 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

  • Obviously, \(F[\theta] \subseteq F(\theta)\). It is sufficient to show that \(F[\theta]\) is a field.
    • \(\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] = \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\}\).
    • \(\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 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.

• Thm 6.13: Let \(m(x)\) be an irreducible polynomial with \(\deg(m) = d\) over \(F\) 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) \subseteq 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 with \(p^n\) elements.

  • Notation: We denote the unique finite field with \(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: \(\mathrm{F}_{p^n}\) is a field extension of \(\mathrm{F}_{p^k} \iff k \mid n\).

  ▶

  Proof

  • \(\implies\): Let \(E = \mathrm{F}_{p^n}\) and \(F = \mathrm{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 \(\mathrm{F}_{p^n}\) is a field extension of \(\mathrm{F}_{p^k}\) with extension degree \(m\).

• Alg 6.23: Construction of finite fields of \(p^n\) elements:

  1. Find an 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) = (\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)\).