Summary of Lecture 2

L02 – Equivalence, Congruence, and Residue Class

2026年3月6日

499.5K

Binary relation: from $A$ to $B$, $R\subseteq A\times B=\left\{(a,b):\,a\in A,\,b\in B\right\}$

Equivalence relation: a binary relation $R$ on a set $A$. $R\subseteq A\times A$

1. reflexive: $\forall a\in A,\,aRa$
2. symmetric: $\forall a,b\in A,\,aRb\implies bRa$
3. transitive: $\forall a,b,c\in A,\,aRb,bRc\implies aRc$

• equivalence class $[a]_R=\left\{b\in A:\,aRb\right\}$

Congruence: $R = \left\{(a,b) \in \mathbb{Z}^2 :\,n\mid(a-b)\right\}$

$n\in\mathbb{Z}^+,\,R_n=\left\{(a,b):\,\substack{R_n\subseteq\mathbb{Z}\times\mathbb{Z}\\a\in\mathbb{Z},\,b\in\mathbb{Z}\\n\mid(a-b)}\right\}$
❌ $aR_nb$
✅ $a\equiv b\pmod{n}$

• $\mathbf{a \equiv b \pmod{n}}:\,(a,b) \in R$
• $[a]_n = a + n\mathbb{Z} = \left\{a + nx :\,x \in \mathbb{Z}\right\}$
• $a = nq + r:\,\mathbf{a} \bmod\mathbf{n = r}$
• $[a]_n \cap [b]_n = \emptyset$ or $[a]_n = [b]_n$ (iff $a \equiv b \pmod{n}$)
• $\mathbb{Z}_n = {[0]_n, [1]_n, …, [n-1]_n}$

$\exists(q,r)$ s.t. $a=nq+r,\,0\leq r<n$
$[a]_n=[r]_n$
$[a]_n\in\mathbb{Z}_n = {[0]_n, [1]_n, …, [n-1]_n}$

Arithmetic operations over the set$\mathbb{Z}_n = \left\{[0]_n, [1]_n, …, [n-1]_n\right\}$
partition

• $[a]_n + [b]_n = [a+b]_n$
• $[a]_n – [b]_n = [a-b]_n$
• $[a]_n \cdot [b]_n = [a \cdot b]_n$//not an equality of sets

$\mathbb{Z}_n^*$

$[c]_n=[a]_n\left([b]_n\right)^{-1}$
$[b]_n=[a]_n\cdot [s]_n$
$[b]_n$ has an inverse $[b]_n[s]_n=[1]_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,\,[bs]_n=[1]_n,\,n\mid(bs-1)$;
  $\exists t, bs – 1 = nt,\,d=\gcd(b,n),\,\substack{d\mid bs,\,d\mid nt\\d\mid 1,\,d=1}$;
  $\gcd(b, n) = 1$
• If: $\exists s, t$ such that $bs + nt = 1;\,bs \equiv 1 \pmod{n}$
  $[bs]_n=[1]_n,\,[b]_n[s]_n=[1]_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}$

Euler’s Phi Function

QUESTION: How many elements are there in $\mathbb{Z}_{n}^{*}$

$\left|\mathbb{Z}_{n}^{*}\right|$ is the number of integers $b\in[n]\,\left([n]=\left\{1,2,\dots,n\right\}\right)$ such that $\gcd(b,n)=1$

DEFINITION (Euler’s Phi Function) $\phi(n)=|\mathbb{Z}_{n}^{*}|,\,\forall n \in \mathbb{Z}^{+}$.

• $\phi(n)$ is the number of integers $b \in[n]$ such that $\gcd(b,n)=1$
  //notation: $[n]=\left\{1,2,\dots,n\right\}$
• Gauss chose the symbol $\phi$ for Euler’s Phi function

THEOREM: Let $p$ be a prime. Then $\forall\mathrm{e}\in\mathbb{Z}^{+},\,\phi\left(p^{e}\right)=p^{e-1}(p-1)$.

• Let $x \in\left\{1,2,\dots,p^{e}\right\}$.
• $\gcd\left(x, p^{e}\right) \neq 1$ iff $p\mid x$
  $\gcd\left(x, p^{e}\right) \neq 1$ iff $x=p,2p,\dots,p^{e-1}\cdot p$
  • $\phi\left(p^{e}\right)=p^{e}-p^{e-1}=p^{e-1}(p-1)$

EXAMPLE: $\phi\left(3^{2}\right)=3(3-1)=6$

• $\mathbb{Z}_{9}^{*}=\left\{1,2,4,5,7,8\right\}$

EXAMPLE: $\phi(p)=p-1$

• $\mathbb{Z}_{p}^{*}=\left\{1,2, …, p-1\right\}$

