Summary of Lecture 1

L01 – Fundamental theorem of arithmetic, the well-ordering property, division algorithm, ideal,greatest common divisor, and Bézout’s theorem

2026年3月6日

93118.3K

Divide, Divisor, Multiple, Prime, Composite

• Fundamental Theorem of Arithmetic:$n=p_1^{e_1}\dots p_r^{e_r}$
• The Well-Ordering Property:$\emptyset\neq S\subseteq\mathbb{N}\implies\min{S}\in S$
• Division Algorithm:$a\in\mathbb{Z},\,b\in\mathbb{Z}^+,\,\exist!p,q,\text{ s.t. }a=bq+r,\,0\leq r<b$
• Ideal of $\mathbb{Z}$: A nonempty set $I\subseteq\mathbb{Z}$ such that $a,b\in I\implies a+b\in I$ and $a\in I,\,r\in\mathbb{Z}\implies ra\in I$
  • THEOREM:$I$ is an ideal of $\mathbb{Z}\iff I=d\mathbb{Z}$
• Sum of Ideals:$I_1+I_2=\set{x+y:\,x\in I_1,\,y\in I_2}$
  • THEOREM:$I_1,I_2$ are ideals of $\mathbb{Z}\implies I_1+I_2$ is an ideal of $\mathbb{Z}$
• Sum of ideals:$a\mathbb{Z}+b\mathbb{Z}=\gcd(a,b)\mathbb{Z}.\,\set{a,b}\neq 0$
• Greatest common divisor:$\gcd(a,b)=as+bt.$

FTA Proof

THEOREM: If $a,b,c\in\mathbb{Z},\,c\mid ab$ and $\gcd(c,a)=1$, then $c\mid b$.

• $\exists s,t\in\mathbb{Z}$ such that $c\cdot s+a\cdot t=1=\gcd(c,a)\implies b\cdot(c\cdot s+a\cdot t)=b\cdot 1$
  • $bcs+abt=b$
  • $c\mid(bcs),\,c\mid(abt)\implies c\mid b$

THEOREM: If $p$ is a prime and $p\mid ab$, then $p\mid a$ or $p\mid b$.

• $p\mid a$: done
• $p\nmid a\implies\gcd(p,a)=1$
  • $\gcd(p,a)=1\wedge p\mid ab\implies p\mid b$

FTA: proof of uniqueness

• Suppose that $n=p_1\dots p_r=q_1\dots q_s$, where $p_i,q_j$ are all primes
  • $p_1\mid n\implies p_1\mid q_1\dots q_s\implies p_1\mid q_j$ for some $j\implies p_1=q_j$
  • W.l.o.g., we suppose that $j=1$. Then $p_2\dots p_r=q_2\dots q_s$
  • The theorem is true by induction.

FTA Applications

THEOREM: Suppose that $a=p_1^{\alpha_1}\dots p_r^{\alpha_r},\,b=p_1^{\beta}\dots p_r^{\beta}$. Then $\gcd(a,b)=d$, where

• $d$ is a common divisor of $a,b$
• $d$ is largest among the common divisors
  • Suppose that $d’$ is a common divisor of $a,b$
  • $d’=p_1^{e_1}\dots p_r^{e_r}$
    • $d’\mid a\implies e_i\leq \alpha_i$ for all $i\in[r]$;
      $d’\mid b\implies e_i\leq \beta_i$ for all $i\in[r]$;
      • $e_i\leq\min\set{\alpha_i,\beta_i}$ for all $i\in[r]$

THEOREM (Euclid) There are infinitely many primes.

• Supposethereare only $n$ primes: $p_1,\dots,p_n$
• By FTA, $N=p_1\dots p_n+1$ must be a product of primes
• $\exists i\in[n]$ such that $p_i\mid N$
• But $p_i\nmid N$

Equivalence Relation

DEFINITION: Let $A,B$ be two sets. A binary relation from $A$ to $B$ is a subset $R\subseteq A\times B$. $\forall a\in A,\,b\in B,\,aRb\iff(a,b)\in R$

EXAMPLE:$R=\set{(a,a):\,a\in\mathbb{Z}}$ is a binary relation from $\mathbb{Z}$ to $\mathbb{Z}$

• $A=\mathbb{Z},\,B=\mathbb{Z},\,R=\set{(a,a):\,a\in\mathbb{Z}}\subseteq A\times B,\,\forall a,b\in\mathbb{Z},\,aRb\iff(a,b)\in R\iff a=b$

DEFINITION: Let $A$ be a set. An equivalence relation$R\subseteq A\times A$ on $A$ is a binary relation $R$ from $A$ to $A$ such that

• Reflective:$\forall a\in A,\,aRa$
• Symmetric:$\forall a,b\in A,\,aRb\implies bRa$
• Transitive:$\forall a,b,c\in A,\,aRb,\,bRc\iff aRc$

