初等数论与抽象代数
本笔记基于上海交通大学 邢朝平老师 2025-2026 学年春季学期 信息安全数学基础2 课程教学内容进行整理,若有侵权请联系删除。
- 定义: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
\(\forall c \in \mathbb{Z}, b\mid a \implies bc\mid ac\)
\(c\mid b,~b\mid a \implies c \mid a\)
\(a\mid b,~b\mid a \implies a=\pm b\)
\(d\mid a,~d\mid b \implies \forall u,v \in \mathbb{Z},~d \mid (ua+vb)\)
▶ProofSince \(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)\). (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
- There is a least positive integer in \(S\)
- 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 thecondition, 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, thereis 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\).
- Uniqueness: Let
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.
- \(d\mid a,~d\mid b\)
- \(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, weassume \(b\ne 0\), then \(\pm b\in S\), \(S\cap \mathbb{Z}^+ \ne \varnothing\). By WOP, there is a leastpositive 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 \inS\), this forces \(r=0\) due tominimality of \(d\), thus \(d\mid a\). - \(d\mid b\): Similar to
\(d\mid a\). - Let \(d'\) be a common divisorof \(a,b\), then
\(d'\mid (u_0a+v_0b)\), thus \(d'\mid d\). - Thus, \(d=\gcd(a,b)\).
- \(d\mid a\): Let
- Uniqueness: Let \(d_1,d_2\) be two GCDs of \((a,b)\),then \(d_1\mid d_2\) and
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
- \(m>0 \implies m\cdot \gcd(a,b)=\gcd(ma, mb)\)
- \(\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1\)
- \(\gcd(a_i,b)=1, i=1,2,\cdots,t \implies \gcd\left(\prod_{i=1}^t a_i, b\right)=1\)
- \(c\mid ab,~\gcd(c,b)=1 \implies c\mid a\)
- \(\forall r\in\mathbb{Z}, \gcd(a,b)=\gcd(a, b+ra)\)
▶Proof- 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'\)
- \(d\mid a,~d\mid b\), thus
- Let \(d=\gcd(a,b)\), then
\(\gcd(\frac{a}{d},\frac{b}{d})=\frac{1}{d}\gcd(a,b)=1\) - Since Bézout’s Identity, \(\existsu_i,v_i\in\mathbb{Z}\) s.t. \(u_ia_i+v_i b=1\), thus \(\prod_{i=1}^t(u_ia_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\). - 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\). - 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' \midd\)
- Thus, \(d=d'\)
- \(d\mid a,~d\mid b\), thus
Euclidean Algorithm
Thm 1.9 Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b\), we can compute \(r_2, r_3, \cdots\) by long division: \[ \begin{cases} r_0=q_1r_1+r_2, & 0\le r_2<r_1 \\ r_1=q_2r_2+r_3, & 0\le r_3<r_2 \\ \cdots \\ r_{i-1}=q_ir_i+r_{i+1}, & 0\le r_{i+1}<r_i \\ \cdots \\ r_{n-1}=q_{n}r_n, & r_{n+1}=0 \end{cases} \]
then \(\gcd(r_{i-1},r_i)=\gcd(r_i, r_{i+1})\) for all \(i=1,2,\cdots,n-1\). In particular, \(\gcd(a,b)=\gcd(r_0,r_1)=\cdots=\gcd(r_{n-1},r_n)=r_n\)
- the matrix form of Euclidean Algorithm:
\[ \begin{pmatrix}a \\ b\end{pmatrix} =\begin{pmatrix}r_0 \\ r_1\end{pmatrix} =\begin{pmatrix}q_1 & 1 \\ 1 &0\end{pmatrix}\begin{pmatrix}r_1 \\ r_2\end{pmatrix} =\cdots =\begin{pmatrix}q_1 & 1 \\ 1 &0\end{pmatrix}\begin{pmatrix}q_2 & 1 \\ 1 &0\end{pmatrix}\cdots\begin{pmatrix}q_n & 1 \\ 1 &0\end{pmatrix}\begin{pmatrix}r_n \\ 0\end{pmatrix} \]
▶ProofBy 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}\]
- the matrix form of Euclidean Algorithm:
Thm 1.10 Extended Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b, s_0=1, s_1=0, t_0=0, t_1=1\), we can compute \(r_2, r_3, \cdots\) by long division, and compute \(s_i,t_i\) by \[ \begin{cases} s_{i+1}=s_{i-1}-q_is_i \\ t_{i+1}=t_{i-1}-q_it_i \end{cases} \]
then \(r_i=a s_i+b t_i\) for all \(i\ge 0\). In particular, \(\gcd(a,b)=r_n=a s_n+b t_n\).
- the matrix form of Extended Euclidean Algorithm:
\[ \begin{pmatrix}s_i & s_{i+1}\\ t_i &t_{i+1}\end{pmatrix}=\begin{pmatrix}s_{i-1} & s_i\\t_{i-1} &t_i\end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 &-q_i\end{pmatrix},\quad \begin{pmatrix}s_0 & s_1\\t_0 &t_1\end{pmatrix}=\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix} \]
▶ProofWe can prove by induction that \(r_i=as_i+b t_i\) for all \(i\ge0\).
- Base case:
- \(i=0\),
\(r_0=a s_0+b t_0=a\cdot 1 + b\cdot0=a\) - \(i=1\),
\(r_1=a s_1+b t_1=a\cdot 0 + b\cdot1=b\)
- \(i=0\),
- Induction step: Assume \(r_i=a s_i+bt_i\) and \(r_{i-1}=a s_{i-1}+bt_{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} \]
- the matrix form of Extended Euclidean Algorithm:
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.
- \(a\mid D,~b\mid D\)
- \(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 aleast 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 multipleof \(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\midD'\). - Thus, \(D=\mathrm{lcm}(a,b)\).
- \(a\mid D\) and
- Uniqueness: Let \(D_1,D_2\) be two LCMs of \((a,b)\),then \(D_1\mid D_2\) and
Thm 1.13 Properties of LCM: Let \(a,b,c\in\mathbb{Z}^*\), then
- \(m>0 \implies m\cdot \mathrm{lcm}(a,b)=\mathrm{lcm}(ma, mb)\)
- \(\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\)
- \(\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|\)
▶Proof- 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'\)
- \(a\mid D\) and
- 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\), wehave \(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|\).
- WLG, we assume \(a,b>0\). Let\(d=\gcd(a,b)\), then
\(\gcd(\frac{a}{d},\frac{b}{d})=1\) by Thm1.8(2), thus \(\mathrm{lcm}(a,b) = d\cdot\mathrm{lcm}(\frac{a}{d},\frac{b}{d})=d\cdot \frac{a}{d}\cdot\frac{b}{d}=\frac{ab}{d}\), thus \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|\).
Prime
Def 1.14 Prime: A positive integer \(p>1\) is called prime if its only positive divisors are \(1\) and \(p\). Otherwise, we call it composite.
Thm 1.15 Equivalent definition of prime: \(p>1\) is a prime \(\iff\) \(\forall a,b\in \mathbb{Z}, p\mid ab \implies p\mid a\) or \(p\mid b\).
▶Proof- (\(\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\).
- Case 1:
- (\(\impliedby\)) Suppose
\(p\) were not a prime, then \(\exists 1<u<p\) s.t. \(u\mid p\), thus \(p=\frac{p}{u}\cdot u \implies p\mid\frac{p}{u}\cdot u \implies p\mid \frac{p}{u}\) or \(p\mid u\), both of which are impossiblesince \(1<u<p\). Contradiction,thus \(p\) is a prime.
- (\(\implies\))
Thm 1.16: There are infinitely many primes.
▶Proof by Euclid's methodSuppose there are only finitely many primes
\(p_1, p_2, \cdots, p_k\), consider \(n=\prod_{i=1}^k p_i + 1\) must be acomposite number, then \(\exists p_i\)s.t. \(p_i\mid n\), thus \(p_i\mid (n-\prod_{i=1}^k p_i)\implies p_i\mid1\), contradiction, thus there are infinitely many primes. ▶Proof by Saliak's methodChose \(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 primedivisors. Then consider \(n(n+1)(n(n+1)+1)\), it has at least threedistinct prime divisors. By induction, we can show that there areinfinitely 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\), obviouslytrue.
- Induction step: \(n>2\), if\(\frac{n}{p_1} = 1\) for some primedivisor \(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\). Byinduction hypothesis, \(\frac{n}{p_1}\)can be factorized into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) can befactorized into a product of primes.
- Uniqueness: By induction on
\(n\). - Base case: \(n=2\), obviouslytrue.
- Induction step: \(n>2\), let\(p_1\) be the smallest prime divisorof \(n\), then
\(\frac{n}{p_1}\in \mathbb{Z}\) and \(1\leq\frac{n}{p_1}<n\). By inductionhypothesis, \(\frac{n}{p_1}\) has aunique factorization into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) has a uniquefactorization into a product of primes.
Cor 1.18: Let \(m,n\in \mathbb{Z}^+\), then
- \[\gcd(m,n)=\prod_{p\in \mathbb{P}} p^{\min\{v_p(m), v_p(n)\}}\]
- \[\mathrm{lcm}(m,n)=\prod_{p\in \mathbb{P}} p^{\max\{v_p(m), v_p(n)\}}\]
Thm 1.19: There are infinitely many primes of the form \(4n+3\).
▶Proof- Suppose there are only finitely many primes of the form
\(4n+3\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the otherprimes must be of the form \(4n+1\) or\(2\). Consider the number: \[ N = 4\prod_{i=1}^k p_i - 1 \] then we have \(N \equiv 3\pmod{4}\). Since \(N\) is ofthe form \(4n+3\), it must be acomposite number. - Since \(N\) is odd,
\(2\nmid N\), suppose \(N\) is a composite number. Thus, any primedivisor of \(N\) must be of the form\(4n+1\) or \(4n+3\). - If all prime divisors of \(N\) areof the form \(4n+1\), then
\(N \equiv 1 \pmod{4}\) since \(\prod_{i=1}^t (4n_i+1) \equiv 1 \pmod{4}\),contradiction. - Thus, \(\exists i\in\{1,2,\dots,k\}\) s.t. \(p_i\midN\), thus \(p_i\mid (4\prod_{i=1}^k p_i- N)\), thus \(p_i\mid 1\),contradiction.
- If all prime divisors of \(N\) areof the form \(4n+1\), then
- Thus, \(N\) is a new prime of theform \(4n+3\), contradiction. Thus,there are infinitely many primes of the form
\(4n+3\).
- Suppose there are only finitely many primes of the form
Thm 1.20: There are infinitely many primes of the form \(3n+2\).
▶Proof- Suppose there are only finitely many primes of the form
\(3n+2\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the otherprimes must be of the form \(3n+1\) or\(3\). Consider the number: \[ N = 3\prod_{i=1}^k p_i - 1 \] then we have \(N \equiv 2\pmod{3}\). Since \(N\) is ofthe form \(3n+2\), it must be acomposite number. - Since \(3\nmid N\), thus any primedivisor of \(N\) must be of the form\(3n+1\) or
\(3n+2\). - If all prime divisors of \(N\) areof the form \(3n+1\), then
\(N \equiv 1 \pmod{3}\) since \(\prod_{i=1}^t (3n_i+1) \equiv 1 \pmod{3}\),contradiction. - Thus, \(\exists i\in\{1,2,\dots,k\}\) s.t. \(p_i\midN\), thus \(p_i\mid (3\prod_{i=1}^k p_i- N)\), thus \(p_i\mid 1\),contradiction.
- If all prime divisors of \(N\) areof the form \(3n+1\), then
- Thus, \(N\) is a new prime of theform \(3n+2\), contradiction. Thus,there are infinitely many primes of the form
\(3n+2\).
- Suppose there are only finitely many primes of the form
Thm 1.21: There are infinitely many primes of the form \(4n+1\).
▶Proof By Quadratic Residue- Suppose there are only finitely many primes of the form
\(4n+1\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Consider thenumber: \[ N = \left(2\prod_{i=1}^k p_i\right)^2 + 1 = 4\left(\prod_{i=1}^kp_i\right)^2 + 1 \] then we have \(N \equiv 1\pmod{4}\). Since \(N\) is ofthe form \(4n+1\), it must be acomposite number. - Let \(p\) be a prime divisor of\(N\), obviously
\(p\ne 2\) since \(N\) is odd and \(p\neq p_i\) since \(p_i\nmid N\). Thus, we have \[ \left(2\prod_{i=1}^k p_i\right)^2 \equiv -1 \pmod{p} \] which means \(-1\) is aquadratic residue modulo \(p\) - Thus
\(\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=1\),thus \(p\equiv 1 \pmod{4}\), thus \(p\) is a new prime of the form \(4n+1\), contradiction. Thus, there areinfinitely many primes of the form \(4n+1\).
- Suppose there are only finitely many primes of the form
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
- \(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\)
- \(m>\gcd(m,c), ac\equiv bc \pmod m \implies a\equiv b \pmod{\frac{m}{\gcd(m,c)}}\)
▶Proof- We only prove the last one. \(\existsu,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\). - 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)}}\).
- \(a\equiv b \pmod m\) and \(c\equiv d \pmod m \implies\)
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:
- \(\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\).
- \(\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- 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\equivr_2 \pmod m\). So \(\forall x\in[r_1]_m\), we have \(x\equiv r_1 \equivr_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\). - \(\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 divisionalgorithm, \(\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
- \(\forall i\neq j, [r_i]_m\cap [r_j]_m=\emptyset\)
- \(\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}\).
▶ProofSince \(\bar{a}=\bar{a}_1\) and\(\bar{b}=\bar{b}_1\), we have
\(a\equiv a_1 \pmod m, b\equiv b_1 \pmod m\),thus \(\exists u,v\in \mathbb{Z}\) s.t.\(a-a_1=um\) and \(b-b_1=vm\), thus \((a+b)-(a_1+b_1)=(a-a_1)+(b-b_1)=um+vm=(u+v)m\),thus \(\overline{a+b}=\overline{a_1+b_1}\).Similarly, we can prove \(\overline{ab}=\overline{a_1b_1}\). Conclusion: \(\mathbb{Z}_m\) is a commutative ring with zero element \(\bar{0}\) and multiplicative identity element \(\bar{1}\).
Def 2.7 Invertible Element: An element \(\bar{r}\in \mathbb{Z}_m\) is called invertible if there exists \(\bar{r}'\in \mathbb{Z}_m\) s.t. \[\bar{r}\cdot \bar{r}'=\bar{1}\] In this case we call \(\bar{r}'\) the inverse of \(\bar{r}\), denoted by \(\bar{r}^{-1}\).
- Every element \(\bar{r}\in \mathbb{Z}_m\) have the additive inverse \(-\bar{r}=\overline{-r}\) since \(\bar{r}+(-\bar{r})=\overline{r+(-r)}=\bar{0}\), but not every element \(\bar{r}\in \mathbb{Z}_m\) have the multiplicative inverse.
Thm 2.8: Let \(r\in \mathbb{Z}\) and \(m\in \mathbb{Z}^+\), then \(\bar{r}\in \mathbb{Z}_m\) is multiplicative invertible \(\iff \gcd(r,m)=1\). In this case, the inverse is unique, denoted by \(\bar{r}^{-1}\).
▶Proof- \(\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\). - \(\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\).
- Uniqueness: If
- \(\implies\): Since
Euler Function and Chinese Remainder Theorem
Def 2.9 Euler Function: For \(m\in \mathbb{Z}^+\), the Euler function \(\varphi(m)\) is defined to be the cardinality of invertible elements of the set \[\mathbb{Z}_m^* = \{\bar{r}\in \mathbb{Z}_m: \gcd(r,m)=1\}\] i.e. \(\varphi(m)=|\mathbb{Z}_m^*|\).
- Remark: \(\mathbb{Z}_m^*\) forms a multiplicative group with identity element \(\bar{1}\).
- Example: \(\varphi(1)=1\), \(\varphi(2)=1\), \(\varphi(3)=2\), \(\varphi(4)=2\), \(\varphi(5)=4\), \(\varphi(6)=2\), \(\varphi(7)=6\), \(\varphi(8)=4\), \(\varphi(9)=6\), \(\varphi(10)=4\).
Thm 2.10 Chinese Remainder Theorem: Let \(m_1,m_2,\cdots,m_r\in \mathbb{Z}^+\) be pairwise coprime integers \(\geq 2\), (i.e. \(\forall i\neq j, \gcd(m_i,m_j)=1\)), then \(\forall a_1,a_2,\cdots,a_r\in \mathbb{Z}\), the system of congruences \[ \begin{cases} x\equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \\ \cdots \\ x\equiv a_r \pmod {m_r} \end{cases} \]
has a unique solution modulo \(M=\prod_{i=1}^r m_i\), and the solution \(x=\sum_{i=1}^r a_i M_i y_i\), where \(M_i=\frac{M}{m_i}\) and \(y_i\) is the inverse of \(M_i\) in \(\mathbb{Z}_{m_i}\).
▶Proof- Uniqueness: If
\(x_1\) and \(x_2\) are two solutions, then \(\forall 1\leq i\leq r, x_1\equiv a_i \equiv x_2\pmod {m_i}\), thus \(x_1\equiv x_2\pmod {m_i}\), since \(\gcd(m_i,m_j)=1\) for \(i\neq j\), we have \(x_1\equiv x_2 \pmod M\). - Existence: Let
\(M_i=\frac{M}{m_i}\), so \(\gcd(M_i,m_i)=1\), by Thm 2.8, there exists\(y_i\in \mathbb{Z}\) s.t. \(\overline{M_i}\cdot\overline{y_i}=\bar{1}\) in \(\mathbb{Z}_{m_i}\), thus \(M_i y_i\equiv 1 \pmod {m_i}\) and \(\forall j\neq i, M_i y_i\equiv 0 \pmod{m_j}\). Let \(x=\sum_{i=1}^r a_i M_iy_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.
- Uniqueness: If
Thm 2.11 Properties of Euler Function: Let \(m,n\in \mathbb{Z}^+\), then
- \(m,n\geq 2, \gcd(m,n)=1 \implies \varphi(mn)=\varphi(m)\varphi(n)\)
- \(\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}) \]
▶ProofClaim 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) \iffm\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)\). - \(\pi\) is well-defined:
First consider \(n=p^r\) where\(p\) is a prime and
\(r\in \mathbb{Z}^+\), consider \[\mathbb{Z}_n \backslash \mathbb{Z}_n^*=\{\overline{0},\overline{1p},\overline{2p},\cdots,\overline{(p^{r-1}-1)p}\}\] then \(|\mathbb{Z}_n \backslash\mathbb{Z}_n^*|=p^{r-1}\), thus \[\varphi(n)=|\mathbb{Z}_n^*|=|\mathbb{Z}_n|-|\mathbb{Z}_n \backslash\mathbb{Z}_n^*|=p^r-p^{r-1}=p^r(1-\frac{1}{p})\]
For general \(n\), let
\(p_1,p_2,\cdots,p_k\) be the distinct primedivisors 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}^kp_i^{r_i}(1-\frac{1}{p_i})=n\prod_{p\mid n}(1-\frac{1}{p})\]
Cor 2.12:
Let \(p\) be a prime and \(r\in \mathbb{Z}^+\), then \(\varphi(p^r)=p^r-p^{r-1}\).
\(\varphi(n)=n-1 \iff n\) is a prime.
▶Proof- If \(n\) is a prime, then
\(\varphi(n)=n-1\). - If \(n\) is not a prime, then
\(\exists 1<p<n\) s.t. \(p\mid n\), thus \(\gcd(p,n)=p\neq 1\), thus \(\bar{p}\not\in \mathbb{Z}_n^*\), thus \(\mathbb{Z}_n^* \subseteq \mathbb{Z}_n\backslash\{\bar{0},\bar{p}\}\), thus \(\varphi(n)=|\mathbb{Z}_n^*| \leq|\mathbb{Z}_n\backslash \{\bar{0},\bar{p}\}|=n-2<n-1\).
- If \(n\) is a prime, then
Set \(\varphi(1)=1\), then \(\forall n\geq 1, \sum_{d\mid n} \varphi(d)=n\).
▶ProofLet \(n=\prod_{i=1}^k p_i^{e_i}\) bethe 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^*\), weclaim that \(\overline{ab}\in\mathbb{Z}_m^*\): - Since \(\gcd(a,m)=1\) and
\(\gcd(b,m)=1\), thus \(\gcd(ab,m)=1\), so \(\overline{ab}\in \mathbb{Z}_m^*\).
- Since \(\gcd(a,m)=1\) and
- 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^*\).
- Since
- 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\).
- Since \(\gcd(a,m)=1\), then
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\mida\), then \(a^p\equiv 0 \equiv a \pmodp\).
- Case 2: \(p\nmida\), then \(\gcd(a,p)=1\) and\(a\in \mathbb{Z}_p^*\), by Thm 3.1,\(a^{\varphi(p)}=a^{p-1}\equiv 1 \pmodp\), thus \(a^p\equiv a \pmodp\).
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 apositive integer \(k\) such that \(\bar{a}^k=\bar{1}\). - Uniqueness: Let
\(S=\{k\in \mathbb{Z}^+: a^k\equiv 1 \pmodm\}\), thus \(S\) containspositive 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
- \(a^l\equiv 1 \pmod m \iff
\mathrm{ord}_m(a)\mid l\).
- In particular, \(\mathrm{ord}_m(a)\mid \varphi(m)\).
- \(\mathrm{ord}_m(a)=k \implies\mathrm{ord}_m(a^l)=\frac{k}{\gcd(k,l)}\).
- \(\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- 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 \pmodm\), thus \(r=0\), so \(k\mid l\). - \(\impliedby\): Let
\(l=kq\), then \(a^l=(a^k)^q\equiv 1 \pmod m\).
- \(\implies\): Write
- Proof of 2
- Consider
\((a^l)^\frac{k}{\gcd(k,l)}=(a^k)^\frac{l}{\gcd(k,l)}\equiv1 \pmod m\), thus \(\mathrm{ord}_m(a^l)\mid\frac{k}{\gcd(k,l)}\). - Let \(r=\mathrm{ord}_m(a^l)\), then\((a^{l})^r\equiv 1 \pmod m\), thus\(k\mid lr\). Since
\(\frac{k}{\gcd(k,l)} \mid\frac{l}{\gcd(k,l)}r\) and \(\gcd(\frac{k}{\gcd(k,l)},\frac{l}{\gcd(k,l)})=1\), we have \(\frac{k}{\gcd(k,l)}\mid r =\mathrm{ord}_m(a^l)\). - So
\(\mathrm{ord}_m(a^l)=\frac{k}{\gcd(k,l)}\).
- Consider
- 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\miduv\).
- Since \((ab)^w\equiv 1 \pmod m\),thus \(1\equiv ((ab)^{wu}=(a^u)^w(b^w)^u\equivb^{wu} \pmod m\), thus \(v\midwu\), so \(v\mid w\) since
\(\gcd(u,v)=1\). Similarly, \(u\mid w\), so \(uv\mid w\). - So \(\mathrm{ord}_m(ab) = w = uv =\mathrm{ord}_m(a)\cdot \mathrm{ord}_m(b)\).
- \(a^l\equiv 1 \pmod m \iff
\mathrm{ord}_m(a)\mid l\).
Primitive root
Def 3.5 Primitive root: Let \(m\geq 2\), \(g\) is called a primitive root modulo \(m\) if \[\mathrm{ord}_m(g)=\varphi(m)\] I.e. \(g\) is a generator of the multiplicative cyclic group \(\mathbb{Z}_m^*\).
Thm 3.6: Let \(g\) be a primitive root modulo \(m\), then
- \(\mathbb{Z}_m^*=\langle\bar{g}\rangle=\{\bar{1},\bar{g},\bar{g}^2,\cdots,\bar{g}^{\varphi(m)-1}\}\) is a cyclic group.
- 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- 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 impossiblesince \(0<j-i<\varphi(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
- \(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\) hascanonical factorization \[p-1=\prod_{i=1}^kp_i^{e_i}\] with \(e_i\geq 1\)and \(p_i\in \mathbb{P}\) are pairwisedistinct. 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 rootmodulo \(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\equiv0 \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\) hasat 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}}\equiv1 \pmod p\), thus \(g_i\) is aroot of \(x^{p_i^{e_i-1}}-1\), which isa contradiction, so \(r=e_i\),i.e. \(\mathrm{ord}_p(g_i)=p_i^{e_i}\).
- Since \(g_i\) is a root of
- Thus,
\(\mathrm{ord}_p(g)=\mathrm{ord}_p(\prod_{i=1}^kg_i)=\prod_{i=1}^k \mathrm{ord}_p(g_i)=\prod_{i=1}^kp_i^{e_i}=p-1\), so \(g\) is aprimitive 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\).
- Consider the set \(S=\{\frac{1}{n},\frac{2}{n}, \cdots, \frac{n}{n}\}\), obviously
- Claim that \(|\pi(d)| =\varphi(d)\) for all \(d\midp-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 distinctmodulo \(p\).
- Since \(a^d \equiv 1 \pmod p\),each element in \(S\) is a root of\(x^d - 1 \equiv 0 \pmod p\). And byFact 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\midp-1\).
- In particular, \(|\pi(p-1)| = \varphi(p-1)> 0\), so there exists a primitive root modulo
\(p\).
- Recap: A field \(F\) is a commutative ring with identity in
which every nonzero element is invertible.
Algorithm 3.8: Find all primitive roots modulo \(p\) for odd prime \(p\in \mathbb{P}\).
- Factor \(\varphi(p)=p-1\) into its prime factorization \(\prod_{i=1}^k p_i^{e_i}\).
- 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\).
- 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\).
- Find all primitive roots:
- For each \(1\leq l\leq \varphi(p)\) with \(\gcd(\varphi(p),l)=1\), \(g^l\) is a primitive root modulo \(p\).
- Thus, all \(\varphi(\varphi(p))\) primitive roots modulo \(p\) are \(G = \{g^l: 1\leq l\leq \varphi(p), \gcd(\varphi(p),l)=1\} = \{g^l \in \mathbb{Z}_p^* \mid l \in \mathbb{Z}_{p-1}^*\}\).
▶Table of primitive roots\(p\) Primitive roots modulo \(p\) 2 1 3 2 5 2, 3 7 3, 5 11 2, 6, 7, 8 13 2, 6, 7, 11 17 3, 5, 6, 7, 10, 11, 12, 14 19 2, 3, 10, 13, 14, 15, 16, 17 Thm 3.9: There exists primitive root modulo \(p^k\) for odd prime \(p\) and \(k\geq 1\), and there exists primitive root modulo \(2^k\) for \(k=1,2\).
▶ProofLet \(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)\).
- Due to Thm 3.4(1),
- 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\).
- Since \(g+p\equiv g \pmod p\), thus
- 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\).
- Claim that \(\mathrm{ord}_{p}(g) \mid\mathrm{ord}_{p^2}(g) \mid \varphi(p^2)\), so
- If
- 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 acontradiction since \(\mathrm{ord}_{p^2}(g_1)=p(p-1)\).
- If \(\gcd(a,p)\neq 1\), then
- Then we have: (Line 3 uses the fact that
\(p\) is odd prime, so for\(i\geq 2\), \(\binom{p^{k-2}}{i} (ap)^i \equiv 0 \pmod{p^k}\)) \[ \begin{aligned} g_1^{p^{k-2}(p-1)} &= (1 + ap)^{p^{k-2}} = \sum_{i=0}^{p^{k-2}}\binom{p^{k-2}}{i} (ap)^i \\ &= 1 + p^{k-2} ap + \binom{p^{k-2}}{2} (ap)^2 + \cdots \\ &\equiv 1 + ap^{k-1} \pmod{p^k} \\ &\not\equiv 1 \pmod{p^k} \end{aligned} \]
- 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\)
- 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\).
- 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
Thm 3.10: There exists primitive root modulo \(2\cdot p^k\) for odd prime \(p\) and \(k\geq 1\).
▶ProofLet \(g\) be a primitive root modulo\(p^k\)
- Case 1: \(g\) isodd, claim that
\(\mathrm{ord}_{2p^k}(g)=\varphi(2p^k)\): - Since \(g^l\equiv 1 \pmod{2p^k} \impliesg^l\equiv 1 \pmod{p^k}\), we have
\(\mathrm{ord}_{p^k}(g) \mid\mathrm{ord}_{2p^k}(g)\). - Since \(\gcd(g,p^k)=1\) and
\(g\) is odd, we have \(\gcd(g,2p^k)=1\), thus \(\mathrm{ord}_{2p^k}(g)\mid\varphi(2p^k)\). - Since \(\varphi(2p^k)=\varphi(2)\cdot\varphi(p^k)=\varphi(p^k) = \mathrm{ord}_{p^k}(g)\), thus
\(\mathrm{ord}_{2p^k}(g)=\varphi(2p^k)\), so\(g\) is a primitive root modulo \(2p^k\).
- Since \(g^l\equiv 1 \pmod{2p^k} \impliesg^l\equiv 1 \pmod{p^k}\), we have
- Case 2: \(g\) iseven, then \(g+p^k\) is a primitiveroot modulo \(p^k\) and is odd. By case1,
\(\mathrm{ord}_{2p^k}(g+p^k)=\varphi(2p^k)\).
- Case 1: \(g\) isodd, claim that
Thm 3.11: For \(m\geq 3\), there exists primitive root modulo \(m \iff m\) is of the form \(2,4,p^k,2p^k\) for odd prime \(p\) and \(k\geq 1\).
▶Proof- \(\implies\): Assume that
\(m\) has the standard factorization \(m=\prod_{i=1}^r p_i^{e_i}\) with \(e_i\geq 1\), then \(\varphi(m) = \prod_{i=1}^rp_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\leqi<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^ap^b\) for some \(a,b\geq 0\) and\(p\in \mathbb{P}\) is odd. - Case 1: \(b\geq1\), then \(\gcd(\varphi(2^a),\varphi(p^b))=\gcd(2^{a-1}, p^{b-1}(p-1))=1\), thus
\(a\leq 1\) since \(2\mid p-1\), so \(m=p^b\) or \(2p^b\). - Case 2: \(b=0\),\(m=2^a\),
\(\mathrm{ord}_{m}(g)=\varphi(m)=2^{a-1}\),so \(g^{2^{a-2}} \not\equiv 1\pmod{2^a}\). Since \(\gcd(g,2^a)=1\), thus \(g\) is odd. Let \(g=2k+1\) for some \(k\in \mathbb{Z}\), claim that \(a\leq 2\): Suppose \(a\geq 3\), then: \[ \begin{aligned} g^{2^{a-2}} &= (2k+1)^{2^{a-2}} = \sum_{i=0}^{2^{a-2}}\binom{2^{a-2}}{i} (2k)^i \\ &= 1 + 2^{a-1} k + \frac{2^{a-2} (2^{a-2}-1) (2k)^2}{2} +\frac{2^{a-2} (2^{a-2}-1) (2^{a-2}-2) (2k)^3}{6} + \cdots \\ &\equiv 1 + 2^{a-1} k + 2^{a-3} (2^{a-2}-1) (2k)^2 \pmod{2^a} \\ &= 1 + 2^{a-1}(k + k^2(2^{a-2}-1)) \pmod{2^a} \end{aligned} \] Since \(a\geq 3\), we have\((k+ k^2(2^{a-2}-1)) = k^2\cdot 2^{a-2} -k(k-1)\) is even, thus \(g^{2^{a-2}}\equiv 1 \pmod{2^a}\), which is a contradiction, so \(a\leq 2\).
- Case 1: \(b\geq1\), then \(\gcd(\varphi(2^a),\varphi(p^b))=\gcd(2^{a-1}, p^{b-1}(p-1))=1\), thus
- Let \(t = \mathrm{lcm}(\varphi(p_1^{e_1}),\varphi(p_2^{e_2}), \cdots, \varphi(p_r^{e_r}))\), thus
- \(\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\geq1\): Show in Thm 3.9 - \(m=2p^k\) for odd prime
\(p\) and \(k\geq1\): Show in Thm 3.10
- \(m=2\):
- \(\implies\): Assume that
Algorithm 3.12: Find all primitive roots modulo \(n\).
- 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\)
- 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\).
- \(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\).
- \(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\).
- \(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- \(G_1\) is the set of all primitiveroots modulo \(p^2\):
- If \(g_1\) is a primitive rootmodulo \(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 rootmodulo \(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.
- If \(g_1\) is not a primitive rootmodulo \(p\), then
- Suppose \(g_1=g+ap\) is a primitiveroot modulo \(p^2\), then we have
\[ \begin{aligned} g_1^{p-1} &= (g+ap)^{p-1} = \sum_{i=0}^{p-1} \binom{p-1}{i} g^i(ap)^{p-1-i} \\ &\equiv g^{p-1} + ap(p-1)g^{p-2} \pmod{p^2} \\ &\equiv g^{p-1} - ap g^{p-2} \pmod{p^2} \\ &\not\equiv 1 \pmod{p^2} \\ \end{aligned} \] Thus \[ apg^{p-1} \not\equiv g^p-g \pmod{p^2} \] Since \(g\) is a primitiveroot modulo \(p\), thus \(g^{p-1}\equiv 1 \pmod p\), so \(apg^{p-1} \equiv ap(1+kp) \equiv ap\pmod{p^2}\), thus \[ ap \not\equiv g^p-g \pmod{p^2} \iff a \not\equiv \frac{g^p-g}{p} \pmodp \] I.e. there is a unique \(a\) not satisfying the condition, so thereare \(p-1\) choices for \(a\) for each \(g\in G\). - So \(G_1\) has totally
\((p-1)\varphi(\varphi(p))\) distinctelements, 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 primitiveroots modulo \(p^2\).
- If \(g_1\) is a primitive rootmodulo \(p^2\), then
- \(G_2\) is the set of all primitiveroots modulo \(p^k\) for
\(k\geq 3\): - If \(g_2\) is a primitive rootmodulo \(p^k\), then
\(g_2\) is a primitive root modulo \(p^2\), so \(g_2 =g + ap^2\) for some \(g \inG_1\) and \(a \in\mathbb{Z}_{p^{k-2}}\). - Suppose \(g_2=g+ap^2\) is aprimitive root modulo \(p^k\), then wehave \[ \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 primitiveroot 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 formulaabove always holds. - So \(G_2\) has totally
\(|\mathbb{Z}_{p^{k-2}}||G_1|\) distinctelements. Since \(\varphi(\varphi(p^k))=p^{k-2}\varphi(\varphi(p^2))=|G_2|\),\(G_2\) is the set of all primitiveroots modulo \(p^k\) for all \(k\geq 3\).
- If \(g_2\) is a primitive rootmodulo \(p^k\), then
- \(G_3\) is the set of all primitiveroots 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 primitiveroots modulo \(2p^k\).
- Due to the proof of Thm 3.9, the primitive roots modulo
- 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.
Cor 3.13: For odd prime \(p\) and \(\forall k \geq 2\)
- \(\mathrm{ord}_{p^k}(g)=\varphi(p^k) \implies \mathrm{ord}_{p^{k+1}}(g)=\varphi(p^{k+1})\).
- \(\mathrm{ord}_{p^{k}}(g)=\varphi(p^{k}) \implies \mathrm{ord}_{p^{k-1}}(g)=\varphi(p^{k-1})\).
▶Proof- Since
\(\mathrm{ord}_{p^k}(g)=\varphi(p^k)\), thus\(g^{\varphi(p^{k-1})}\not\equiv 1\pmod{p^k}\) and \(g^{\varphi(p^{k-1})}\equiv 1\pmod{p^{k-1}}\), thus \(g^{\varphi(p^{k-1})}=1+ap^{k-1}\) with\(\gcd(a,p)=1\). Since \(p^{k-1}(p-1) = \mathrm{ord}_{p^k}(g) \mid\mathrm{ord}_{p^{k+1}}(g) \mid \varphi(p^{k+1})=p^{k}(p-1)\), wehave \(\mathrm{ord}_{p^{k+1}}(g)=p^{k-1}(p-1)\) or\(p^{k}(p-1)\). Since \[\begin{aligned}g^{p^{k-1}(p-1)} &= g^{\varphi(p^{k-1})p} \\&= (1+ap^{k-1})^{p} \\&\equiv 1 + ap^{k} \pmod{p^{k+1}} \\&\not\equiv 1 \pmod{p^{k+1}}\end{aligned}\] So \(\mathrm{ord}_{p^{k+1}}(g)\neq\varphi(p^{k})=p^{k-1}(p-1)\), thus \(\mathrm{ord}_{p^{k+1}}(g)=\varphi(p^{k+1})\). - Suppose
\(\mathrm{ord}_{p^{k-1}}(g)=d\), then \(d\mid \varphi(p^{k-1})\) and \(g^d\equiv 1 \pmod{p^{k-1}}\), thus \(g^d=1+ap^{k-1}\) for some \(a\in \mathbb{Z}\), then we have \[(g^d)^p = (1+ap^{k-1})^p \equiv 1 \pmod{p^{k}}\] So \(\mathrm{ord}_{p^{k}}(g) \midpd\), thus \(\varphi(p^{k})\midpd\), thus \(\varphi(p^{k-1})\midd\), so \(\mathrm{ord}_{p^{k-1}}(g)=d=\varphi(p^{k-1})\).
Discrete Logarithm
Def 3.14 Discrete Logarithm: Let \(g\) be a primitive root modulo \(m\), then discrete logarithm of \(a\) modulo \(m\) with \(\gcd(a,m)=1\) is defined to be an integer \(x\) satisfying \[ g^x \equiv a \pmod m \]
Denoted by \(x = \log_g a \pmod{\varphi(m)}\).
Thm 3.15 Properties of Discrete Logarithms: Let \(g\) be a primitive root modulo \(m\), then for \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), we have
- \(\log_g 1 \equiv 0 \pmod{\varphi(m)}\).
- \(\log_g g \equiv 1 \pmod{\varphi(m)}\).
- \(\log_g (ab) \equiv \log_g a + \log_g b \pmod{\varphi(m)}\).
- \(\log_g a^n \equiv n \cdot \log_g a \pmod{\varphi(m)}\).
Thm 3.16: Let \(g\) be a primitive root modulo \(m\), then \(\log_g a \equiv \log_g b \pmod{\varphi(m)} \iff a \equiv b \pmod m\).
▶Proof- \(\implies\): Since
\(g^{\log_g a} \equiv a \pmod m\) and \(g^{\log_g b} \equiv b \pmod m\), thus \(a \equiv g^{\log_g a} \equiv g^{\log_g b} \equiv b\pmod m\). - \(\impliedby\): Since
\(a \equiv b \pmod m\), thus \(g^{\log_g a} \equiv g^{\log_g b} \pmod m\),thus \(\mathrm{ord}_m(g)\mid (\log_g a -\log_g b)\), so \(\log_g a \equiv\log_g b \pmod{\varphi(m)}\).
- \(\implies\): Since
Thm 3.17: Let \(g\) be a primitive root modulo \(m\), then the equation \(x^b \equiv a \pmod m\) has a solution \(\iff \gcd(b, \varphi(m)) \mid \log_g a\).
▶Proof- \(\impliedby\): Since
\(\gcd(b, \varphi(m)) \mid \log_g a\), thus\(\exists u,v\in \mathbb{Z}\) s.t.\(ub + v\varphi(m) = \log_g a\), thus\(g^{ub} \equiv g^{ub + v\varphi(m)} \equivg^{\log_g a} \equiv a \pmod m\), so \(x=g^u\) is a solution to the equation. - \(\implies\): Since
\(g\) is a primitive root modulo \(m\), thus \(x=g^k\) and \(a=g^l\) for some \(1\leq k,l \leq \varphi(m)\), thus theequation is equivalent to \(g^{kb} \equiv g^l\pmod m\), thus \(kb \equiv l\pmod{\varphi(m)}\), let \(d=\gcd(b,\varphi(m))\), then \(k \equiv\frac{l}{d} \cdot \left(\frac{b}{d}\right)^{-1}\pmod{\frac{\varphi(m)}{d}}\), this requires \(\frac{l}{d} \in \mathbb{Z}\), so \(d \mid l\), i.e. \(\gcd(b, \varphi(m)) \mid \log_g a\). - Thus, the solution to the equation is \(x= g^{\frac{l}{d} \cdot \left(\frac{b}{d}\right)^{-1} + t\cdot\frac{\varphi(m)}{d}}\) for
\(t=0,1,\cdots,d-1\).
- \(\impliedby\): Since
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:
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.
- \(\implies\): Assume
\(a = QR, b = QR \implies ab = QR\).
\(a = QNR, b = QNR \implies ab = QR\).
\(a = QR, b = QNR \implies ab = QNR\).
The number of \(QR\) / \(QNR\) modulo \(p\) is \(\frac{p-1}{2}\).
▶Proof of 5- Since there are \(p-1\) non-zeroelements in \(\mathbb{Z}_p^*\),consider \(x\in\mathbb{Z}_p^*\), then\((p-x)^2 \equiv p^2 - 2px + x^2 \equiv x^2\pmod p\).
- Consider \(x^2\) for
\(x\in\{1, 2, \cdots, \frac{p-1}{2}\}\),claim that \(\forall 1\leq x < y \leq\frac{p-1}{2}, x^2 \not\equiv y^2 \pmod p\). - If \(x^2 \equiv y^2 \pmod p\), then\(y^2 - x^2 \equiv (y-x)(y+x) \equiv 0 \pmodp\), thus \(p \mid y-x\) or\(p \mid y+x\).
- Since \(1\leq x < y \leq\frac{p-1}{2}\), \(y+x <\frac{p-1}{2} + \frac{p-1}{2} = p-1 < p\) and
\(y-x < p\), thus \(p \nmid x+y\) and \(p \nmid x-y\), contradiction.
- Thus \(x^2\) for
\(x\in\{1, 2, \cdots, \frac{p-1}{2}\}\) are\(\frac{p-1}{2}\) distinct \(QR\) modulo \(p\), and the remaining \(\frac{p-1}{2}\) non-zero elements are \(QNR\) modulo \(p\).
Legendre Symbol
Def 4.3 Legendre Symbol: Let \(p\) be an odd prime, then for any \(a\in\mathbb{Z}\), the Legendre symbol \(\left(\frac{a}{p}\right)\) is defined as \[ \left(\frac{a}{p}\right) = \begin{cases} 0 ,& p \mid a \\ 1 ,& a \text{ is a QR modulo } p \\ -1 ,& a \text{ is a QNR modulo } p \end{cases} \]
Thm 4.4: The number of solutions to \(x^2 \equiv a \pmod p\) is \(1 + \left(\frac{a}{p}\right)\).
▶Proof- Case 1: \(p \mida\), then \(x^2 \equiv a \equiv 0 \pmodp\) has exactly one solution \(x \equiv0 \pmod p\). Thus \(1 = 1 +\left(\frac{a}{p}\right)\), done.
- Case 2: \(a\) is aQR 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 distinctsolutions to \(x^2 \equiv a \pmod p\).Thus \(2 = 1 +\left(\frac{a}{p}\right)\), done. - Case 3: \(a\) is aQNR modulo \(p\), then there are nosolutions 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- Case 1: \(p \mida\), 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. - Case 2: \(a\) is aQR modulo \(p\), then
\(a \equiv g^{2k} \pmod p\) for some \(k\in\mathbb{Z}\). Then \(\left(\frac{a}{p}\right) \equiv 1 \equiv(g^{2k})^{\frac{p-1}{2}} \equiv g^{(p-1)k} \pmod p\), done. - Case 3: \(a\) is aQNR 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.
- Case 1: \(p \mida\), then \(a=kp\) for some\(k\in\mathbb{Z}\). Then
Thm 4.6 Properties of Legendre Symbol: Let \(p\) be an odd prime, then for any \(a, m, n\in\mathbb{Z}\), we have
- \(\left(\frac{mn}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)\)
- \(\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}\)
- \(\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}\)
- \(\sum_{a\in\mathbb{Z}_p} \left(\frac{a}{p}\right) = 0\).
▶Proof- 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. - 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. - 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} \equiv2^{\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.
- 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.
- Since \(\left(\frac{0}{p}\right) =0\), \(\left(\frac{a}{p}\right) =1\) for \(\frac{p-1}{2}\)
\(QR\) and \(\left(\frac{a}{p}\right) = -1\) for \(\frac{p-1}{2}\) \(QNR\), we have \(\sum_{a\in\mathbb{Z}_p} \left(\frac{a}{p}\right) =0 + \frac{p-1}{2} \cdot 1 + \frac{p-1}{2} \cdot (-1) = 0\),done.
Jacobi Symbol
- Def 4.7 Jacobi Symbol: Let \(m\geq 3\) be an odd integer, assume that \(m\) has the standard factorization \(m = \prod_{i=1}^r p_i^{e_i}\) with \(p_i\) are distinct odd primes and \(e_i \geq 1\), then for any \(a\in\mathbb{Z}\), the Jacobi symbol \(\left(\frac{a}{m}\right)\) is defined as \[ \left(\frac{a}{m}\right) = \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i} \]
- Thm 4.8 Properties of Jacobi Symbol: Let \(m,n\geq 3\) be odd integers, then for any
\(a, b\in\mathbb{Z}\), we have
- \(\left(\frac{a}{m}\right) = 0 \iff \gcd(a, m) > 1\).
- \(\left(\frac{ab}{m}\right) = \left(\frac{a}{m}\right)\left(\frac{b}{m}\right)\).
- \(\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)\).
- \(\left(\frac{n^2}{m}\right) = \left(\frac{n}{m^2}\right) = 1 \iff \gcd(n, m) = 1\).
- \(\left(\frac{-1}{m}\right) = (-1)^{\frac{m-1}{2}}\).
- \(\left(\frac{2}{m}\right) = (-1)^{\frac{m^2-1}{8}}\).
▶Proof- 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.
- \(\implies\): Assume
- 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}\]
- 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}^rp_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}\] - Follows from (1), (2) and (3).
- Proof of 5:
- Method 1: Let \(m =\prod_{i=1}^r p_i^{e_i}\) be the standard factorization of
\(m\), then \[ \begin{aligned} \left(\frac{-1}{m}\right) &= \prod_{i=1}^r\left(\frac{-1}{p_i}\right)^{e_i} \\ &= \prod_{i=1}^r (-1)^{\frac{p_i-1}{2} e_i} \\ &= (-1)^{\sum_{i=1}^r \frac{p_i-1}{2} e_i} \overset{?}{=}(-1)^{\frac{m-1}{2}} \end{aligned} \] Claim that \(\sum_{i=1}^r\frac{p_i-1}{2} e_i \equiv \frac{m-1}{2} \pmod 2\). - Method 2: We can prove by induction on
\(m\): - If \(m=3\), done.
- Assume the claim holds for all odd integers
\(\leq m\), then consider \(m+2 = pk\) for some odd prime \(p\) and odd integer \(k\geq 1\). Then \[\begin{aligned}\left(\frac{-1}{m+2}\right) &= \left(\frac{-1}{pk}\right) =\left(\frac{-1}{p}\right)\left(\frac{-1}{k}\right) \\&= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{k-1}{2}} \\&= (-1)^{\frac{p-1}{2} + \frac{k-1}{2}}\end{aligned}\] It is sufficient to prove \(\frac{p-1}{2} + \frac{k-1}{2} \equiv\frac{pk-1}{2} \pmod 2\). Let \(p = 2u+ 1\) and \(k = 2v + 1\), then\[\begin{aligned}&\frac{p-1}{2} + \frac{k-1}{2} - \frac{pk-1}{2} \\=& \frac{p+k-pk-1}{2} \\=& \frac{-(p-1)(k-1)}{2} \\=& -2uv \equiv 0 \pmod 2\end{aligned}\] Thus \(\frac{p-1}{2} + \frac{k-1}{2}\equiv \frac{pk-1}{2} \pmod 2\), done.
- Method 1: Let \(m =\prod_{i=1}^r p_i^{e_i}\) be the standard factorization of
- Similar to (5), we can prove by induction on
\(m\): - If \(m=3\), done.
- Assume the claim holds for all odd integers
\(\leq m\), then consider \(m+2 = pk\) for some odd prime \(p\) and odd integer \(k\geq 1\). Then \[\begin{aligned}\left(\frac{2}{m+2}\right) &= \left(\frac{2}{pk}\right) =\left(\frac{2}{p}\right)\left(\frac{2}{k}\right) \\&= (-1)^{\frac{p^2-1}{8}} \cdot (-1)^{\frac{k^2-1}{8}} \\&= (-1)^{\frac{p^2-1}{8} + \frac{k^2-1}{8}}\end{aligned}\] It is sufficient to prove \(\frac{p^2-1}{8} + \frac{k^2-1}{8} \equiv\frac{(pk)^2-1}{8} \pmod 2\). Let \(p =2u + 1\) and \(k = 2v + 1\),then \[ \begin{aligned} &\frac{p^2-1}{8} + \frac{k^2-1}{8} - \frac{(pk)^2-1}{8} \\ =& \frac{p^2+k^2-(pk)^2-1}{8} \\ =& \frac{-(p^2-1)(k^2-1)}{8} \\ =& \frac{-(4u(u+1))(4v(v+1))}{8} \\ =& -2u(u+1)v(v+1) \equiv 0 \pmod 2 \end{aligned} \] Thus \(\frac{p^2-1}{8} +\frac{k^2-1}{8} \equiv \frac{(pk)^2-1}{8} \pmod 2\), done.
Quadratic Reciprocity
Thm 4.6 Law of Quadratic Reciprocity: Let \(m,n\) be odd integers with \(\gcd(m, n) = 1\), then \[ \left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}} \]
Equivalently, \(\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right) \cdot (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}\)
▶Example- 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\).
- 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
- 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 inwhich every non-zero element is a unit, i.e. every non-zero element hasa multiplicative inverse. In particular, a field is an integral domain.
- \(\mathbb{Q}\): the field ofrational numbers.
- \(\mathbb{R}\): the field of realnumbers.
- \(\mathbb{C}\): the field ofcomplex numbers.
- \(\mathbb{Z}_p\): the field ofintegers 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
- \(\deg(f + g) \leq \max(\deg(f), \deg(g))\).
- \(\deg(f \cdot g) = \deg(f) + \deg(g)\).
- \(\deg(a \cdot f) = \deg(f)\) if \(a \in F \setminus \{0\}\).
Def 5.4 Polynomial Ring: The polynomial ring over field \(F\) is defined as \[ F[x] = \left\{\sum_{i=0}^n a_i x^i : n \geq 0, a_i \in F\right\} \]
Indeed \((F[x], +, \cdot)\) forms a commutative ring with additive identity \(0\) and multiplicative identity \(1\). Furthermore, \(F[x]\) is an integral domain.
Thm 5.5: The unit group of \(F[x]\) is \(F^* = F \setminus \{0\}\).
- Notation: The unit group of a ring \(R\) is the set of all invertible elements in \(R\), denoted by \(R^*\).
▶Proof- Let \(f\in F[x]\) be a unit. Then\(\exists g \in F[x]\) s.t.
\(f \cdot g = 1\). By Thm 5.3, \(\deg(f) + \deg(g) = \deg(f\cdot g) = \deg(1) =0\). Thus \(\deg(f) = \deg(g) =0\), which means \(f, g \inF^*\). - 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]\).
- \(g\mid f \implies \forall h\in F[x]\setminus\{0\}, gh \mid fh\)
- \(g\mid f, f\mid h \implies g\mid h\)
- \(g\mid f, f\mid g \implies f = a g\) for some \(a \in F^*\)
- \(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\}\)
- If \(S\neq \emptyset\), \(S\) contains the smallest number (including \(-\infty\)).
- If \(S\) contains a non-negative integer, then \(S\) contains the smallest non-negative integer.
- 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 ofpolynomials 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 wehave \[ \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 \neq0) \\ g(x) &= g_m x^m + g_{m-1} x^{m-1} + \cdots + g_0 \quad (g_m \neq0) \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) \inS\) and \(\deg(u) < t\),contradicting the definition of
\(t\).
- 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 \neq0) \\ g(x) &= g_m x^m + g_{m-1} x^{m-1} + \cdots + g_0 \quad (g_m \neq0) \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) \inS\) and \(\deg(u) < t\),contradicting the definition of
- Uniqueness: Assume taht
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
- \(d \mid f, d \mid g\).
- \(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 \impliesab = 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-negativeinteger \(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 byits 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\).
- Let \(f=q\cdot d + r\) with
- Uniqueness: Assume that
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
- \(a(x)\) is monic \(\implies \gcd(af, ag) = a \cdot \gcd(f,g)\)
- \(\gcd\left(\frac{f}{\gcd(f,g)}, \frac{g}{\gcd(f,g)}\right) = 1\)
- \(\gcd(f_i,g)=1, i=1,2,\cdots,t \implies \gcd\left(\prod_{i=1}^t f_i, g\right)=1\)
- \(h\mid fg,~\gcd(h,g)=1 \implies h\mid f\)
- \(\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
- \(f \mid D, g \mid D\).
- \(\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 \impliesab = 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-negativeinteger \(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 divideit 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'\).
- If \(D' \in F[x]\) satisfies\(f \mid D', g \mid D'\), then\(\deg(D') \in S\), thus
- Uniqueness: Assume that
Thm 5.20 Properties of LCM: Let \(f, g, h, f_i \in F[x]\), then
\(a(x)\) is monic \(\implies \mathrm{lcm}(af, ag) = a \cdot \mathrm{lcm}(f,g)\)
\(\gcd(f,g)=1\) and \(f,g\) are monic \(\implies \mathrm{lcm}(f,g) = f \cdot g\)
\(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\).
- Let \(d = \gcd(f,g)\), then
Irreducible Polynomials
Def 5.21 Irreducible Polynomial: A non-constant polynomial \(f\) is called irreducible if \(f\) is only divisible by \(a\) or \(af\) for some \(a \in F^*\).
Thm 5.22: \(f\) is irreducible \(\iff (f\mid ab \implies f\mid a \text{ or } f\mid b)\).
▶Proof- \(\implies\):
- If \(f\mid a\), done.
- If \(f\nmid a\), then
\(\gcd(f,a) = 1\), thus \(f\mid b\), done.
- \(\impliedby\): Suppose
\(f\) were not irreducible, then \(f=g\cdot h\) with \(1\leq \deg(g), \deg(h) < \deg(f)\), thus\(f\mid g\cdot h \implies f\mid g \text{ or }f\mid h\), thus \(\deg(f) \leq\deg(g)\) or \(\deg(f) \leq\deg(h)\), contradiction.
- \(\implies\):
Lemma 5.23: \(\forall f \in F[x]\) with \(\deg(f) \geq 1, \exists p \in F[x]\) s.t. \(p\mid f\) and \(p\) is irreducible.
▶Proof- Consider the set \(S = \{\deg(u): u\mid f,\deg(u) \geq 1\}\), thus \(f \inS\), so \(S\neq\emptyset\). ByAxiom 5.8, \(S\) contains the smallestpositive 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 \cdotr\), then \(\deg(r) = \deg(p) - \deg(q)= 0\), thus \(r \in F^*\) and\(q=r^{-1} p\), thus \(p\) is irreducible.
- If \(q\in F^*\), then
- Consider the set \(S = \{\deg(u): u\mid f,\deg(u) \geq 1\}\), thus \(f \inS\), so \(S\neq\emptyset\). ByAxiom 5.8, \(S\) contains the smallestpositive integer \(t\), thus
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
- \[f = a \cdot \prod_{p} p^{v_p(f)}\]
- \[\gcd(f,g) = \prod_{p} p^{\min\{v_p(f), v_p(g)\}}\]
- \[\mathrm{lcm}(f,g) = \prod_{p} p^{\max\{v_p(f), v_p(g)\}}\]
Congruence
Congruence and Residue Classes
Def 5.27 Congruence: Let \(m \in F[x]\) with \(\deg(m) \geq 1\), then two polynomials \(a,b \in F[x]\) are said to be congruent modulo \(m\) if \[ m(x) \mid a(x) - b(x) \]
Denoted by \(a(x)\equiv b(x) \pmod{m(x)}\).
Thm 5.28 Properties of Congruence:
- \(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\)
- \(m>\gcd(m,c), ac\equiv bc \pmod m \implies a\equiv b \pmod{\frac{m}{\gcd(m,c)}}\)
- \(a\equiv b \pmod m\) and \(c\equiv d \pmod m \implies\)
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:
- \(\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\).
- \(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 \subseteqF[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 Lemma5.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- \(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\] - \(m(x)=x^2+1\), then
\(\deg(m) = 2\), thus \[F[x]/(m) = \{\bar{r}: \deg(r) < 2\} = \{\overline{a + bx}: a,b \inF\} \cong F^2\]
- \(m(x)=x\), then
Def 5.32 Addition and Multiplication: Define addition \(+\) and multiplication \(\cdot\) on \(F[x]/(m)\) by \[ \begin{aligned} \bar{r}_1 + \bar{r}_2 &= \overline{r_1 + r_2} \\ \bar{r}_1 \cdot \bar{r}_2 &= \overline{r_1 \cdot r_2} \end{aligned} \]
Thm 5.33: Under the above addition and multiplication, \(F[x]/(m)\) forms a commutative ring with the additive identity \(\bar{0}\) and the multiplicative identity \(\bar{1}\).
Def 5.34 Invertible Element: A polynomial \(a\in F[x]\) is called invertible modulo \(m\) if \(\exists b\in F[x]\) s.t. \[ a\cdot b \equiv 1 \pmod m \]
I.e. \(a\) is a unit in the commutative ring \(F[x]/(m)\), and \(b\) is called the inverse of \(a\) modulo \(m\), denoted by \(a^{-1}\).
Thm 5.35 Properties of Invertible: \(a\) is invertible modulo \(m \iff \gcd(a,m) = 1\).
▶Proof- \(\implies\): If
\(a\) is invertible modulo \(m\), then \(\exists b\in F[x]\) s.t. \(a\cdot b \equiv 1 \pmod m\), thus \(\exists u\in F[x]\) s.t. \(a\cdot b - 1 = u \cdot m\), thus \(a\cdot b - u \cdot m = 1\), thus \(\gcd(a,m) = 1\). - \(\impliedby\): By Bézout’sIdentity, \(\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\).
- \(\implies\): If
Def 5.36 Unit Group: The unit group of the ring \(F[x]/(m)\) is denoted by \[ (F[x]/(m))^* = \{\bar{r} \in F[x]/(m) : \gcd(r,m) = 1\} \]
Euler Function and Chinese Remainder Theorem
Def 5.37 Euler Function: The Euler function \(\Phi_p(m)\) is defined to be the number of invertible elements in the ring \(\mathbb{Z}_p[x]/(m)\) with \(\deg(m) \geq 1\), i.e. \[ \Phi_p(m) = |(\mathbb{Z}_p[x]/(m))^*| = \#\{\bar{r} \in \mathbb{Z}_p[x]/(m) : \gcd(r,m) = 1\} \]
- When \(\deg(\alpha) = 0\), we define \(\forall \alpha \in \mathbb{Z}_p^*, \Phi_p(\alpha) \triangleq 1\).
▶Example- To compute \(\Phi_2(x)\), considerthe 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\).
- 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]\)
- If \(\gcd(m,n) = 1\), then \[ \Phi_p(mn) = \Phi_p(m) \cdot \Phi_p(n) \]
- 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\).
- 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- If \(m\in \mathbb{Z}_p^*\), then\(\Phi_p(mn) = \Phi_p(n) = \Phi_p(m) \cdot\Phi_p(n)\) since \(\Phi_p(m) =1\). So we just need to consider the case when
\(\deg(m) \geq 1\) and \(\deg(n) \geq 1\): - Since \(\begin{cases}\Phi_p(mn) =|(\mathbb{Z}_p[x]/(mn))^*| \\ \Phi_p(m)\Phi_p(n) =|(\mathbb{Z}_p[x]/(m))^* \times (\mathbb{Z}_p[x]/(n))^*|\end{cases}\), it is sufficient to show that there is a bijectionbetween \((\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 ringisomorphism, thus \(\varphi\) is abijection, thus \(\Phi_p(mn) = \Phi_p(m) \cdot\Phi_p(n)\).
- Consider the set \[\begin{aligned}S &= (\mathbb{Z}_p[x]/(q^n)) \backslash (\mathbb{Z}_p[x]/(q^n))^* =\{\bar{r} \in \mathbb{Z}_p[x]/(q^n) : \gcd(r,q^n) \neq 1\} \\&= \{\overline{uq}: u \in \mathbb{Z}_p[x]\} \\&= \{\overline{uq}: \deg(uq) < \deg(q^n)\} \\&= \{\overline{uq}: \deg(u) < (n-1)\deg(q)\} \\&= \{\overline{\sum_{i=0}^{(n-1)\deg(q)-1} u_i x^i q}: u_i \in\mathbb{Z}_p\}\end{aligned}\] Thus \(|S| =p^{(n-1)\deg(q)}\), thus \[\begin{aligned}\Phi_p(q^n) &= |\mathbb{Z}_p[x]/(q^n)| - |S| \\&= p^{n\deg(q)} - p^{(n-1)\deg(q)} \\&= p^{n\deg(q)} \left(1 - \frac{1}{p^{\deg(q)}}\right)\end{aligned}\]
- Let \(m = \alpha \cdot \prod_{i=1}^tq_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}^tq_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} \]
- Let \(m = \alpha \cdot \prod_{i=1}^tq_i^{e_i}\) be the standard factorization of
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 canlabel 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\).
- Let \(l = \Phi_p(m)\), then we canlabel the elements of
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:
- \(a^l \equiv 1 \pmod m \implies \mathrm{ord}_m(a) \mid l\)
- \(\mathrm{ord}_m(a^t) = \frac{\mathrm{ord}_m(a)}{\gcd(\mathrm{ord}_m(a), t)}\)
- \(\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 elementmodulo \(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 elementsmodulo \(m\).
- Let \(g\) be a primitive elementmodulo \(m\), then
Thm 5.46: \(\mathbb{Z}_p[x]/(q)\) is a field \(\iff q\) is irreducible.
▶Proof- \(\impliedby\): Let
\(u\in \mathbb{Z}_p[x]/q\) with \(u \neq 0\). and \(\deg(u) < \deg(q)\), since \(q\) is irreducible, we have \(\gcd(u,q) = 1\), then by the Bézout’sIdentity, \(\exists a,b\in\mathbb{Z}_p[x]\) s.t. \(a\cdot u + b\cdot q = 1\), thus \(a\cdot u \equiv 1\pmod q\), thus \(u\) is a unitin \(\mathbb{Z}_p[x]/(q)\), thus \(\mathbb{Z}_p[x]/(q)\) is a field. - \(\implies\): Suppose not, thus\(q\) is reducible, then
\(\exists u,v \in \mathbb{Z}_p[x]\) with\(1 \leq \deg(u), \deg(v) <\deg(q)\) s.t. \(u\cdot v = q\),thus \(\bar{u} \cdot \bar{v} =\bar{0}\), thus \(\bar{u}\) is azero divisor in \(\mathbb{Z}_p[x]/(q)\), thus \(\mathbb{Z}_p[x]/(q)\) is not a field,contradiction.
- \(\impliedby\): Let
Thm 5.47: If \(q\in \mathbb{Z}_p[x]\) is irreducible, then there exists a primitive element modulo \(q\).
▶Proof structure- Factorize \(\Phi_p(q) = p^{\deg(q)} - 1 =\prod_{i=1}^t p_i^{e_i}\)
- Find \(g_i\) s.t.
\(\mathrm{ord}_q(g_i) = p_i^{e_i}\) for each\(i\). - Let \(g = \prod_{i=1}^t g_i\), thenit is a primitive element modulo
\(q\).
Thm 5.48: If \(q\in \mathbb{Z}_p[x]\) is irreducible and \(k \geq 2\), then there exists a primitive element modulo \(q^k \iff\)
- \(p\neq 2\), \(k=2\) and \(\deg(q) = 1\), or
- \(p=2\), \(2\leq k \leq 3\) and \(\deg(q) = 1\).
▶Proof- \(\impliedby\):
- \(k=2\): Let
\(g\in \mathbb{Z}_p[x]\) be a primitiveelement 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 primitiveelement 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 elementmodulo \(q^2\).
- \(k=3\): Let
\(g\in \mathbb{Z}_2[x]\) be a primitiveelement 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\).
- \(k=2\): Let
- \(\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\). Sincelinearly \(k-1\) grows faster than\(\lceil \log_2(k) \rceil\) and \(k=4\) not satisfies the inequality,contradiction, thus \(k \leq 3\).
- If \(d\geq 2\), then
- Thus we have:
- \(p\neq 2\),
\(k=2\) and \(\deg(q) = 1\), or - \(p=2\),
\(2\leq k \leq 3\) and \(\deg(q) = 1\).
- \(p\neq 2\),
- If \(p\neq 2\), then
Thm 5.49: Let \(m(x) \in \mathbb{Z}_p[x]\) have the standard factorization \(m(x) = \alpha \prod_{i=1}^n q_i^{e_i}(x)\). There exists a primitive element modulo \(m(x) \iff\)
- \(\prod_{i=1}^n \Phi_p(q_i^{e_i}) = \mathrm{lcm}\{\Phi_p(q_1^{e_1}), \dots, \Phi_p(q_n^{e_n})\}\). I.e. \(\forall 1 \leq i \leq j \leq n\), \(\gcd(\Phi_p(q_i^{e_i}), \Phi_p(q_j^{e_j})) = 1\).
- \(\forall 1 \leq i \leq n\), there exists a primitive element modulo \(q_i^{e_i}\). I.e. satisfies the condition in Thm 5.48.
▶Proof- By the Chinese Remainder Theorem for rings, we have the isomorphismof groups of units: \[(\mathbb{Z}_p[x]/(m(x)))^* \cong (\mathbb{Z}_p[x]/(q_1^{e_1}(x)))^*\times \dots \times (\mathbb{Z}_p[x]/(q_n^{e_n}(x)))^*\] Let \(G =(\mathbb{Z}_p[x]/(m(x)))^*\) and \(G_i= (\mathbb{Z}_p[x]/(q_i^{e_i}(x)))^*\).
- Then we have:
- \(\qquad\) A primitive elementmodulo \(m(x)\) exists
- \(\iff G\) is a cyclic group
- \(\iff G_1 \times \dots \timesG_n\) is cyclic
- \(\iff \forall 1 \leq i \leq n,G_i\) is cyclic and their orders
\(|G_i| = \Phi_p(q_i^{e_i})\) are pairwisecoprime - \(\iff \forall 1 \leq i \leq n\),there exists a primitive element modulo
\(q_i^{e_i}\) and \(\forall 1 \leq i \leq j \leq n\), \(\gcd(\Phi_p(q_i^{e_i}), \Phi_p(q_j^{e_j})) =1\).
Thm 5.50: There exists a primitive element modulo \(m(x) \iff\)
- \(p \neq 2\):
- \(m(x)\) is irreducible;
- \(m(x) = \alpha(x-\beta)^2\) for some \(\alpha\in \mathbb{Z}_p^*\), \(\beta \in \mathbb{Z}_p\);
- \(p = 2\): \(m(x) = \alpha(x-\beta)^e \prod q_i(x)\) for
some \(\alpha \in \mathbb{Z}_2^*\),
\(\beta \in \mathbb{Z}_2\), satisfying:
- \(0 \leq e \leq 3\);
- \(\forall 1 \leq i < j \leq n\), \(\gcd(\deg(q_i), \deg(q_j)) = 1\);
- \(x-\beta, q_i\) are distinct monic irreducible polynomials.
▶Proof- \(p\neq 2\):
- \(m(x)\) is irreducible: Proof byThm 5.46 and Thm 5.47.
- \(m(x) = \alpha(x-\beta)^2\): Proofby Thm 5.48.
- \(p=2\):
- \(m(x) = \alpha\):
\(\alpha = 1 \in \mathbb{Z}_2^*\), thus \(\Phi_2(m) = 1\), thus \(1\) is a primitive element modulo \(m\). - \(m(x) = \alpha(x-\beta)\): Proofby Thm 5.46 and Thm 5.47.
- \(m(x) = \alpha(x-\beta)^2\) or\(m(x) = \alpha(x-\beta)^3\): Proof byThm 5.48.
- \(m(x) = \alpha(x-\beta)^e \prodq_i(x)\): \(\deg(q_i)\) arepairwise coprime, since \(\gcd(2^a-1, 2^b-1) =2^{\gcd(a,b)}-1\), thus \(\Phi_2(q_i) =2^{\deg(q_i)} - 1\) are pairwise coprime. Since
\(e \leq 3\), thus \(\Phi_2((x-\beta)^e) = 2^{e-1} \in \{1, 2,4\}\) and is coprime to \(\Phi_2(q_i)\). Thus by Thm 5.49, thereexists a primitive element modulo \(m\).
- \(m(x) = \alpha\):
- \(p \neq 2\):
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\).
- \(\implies\): Write
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 thestatement holds. - Assume that the statement holds for any polynomial with degree lessthan \(n\).
- If \(f\) has no root, then thestatement holds.
- Otherwise, let \(r\) be a root of\(f\), then by Lemma 5.52, we have\(f(x) = (x-r)g(x)\) with
\(\deg(g) = n-1\), thus any root of \(f\) is either \(r\) or a root of \(g\), thus the number of distinct roots of\(f\) is at most \((n-1) + 1 = n\), thus the statementholds.
- We prove by induction on \(n\). If\(n=1\), then
Lagrange Interpolation
Thm 5.57: The set \(F[x]_{<n} = \{f \in F[x] : \deg(f) < n\}\) forms a vector space over \(F\) with \(\dim(F[x]_{<n}) = n\). And It has a canonical basis \(\{1, x, \cdots, x^{n-1}\}\) and a lagrange basis \(\{L_i(x) = \prod_{j \ne i}(x-a_j)\}_{i=1}^n\), where \(a_1, \cdots, a_n\) are \(n\) distinct elements of \(F\).
▶Proof of lagrange basis- It is sufficient to show that they are linearly independent. Suppose\(\sum_{i=1}^n \lambda_i L_i(x) = 0\)for some \(\lambda_i \in F\), then\(\forall k\), we have
\[ 0 = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(a_k - a_j) = \lambda_k\prod_{j \ne k}(a_k - a_j), \quad \prod_{j \ne k}(a_k - a_j) \neq 0 \] Since in the sum, when \(i \neqk\), the term \(\prod_{j \ne i}(a_k -a_j) = 0\), only when \(i = k\),the term \(\prod_{j \ne i}(a_k - a_j) =\prod_{j \ne k}(a_k - a_j) \neq 0\). Thus \(\forall k, \lambda_k = 0\), thus they arelinearly independent.
- It is sufficient to show that they are linearly independent. Suppose\(\sum_{i=1}^n \lambda_i L_i(x) = 0\)for some \(\lambda_i \in F\), then\(\forall k\), we have
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_ix^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 withdistinct \(a_i\), it is invertible,thus there exists a unique solution \(\lambda_i\), thus there exists a uniquepolynomial \(f\) with \(\deg(f) \le n-1\) s.t. \(f(a_i) = b_i\) for each \(i\).
▶Proof method 2- Let \(f(x) = \sum_{i=1}^n \lambda_i L_i(x)= \sum_{i=1}^n \lambda_i \prod_{j \ne i}(x-a_j)\) satisfy
\(f(a_i) = b_i\) for each \(i\). Then we have \[ b_k = f(a_k) = \sum_{i=1}^n \lambda_i \prod_{j \ne i}(a_k - a_j) =\lambda_k \prod_{j \ne k}(a_k - a_j) \] Thus \(\lambda_k =\frac{b_k}{\prod_{j \ne k}(a_k - a_j)}\), thus there exists aunique 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\).
- Let \(f(x) = \sum_{i=0}^{n-1} \lambda_ix^i\) satisfy \(f(a_i) = b_i\)for each \(i\). Then we have
Chapter 6. Finite fields
Fields
Def 6.1 Field: A field is a communicative ring with the multiplicative identity \(1\) in which every nonzero element is invertible.
- Examples: \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\)
- Cor:
- \(\mathbb{Z}/(p)\) is a field \(\iff p\) is a prime.
- \(F[x]/(q(x))\) is a field \(\iff q(x)\) is irreducible.
Def 6.2 Characteristic: The characteristic of a field \(F\) is defined by the smallest positive integer \(p\) s.t. \[ p \cdot 1 = \underbrace{1 + \cdots + 1}_p = 0 \]
Denote the characteristic of a field \(F\) by \(\mathrm{char}(F)\). If there is no such \(p\), then \(\mathrm{char}(F) = 0\).
Thm 6.3: The characteristic of a field \(F\) is either \(0\) or a prime.
▶Proof- Suppose \(\mathrm{char}(F) = m >0\) is a composite number. Then there exist
\(1 < a, b < m\) such that \(m = ab\). Then \[ 0 = m \cdot 1 = (ab) \cdot 1 = (a \cdot 1)(b \cdot 1) \implies a \cdot1 = 0 \text{ or } b \cdot 1 = 0 \] Thus contradicts the minimality of \(m\). Therefore, \(\mathrm{char}(F)\) must be a prime.
- Suppose \(\mathrm{char}(F) = m >0\) is a composite number. Then there exist
Def 6.4 Subfield and Field extension: Let \(E\) be a field and \(F \subseteq E\). If \(F\) is a field under the same addition and multiplication as \(E\), then \(E/F\) is called a field extension and \(F\) is called a subfield of \(E\).
Thm 6.5: If \(E/F\) is a field extension, then \(E\) can be viewed as a vector space over \(F\) with
- Vector addition:the addition of \(F\).
- Scalar multiplication:\(\forall \lambda \in F, \alpha \in F \implies \lambda \cdot \alpha\) is multiplication in \(F\).
Def 6.6 Prime field: The prime field of a field \(F\) is the smallest subfield of \(F\) containing \(1\).
Thm 6.7: The prime field of a field \(F\) is either \(\mathbb{Q}\) or \(\mathbb{Z}_p\) for a prime \(p\).
Def 6.8 Extension degree: If \(E/F\) is a field extension, then the extension degree of \(E/F\) is defined to be the dimension \(\dim_F E\), denoted by \([E : F]\). The extension \(E/F\) is called finite if \([E : F]\) is finite, otherwise \(E/F\) is called infinite.
▶Example\[[\mathbb{C},\mathbb{Q}] = +\infty, \quad [\mathbb{C},\mathbb{R}] = 2\]
Thm 6.9 Properties of Extension Degrees: Let \(E/F, F/K\) be field extension. Then
- \([E : K] = [E : F][F : K]\)
- \(E/K\) is a finite extension \(\iff\) Both \(E/F\) and \(F/K\) and finite extensions.
Def 6.10 Ring generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subring of \(E\) containing both \(F\) and \(\alpha\) is called the ring generated by \(\alpha\) over \(F\), denoted by \(F[\alpha]\). \[ F[\alpha] = \{f(\alpha) : f \in F[x]\} \]
Def 6.11 Field generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subfield of \(E\) containing both \(F\) and \(\alpha\) is called the field generated by \(\alpha\) over \(F\), denoted by \(F(\alpha)\). \[ F(\alpha) = \{\frac{f(\alpha)}{g(\alpha)} : f, g \in F[x], g(\alpha) \ne 0\} \]
Thm 6.12: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then \[ F(\theta) = F[\theta] = \left\{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\right\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\} \]
Furthermore, \([F(\theta) : F] = d\).
▶Proof- \(F[θ]=\{\sum_{i=0}^{d-1} a_i\theta^i :a_i \in F\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\}\):
- \(\forall f(\theta) \inF[\theta]\), since we can write \(f(x)= m(x)q(x) + r(x)\) with \(\deg(r) <\deg(m) = d\), thus \(f(\theta) = 0\cdot q(\theta) + r(\theta) = r(\theta) \in \{\sum_{i=0}^{d-1}a_i\theta^i : a_i \in F\}\), thus
\(F[\theta] \subseteq \{\sum_{i=0}^{d-1} a_i\theta^i: a_i \in F\} \subseteq \{f(\theta) : f \in F[x]\} =F[\theta]\). - Thus \(F[\theta] = \{\sum_{i=0}^{d-1}a_i\theta^i : a_i \in F\}\) =
\(\{f(\theta) : f \in F[x], \deg(f) \led-1\}\).
- \(\forall f(\theta) \inF[\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) = F[\theta]\):
- Obviously, \(F[\theta] \subseteqF(\theta)\). It is sufficient to show that
\(F[\theta]\) is a field. Consider nonzeroelement \(r(\theta) \inF[\theta]\). - \(\forall r(x) = \sum_{i=0}^{d-1}a_i\theta^i \neq 0\), we have not all
\(a_i\) are zero. Thus \(\gcd(r(x), m(x)) = 1\), then by Bézout’sidentity, there exist \(u,v \in F[x]\)s.t. \(u(x)r(x) + v(x)m(x) = 1\). Thus\(u(\theta)r(\theta) = 1\) since \(m(\theta) = 0\), thus \(r(\theta)\) is a unit. Therefore, \(F[\theta]\) is a field, thus \(F[\theta] = F(\theta)\).
- Obviously, \(F[\theta] \subseteqF(\theta)\). It is sufficient to show that
- \([F(\theta) : F] = d\): Since\(\{1, \theta, \ldots, \theta^{d-1}\}\)is a basis of \(F(\theta)\) over
\(F\), we have \([F(\theta) : F] = d\).
- \(F[θ]=\{\sum_{i=0}^{d-1} a_i\theta^i :a_i \in F\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\}\):
Thm 6.13: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then \[ F[x]/(m) \simeq F(\theta) = F[\theta] \]
▶Proof- The first isomorphism theorem: Let
\(R, S\) be rings and \(\pi : R \to S\) be a ring homomorphism.Then \(\ker(\pi) = \{r \in R : \pi(r) =0\}\) is an ideal of \(R\) and\(\mathrm{Im}(\pi) = \{\pi(r) : r \inR\}\) 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 ringhomomorphism and \(\ker(\pi) = \{f(x) \in F[x]: \pi(f) = f(\theta) = 0\} = \{f(x) \in F[x] : m(x) \mid f(x)\} = (m) =m(x)F[x]\). Thus by the first isomorphism theorem, we have
\[ F[x]/(m) \simeq \mathrm{Im}(\pi) = F[\theta] = F(\theta) \]
▶Example- \(x^2+1 \in \mathbb{R}[x]\) isirreducible, \(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}\] - \(x^2+x+1 \in \mathbb{Z}_2[x]\) isirreducible, since \(0,1\) are notroots. 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\).
- The first isomorphism theorem: Let
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
- \(\mathrm{char}(F)\) is a prime \(p\).
- \(\forall a, b \in F, (a+b)^p = a^p + b^p\).
- \(\forall a \in F, a^q = a\).
▶Proof- Since \(F\) is a field,
\(\mathrm{char}(F)\) is either \(0\) or a prime. If \(\mathrm{char}(F) = 0\), then the primefield of \(F\) is \(\mathbb{Q}\), which is infinite. Thus \(\mathrm{char}(F)\) must be a prime \(p\). - \(\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 \lep-1\).|
- 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
- \(q = p^n\) for some prime \(p\) and integer \(n \ge 1\).
- \(F^* = F \setminus \{0\}\) is a cyclic group of order \(p^n-1\).
▶Proof- Since \(\mathrm{char}(F) = p\) is aprime, 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\). - Since \(F^*\) is a finite subgroupof 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 inThm 6.16.
- \(\impliedby\): Let
\(m(x) \in \mathbb{Z}_p[x]\) be anirreducible 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 fieldwith \(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 inductionhypothesis, \(g(x)\) has all roots in\(\Omega\). Thus \(f(x)\) has all roots in \(\Omega\).
- If \(\deg(f) = 1\), then
- \(\impliedby\): Obvious.
- \(\implies\): Let
Thm 6.20: For any field \(F\), there exists an algebraically closed field \(\Omega\) containing \(F\).
Thm 6.21: Let \(p\) be a prime and let \(n \ge 1\), then there exists a unique finite field of \(p^n\) elements.
- Notation: We denote the unique finite field of \(q\) elements by \(\mathbb{F}_q\) or \(\mathrm{GF}_q\).
▶Proof- Existence: has been proved in Thm 6.17.
- Uniqueness: Let \(E,F\) be two finite fields with
\(q=p^n\) elements. Then \(\forall a \in E, a^q = a\), i.e. \(a\) is a root of \(x^q - x\), thus \(E = \{a : a^q = a\} \in \Omega\).Similarly, \(F = \{a : a^q = a\} \in\Omega\). Thus \(E = F\).
▶Example- \(x^3 + x + 1 \in \mathbb{Z}_2[x]\)and \(x^3 + x^2 + 1 \in\mathbb{Z}_2[x]\) are irreducible. Let
\(\alpha\) be a root of \(x^3 + x + 1\) and \(\beta\) be a root of \(x^3 + x^2 + 1\). Then \(\mathbb{Z}_2[x]/(x^3 + x + 1) \simeq\mathbb{Z}_2(\alpha)\) and \(\mathbb{Z}_2[x]/(x^3 + x^2 + 1) \simeq\mathbb{Z}_2(\beta)\) are two finite fields with \(8\) elements. By the uniqueness, we have\(\mathbb{Z}_2(\alpha) = \mathbb{Z}_2(\beta) =\mathbb{F}_8\).
Thm 6.22: \(\mathbb{F}_{p^n}\) is a field extension of \(\mathbb{F}_{p^k} \iff k \mid n\).
▶Proof- \(\implies\): Let
\(E = \mathbb{F}_{p^n}\) and \(F = \mathbb{F}_{p^k}\). Then \([E : F] = \frac{[E : \mathbb{Z}_p]}{[F :\mathbb{Z}_p]} = \frac{n}{k}\). Since \([E : F]\) is an integer, we have \(k \mid n\). - \(\impliedby\): Let
\(m = \frac{n}{k}\). Then \(\mathbb{F}_{p^n}\) is a field extension of\(\mathbb{F}_{p^k}\) with extensiondegree \(m\).
- \(\implies\): Let
Alg 6.23: Construction of finite fields of \(p^n\) elements:
- Find a monic irreducible polynomial \(m(x)\) with \(\deg(m) = n\) over \(\mathbb{Z}_p\).
- Find a root \(\theta\) of \(m(x)\) in an algebraically closed field \(\Omega\) containing \(\mathbb{Z}_p\).
- 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 irreduciblepolynomial 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\). Wechoose \(m(x) = x^4+x+1\) to construct\(\mathbb{F}_{16}\).
- The only irreducible polynomial of degree
- 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 rootof \(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 rootof \(m(x)\).
- \(m(\theta^4) = m(\theta + 1) =(\theta+1)^4 + (\theta+1) + 1 = \theta^4 + \theta + 1 = 0\). Thus\(\theta^4\) is a root of
\(m(x)\). - \(m(\theta^8) = m((\theta^4)^2) =m((\theta+1)^2) = m(\theta^2 + 1) = (\theta^2+1)^4 + (\theta^2 + 1) + 1= 0\). Thus \(\theta^8\) is aroot of \(m(x)\).
- Since \(\theta^{16} = \theta\), wehave \(m(\theta^{2^n}) = 0\) for all\(n \ge 0\). Thus
\(\{\theta, \theta^2, \theta^4 = \theta + 1,\theta^8 = \theta^2 + 1\}\) are all distinct roots of \(m(x)\).
Thm 6.24: Let \(F_q\) be a finite field of \(q=p^k\) elements, and let \(I_q(d)=\#\{g \in F_q[x] : \deg(g) = d,\text{ irr, monic}\}\) be the number of monic irreducible polynomials with \(\deg(g) = d\) over \(F_q\). Then
- Let \(n \ge 1 \in \mathbb{Z}\), then \[ x^{q^n} - x = \prod_{d \mid n} \prod_{g \in F_q[x], \text{ monic, irr} \atop \deg(g) = d} g(x) \]
- We have the following identity, which can help us to compute \(I_q(d)\): \[ q^n = \sum_{d \mid n} d \cdot I_q(d) \]
- By the Möbius inversion formula, we have \[ I_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) q^{\frac{n}{d}} \] where \(\mu(d)\) is the Möbius function defined by \[ \mu(d) = \begin{cases} 1 & d = 1 \\ (-1)^k & d = \prod_{i=1}^k p_i \text{ for distinct primes } p_i \\ 0 & \exists p \text{ s.t. } p^2 \mid d \end{cases} \]