QUESTION: What is the formula of $\phi(n)$ for a general integer $n$?

THEOREM: If $n=p_{1}^{e_{1}} \cdots p_{r}^{e_{r}}$ for distinct primes $p_{1},\dots,p_{r}$ and integers $e_{1}, …, e_{r}\geq 1$, then $\phi(n)=\phi\left(p_{1}^{e_{1}}\right) \cdots \phi\left(p_{r}^{e_{r}}\right)$. Hence, $\phi(n)=n\left(1-p_{1}^{-1}\right)\cdots\left(1-p_{r}^{-1}\right)$.

• There are many proofs. We will see in the future.
  • Principle of inclusion-exclusion
  • Chinese remainder theorem

COROLLARY: If $n=p q$ for two primes $p\neq q$, then $\phi(n)=(p-1)(q-1)$.

EXAMPLE: $\phi(10)=(2-1)(5-1)=4;\,n=10;\,p=2,\,q=5$

• $\mathbb{Z}_{10}^{*}=\left\{1,3,7,9\right\}$

Euler’s Theorem

THEOREM (Euler, 1760) Let $n\geq 1$ and $\alpha \in \mathbb{Z}_{n}^{*}$. Then $\alpha^{\phi(n)}=1$

$[ax]_n$

$\left[x_1\right]_n\cdot\left[x_2\right]_n\cdots\left[x_{\phi(n)}\right]_n=[a]_n\left[x_1\right]_n\cdot[a]_n\left[x_2\right]_n\cdots[a]_n\left[x_{\phi(n)}\right]_n$

• $\alpha^{\phi(n)},1$ are both residue classes modulo $n$
• Suppose that $\alpha=[a]_{n}$ for $a \in \mathbb{Z}$. Then $\alpha^{\phi(n)}=1$ is $\left([a]_{n}\right)^{\phi(n)}=[1]_{n}$
• How to prove?
  • Consider the map $f:\,\mathbb{Z}_{n}^{*}\to\mathbb{Z}_{n}^{*}\quad[x]_{n}\mapsto[a]_{n} \cdot[x]_{n}$
  • We show that $f$ is injective
    • $f\left([x]_{n}\right)=f\left([y]_{n}\right)$
    • $[a]_{n} \cdot[x]_{n}=[a]_{n} \cdot[y]_{n}$
    • $[a x]_{n}=[a y]_{n}$
    • $n\mid a(x-y)$
    • $n\mid(x-y)$, this is because $\gcd (n, a)=1$
      • $[x]_{n}=[y]_{n}$
  • Suppose that $\mathbb{Z}_{n}^{*}=\left\{\left[x_{1}\right]_{n},\dots,\left[x_{\phi(n)}\right]_{n}\right\}$
    • $f\left(\left[x_{1}\right]_{n}\right) \cdots f\left(\left[x_{\phi(n)}\right]_{n}\right)=\left[x_{1}\right]_{n} \cdots\left[x_{\phi(n)}\right]_{n}$
    • $\left[a x_{1}\right]_{n} \cdots\left[a x_{\phi(n)}\right]_{n}=\left[x_{1}\right]_{n} \cdots\left[x_{\phi(n)}\right]_{n}$
    • $\left[a^{\phi(n)} x_{1} \cdots x_{\phi(n)}\right]_{n}=\left[x_{1} \cdots x_{\phi(n)}\right]_{n}$
      • $n\mid\left(a^{\phi(n)}-1\right) x_{1} \cdots x_{\phi(n)}$
        • $n\mid\left(a^{\phi(n)}-1\right)$, this is because $\gcd\left(n,x_1\cdots x_{\phi(n)}\right)=1$
          • $\left[a^{\phi(n)}\right]_{n}=[1]_{n}$, i. e., $\left([a]_{n}\right)^{\phi(n)}=[1]_{n}$

Equivalent form: Let $n\geq 1$. Then $a^{\phi(n)} \equiv 1\pmod{n}$ for any integer a such that $\gcd(a, n)=1$

Fermat’s Little Theorem

EXAMPLE: Understand Euler’s theorem with $\mathbb{Z}_{10}^{*}=\{1,3,7,9\}$.