DEFINITION: The equivalence class of $a\in A$ is the set

Equivalence Class

THEOREM: Let $R$ be an equivalence relation on $A$. For any $a,b\in A,\,[a]_R=[b]_R$ if and only if $aRb$.

• $\implies:\,[a]_R=[b]_R\implies\begin{cases}a\in[b]_R\\b\in[a]_R\end{cases}\implies aRb$
• $\impliedby:\,aRb$
  • $\forall x\in[b]_R,\,bRx$;
    $\forall x\in[a]_R,\,aRx\implies xRb\implies x\in[b]_R$
  • $[b]_R\subseteq[a]_R$
  • Similarly, $[a]_R\subseteq[b]_R$

THEOREM: Let $R$ be an equivalence relation on $A$. For any $a,b\in A$, either $[a]_R\cap[b]_R=\emptyset$ or $[a]_R=[b]_R$.

• $[a]_R\cap[b]_R=\emptyset:\,x\in[a]_R\cap[b]_R$, done
• $[a]_R\cap[b]_R\neq\emptyset$
  • $\exists x\in[a]_R\cap[b]_R,\,\begin{cases}aRx\\bRx\end{cases}\implies aRb$, i.e., $[a]_R=[b]_R$

The equivalence classes under $R$ form a partition of $A$: a set $\set{A_1,A_2,\dots,A_n}$ of nonempty subsets of $A$ such that

• $A_i\cap A_j=\emptyset,\,\forall i\neq j$
• $\bigcup_{i=1}^n A_i=A$

Congruence

THEOREM: Let $n\in\mathbb{Z}^+$. Then $R=\set{(a,b)\in\mathbb{Z}^2:\,n\mid(a-b)}\subseteq\mathbb{Z}\times\mathbb{Z}$ is an equivalence relation on $\mathbb{Z}$ (from $\mathbb{Z}$ to $\mathbb{Z}$).

• $R$ is a binary relation from $\mathbb{Z}$ to $\mathbb{Z}$
  • Reflective: $\forall a\in\mathbb{Z},\,n\mid(a-a)\implies aRa$
  • Symmetric: $\forall a,b\in\mathbb{Z},\,aRb\implies n\mid(a-b)\implies b\mid(b-a)\implies bRa$
  • Transitive: $\forall a,b,c\in\mathbb{Z},\,\begin{cases}aRb\\bRc\end{cases}\implies\begin{cases}n\mid(a-b)\\n\mid(b-c)\end{cases}\implies n\mid(a-c)\implies aRc$

DEFINITION: Let $n\in\mathbb{Z}^+$ and $R=\set{(a,b)\in\mathbb{Z}^2:\,n\mid(a-b)}$.

• The notation $a\equiv b\pmod{n}$ means that $aRb$.
  • $a\equiv b\mod n$ is called a congruence
    • Read as: $a$ is congruent to $b$ modulo $n$
    • $n$ is called the modulus of the congruence
  • $a\not\equiv b\pmod{n}:\,(a,b)\notin R$, or equivalently $n\nmid(a-b)$
    • Read as: $a$ is not congruent to $b$ modulo $n$

Residue Class

DEFINITION: Let $a\in\mathbb{Z},\,n\in\mathbb{Z}^+$. We denote the equivalence class of $a$ under the equivalence relation $\mod n$ with $[a]_n$ and call it the residue class of $a\bmod n$.

• $[a]_n=\set{b\in\mathbb{Z}:\,a\equiv b\mod n}=\set{a+nx:\,x\in\mathbb{Z}}=a+n\mathbb{Z}$
  • any element of $[a]_n$ is a representative 代表元 of $[a]_n$

EXAMPLE:$[0]_6=\set{0,\pm 6,\pm 12,\dots}=\set{0+6x:\,x\in\mathbb{Z}}=6\mathbb{Z};\,[1]_6=\set{\dots,-11,-5,1,7,13,\dots};\,\dots$

THEOREM: Let $n \in \mathbb{Z}^+$. For any $a \in \mathbb{Z}$, there is a unique integer $r$ such that $0 \leq r < n$ and $a \equiv r \pmod{n}$. $[a]_n=[r]_n$

• Existence: by division algorithm, $\exists q, r \in \mathbb{Z}$ such that $0 \leq r < n,\,a = qn + r$
  • $a \equiv r \pmod{n}$
• Uniqueness: suppose that $0 \leq r’ < n$ and $a \equiv r’ \pmod{n}$
• $\left|r – r’\right| < n$ and $r \equiv r’ \pmod{n}$
  • $\left|r – r’\right| < n$ and $n \mid\left(r – r’\right)$
    • $r = r’$

COROLLARY: For $n \in \mathbb{Z}^+$, there are $n$ residue classes, i.e., $\set{[0]_n, [1]_n, \dots, [n-1]_n}$.