• $n=10,\,\phi(n)=4$,
• $1^{4} \equiv 1\pmod{10}\implies\left([1]_{10}\right)^{4}=[1]_{10}$
• $3^{4}=81 \equiv 1\pmod{10}\implies\left([3]_{10}\right)^{4}=[1]_{10}$
• $7^{4}=2401 \equiv 1\pmod{10}\implies\left([7]_{10}\right)^{4}=[1]_{10}$
• $9^{4}=6561 \equiv 1\pmod{10}\implies\left([9]_{10}\right)^{4}=[1]_{10}$
  • Consider the map $f:\,\mathbb{Z}_{10}^{*} \to \mathbb{Z}_{10}^{*} \quad[x]_{n} \mapsto[9]_{n} \cdot[x]_{n}$
  • $f\left([1]_{10}\right)=[9]_{10}\cdot [1]_{10}=[9]_{10}$;
    $f\left([3]_{10}\right)=[7]_{10}$;
    $f\left([7]_{10}\right)=[3]_{10}$,
    $f\left([9]_{10}\right)=[1]_{10}$
  • $f$ is injective
  • $f\left([1]_{10}\right) f\left([3]_{10}\right) f\left([7]_{10}\right) f\left([9]_{10}\right)=[9]_{10}[7]_{10}[3]_{10}[1]_{10}$

Fermat’s Little Theorem (Euler, 1736) If $p$ is a prime and $\alpha \in \mathbb{Z}_{p}$.Then $\alpha^{p}=\alpha$.

• By Euler’s theorem, $\alpha^{p-1}=1\,(\forall \alpha \neq[0]_{p})$
  • $\alpha^{p}=\alpha$

Equivalent form: If $p$ is a prime, then $a^{p} \equiv a\pmod{p}$ for any integer $a$.

Cryptography

• Confidentiality: The property that sensitive information is not disclosed to unauthorized individuals, entities, or processes.
  –FIPS 140-2

Private-Key Encryption

• $\mathbf{Gen},\mathbf{Enc},\mathbf{Dec}$: key generation, encryption, decryption
• $m,c,k$: plaintext (message), ciphertext, secret key
• $\mathcal{M},\mathcal{C}$: plaintext space, ciphertext space
• $\Pi=(\mathbf{Gen},\mathbf{Enc},\mathbf{Dec})+\mathcal{M},\,\left|\mathcal{M}\right|>1$
  • Correctness: $\mathbf{Dec}\left(k,\mathbf{Enc}(k, m)\right)=m$ for any $k,m$
  • Security: if $k$ is not known, it’s difficult to learn $m$ from $c$

Public-Key Encryption

• $\mathbf{Gen},\mathbf{Enc},\mathbf{Dec}$: key generation, encryption, decryption
• $m,c,pk,sk$: plaintext (message), ciphertext, public key, private key
• $\mathcal{M},\mathcal{C}$: plaintext space, ciphertext space
• $\Pi=(\mathbf{Gen},\mathbf{Enc},\mathbf{Dec})+\mathcal{M},\,\left|\mathcal{M}\right|>1$
  • Correctness: $\mathbf{Dec}\left(sk,\mathbf{Enc}(pk, m)\right)=m$ for any $pk,sk,m$
  • Security: if $sk$ is not known, it’s difficult to learn $m$ from $pk,c$

RSA

CONSTRUCTION: $\Pi=(\mathbf{Gen},\mathbf{Enc},\mathbf{Dec})+\mathcal{M}$, the message space is $\mathcal{M}=\left\{m:\,0 \leq m<N,\,\gcd(m, N)=1\right\}$

• $(pk, sk) \leftarrow\mathbf{Gen}\left(1^{n}\right)$
  • choose two $n$-bit primes $p\neq q$
  • $N=p q ;\,\phi(N)=(p-1)(q-1)$
  • choose $e,d$ s.t. $0\leq e,\,d<\phi(N)$,
    • $\gcd\left(e, \phi(N)\right)=1$
    • $d=e^{-1}\bmod{\phi(N)}$
  • output $pk=(N, e),\,sk=(N, d)$
• $c \leftarrow\mathbf{Enc}(pk, m)$:
  • output $c=m^e\bmod{N}$
    • $0\leq c<N$
• $m \leftarrow\mathbf{Dec}(sk, c)$:
  • output $m=c^d\bmod{N}$
    • $0\leq m<N$

? $\mathbf{Dec}(sk,\mathbf{Enc}(pk, m))=m$

• $e d \equiv 1\pmod{\phi(N)}$
• $\exists t \in \mathbb{Z}$ s.t. $e d=1+t \cdot \phi(N)$
• $\left[c^d\right]_N=\left([c]_N\right)^d$
  • $=\left(\left[m^e\right]_N\right)^d$
    $=\left(\left([m]_N\right)^e\right)^d$
    $=\left([m]_N\right)^{ed}$
    $=\left([m]_N\right)^{1+t\phi(N)}$
    $=[m]_N\cdot\left([m]_N\right)^{t\phi(N)}$
    $=[m]_N\cdot[1]_N$
    $=[m]_N$
• $m=c^d\bmod{n}$

RSA is correct!

1977, Rivest, Shamir and Adleman: A method for obtaining digital signatures and public-key cryptosystems. MIT/LCS/TM-82. (Turing Award 2002)