$\bmod$

DEFINITION: Let $a, n \in \mathbb{Z}$ and $n > 0$. Then there are unique integers $q, r$ such that $0 \leq r < n$ and $a = nq + r$.

• We define $a \bmod n$ as $r$.

DEFINITION: Let $\alpha \in \mathbb{R}$.

• $\lfloor \alpha \rfloor$: floor of $\alpha$, the largest integer $\leq\alpha$
• $\lceil \alpha \rceil$: ceiling of $\alpha$, the smallest integer $\geq \alpha$
  • If $a = nq + r$, then $q = \left\lfloor \frac{a}{n} \right\rfloor$ and $r = a – nq$

$\mathbb{Z}_n$

DEFINITION: Let $n$ be any positive integer. We define $\mathbb{Z}_n$ to be the set of all residue classes modulo $n$.

• $\mathbb{Z}_n = \set{[0]_n, [1]_n, \dots, [n-1]_n}$ 完全剩余系
  • $\mathbb{Z}_n = \set{0, 1, \dots, n-1}$;
• $\mathbb{Z}_n = \set{[1]_n, [2]_n, \dots, [n]_n}$
  • $\mathbb{Z}_n = \set{1, 2, \dots, n}$

EXAMPLE: Two representations of the set $\mathbb{Z}_6$

• $\mathbb{Z}_6 = \set{[0]_6, [1]_6, [2]_6, [3]_6, [4]_6, [5]_6}=\set{0, 1, 2, 3, 4, 5}$
• $\mathbb{Z}_6 = \set{[-3]_6, [-2]_6, [-1]_6, [0]_6, [1]_6, [2]_6}= \set{-3, -2, -1, 0, 1, 2}$

DEFINITION: Let $n \in \mathbb{Z}^+$. For all $[a]_n, [b]_n \in \mathbb{Z}_n$, define

• addition:$[a]_n + [b]_n = [a + b]_n$
• subtraction:$[a]_n – [b]_n = [a – b]_n$
• multiplication:$[a]_n \cdot [b]_n = [a \cdot b]_n$

Well-defined?$[a]_n = \left[a’\right]_n,\,[b]_n = \left[b’\right]_n \implies [a]_n \star [b]_n = \left[a’\right]_n \star \left[b’\right]_n,\,\star \in \set{+, -, \cdot}$?

• Yes.
• $[a]_n = \left[a’\right]_n \implies a \equiv a’ \pmod{n} \implies n \mid \left(a – a’\right) \implies \exists x$ such that $a – a’ = nx$
• $[b]_n = \left[b’\right]_n \implies b \equiv b’ \pmod{n} \implies n \mid \left(b – b’\right) \implies \exists y$ such that $b – b’ = ny$
  • $(a + b) – \left(a’ + b’\right) = nx + ny$
  • $(a – b) – \left(a’ – b’\right) = nx – ny$
  • $ab – a’b’ = a\left(b – b’\right) + b’\left(a – a’\right) = any + b’nx$
• $[a]_n \star [b]_n = \left[a’\right]_n \star \left[b’\right]_n$

$\mathbb{Z}_n^*$

DEFINITION: Let $n \in \mathbb{Z}^+$ and $[b]_n \in \mathbb{Z}_n$. The residue class $[s]_n \in \mathbb{Z}_n$ is called an inverse of $[b]_n$ if $[b]_n [s]_n = [1]_n$.

• The inverse of a residue class is unique (if exist). We denote $\left([b]_n\right)^{-1} = [s]_n$.
• division: If $[b]_n [s]_n = [1]_n$, define $\frac{[a]_n}{[b]_n} = [a]_n \cdot \left([b]_n\right)^{-1} = [a]_n \cdot [s]_n$

THEOREM: Let $n \in \mathbb{Z}^+$. $[b]_n \in \mathbb{Z}_n$ has an inverse if and only if $\gcd(b, n) = 1$.

• Only if: $\exists s$ such that $[b]_n [s]_n \equiv [1]_n;\,\exists t, bs – 1 = nt;\,\gcd(b, n) = 1$
• If: $\exists s, t$ such that $bs + nt = 1;\,bs \equiv 1 \pmod{n}$

DEFINITION: Let $n \in \mathbb{Z}^+$. Define $\mathbb{Z}_n^* = \set{[b]_n \in \mathbb{Z}_n :\,\gcd(b, n) = 1}$.

• If $n$ is prime, then $\mathbb{Z}_n^* = \set{1, 2, \dots, n-1}$
• If $n$ is composite, then $\mathbb{Z}_n^* \subset \mathbb{Z}_n$

EXAMPLE:$\mathbb{Z}_5^* = \set{1, 2, 3, 4};\,\mathbb{Z}_6^* = \set{1, 5};\,\mathbb{Z}_8^* = \set{1, 3, 5, 7}$