跳转至

Number Theorem 3rd note

3.1 Modular arithmetic

Motivation: want a weaker version of equality (equivalence relation). For example, similar triangles, similar matrices, quotient spaces in linear algebra.

Def 3.1

A binary relation \(\sim\) on a set \(X\) is said to be equivalence relation, if it is reflexive, symmetric and transitive. That is , for all \(a,b,c \in X\), we have

  1. \(a\sim a\) (reflexive)

  2. \(a\sim b\text{ iff }b\sim a\) (symmetric)

  3. \(a\sim b\text{ and }b\sim c\), then \(a\sim c\) (transitive)

The equivalence class of \(a\) under \(\sim\) is defined as \(\lbrack a\rbrack = \left\{ x \in X~|~x\sim a \right\}\). \(a\) is called a representative of the class \(\lbrack a\rbrack\). Clearly \(\lbrack a\rbrack = \lbrack b\rbrack\) iff \(a\sim b\).

Def 3.2

Let \(n \in {\mathbb{N}}\) and \(a,b \in {\mathbb{Z}}\). We say \(a\) is congruent to \(b\operatorname{mod}(n)\), written \(a \equiv b\operatorname{mod}n\) if \(a\) and \(b\) leave the same remainder when divided by \(n\).

Clearly that is equi. to \(n|a - b\).

Lemma 3.3

Congruence modulo \(n\) is an equivalence relation.

We denote the set of equivalence classes(aka. congruence classes) modulo \(n\) by \({\mathbb{Z}}_{n}\).

Ex 3.4

\({\mathbb{Z}}_{4}\) has \(4\) elements \(\left\{ \lbrack 0\rbrack,\lbrack 1\rbrack,\lbrack 2\rbrack,\lbrack 3\rbrack \right\},\lbrack 3\rbrack = \left\{ 4k + 3|k \in {\mathbb{Z}} \right\}\)

We want to define addition, substraction1 and multiplication on the set \({\mathbb{Z}}_{n}\).

Here is a natural \(\lbrack a\rbrack + \lbrack b\rbrack = \lbrack a + b\rbrack,\lbrack a\rbrack - \lbrack b\rbrack = \lbrack a - b\rbrack,\lbrack a\rbrack\lbrack b\rbrack = \lbrack a \cdot b\rbrack\)

(Lemma)

The three modular operations are well-defined.

Ex 3.5

Find the residue of \(3^{2025}\operatorname{mod}7\).

\(\begin{aligned} & (3^{3})^{m} = (27)^{m} & \equiv & ( - 1)^{m}\operatorname{mod}7 \\ m\text{ is odd } && \equiv & - 1\operatorname{mod}7 \end{aligned}\)

Def 3.6 (Group)

A group is a set \(G\) with a binary operation \(( \cdot )\) satisfying

  • the Associativity: \((a \cdot b) \cdot c = a \cdot (b \cdot c)\)

  • \(\exists\) Identity \(e\): \(e \cdot a = a = a \cdot e\)

  • \(\exists\) Inverse \(a^{- 1}\): \(a^{- 1} \cdot a = a \cdot a^{- 1} = e\)

A group is called abelian if the operation is commutative.

Def 3.7 (Ring)

A ring is a set \(R\) with two binary operation \(( + , \cdot )\) satisfying

  • Additive structure: \((R, + )\) is an abelian group (with zero element \(0\) as identity);

  • Associativity: \(r \cdot (s \cdot t) = (r \cdot s) \cdot t\) for all \(r,s,t \in R\)

  • Distributivity: \(r \cdot (s + t) = rs + rt,(s + t) \cdot r = sr + tr\)

  • Identity: there \(1 \in R\) such that \(1 \cdot r = r \cdot 1 = r\).

Example

Matrix ring \(M_{n}\), polynomial ring.

A ring is called commutative if \(rs = sr\) for all \(r,s \in R\).

Theorem 3.8

\({\mathbb{Z}}_{n}\) under the modular addition and multiplication forms a ring.

Def 3.9

A set of integers containing one representative from each congruent class is called a complete set of residue \(\operatorname{mod}n\).

Ex 3.10

Here are two standard classes:

  1. Least non-negative residues \(\operatorname{mod}n\) is \(0,1,2,\ldots,n - 1\)

  2. Least absolute residues \(\operatorname{mod}n\) are \(\begin{cases} 0, \pm 1,\ldots, \pm \frac{n - 1}{2}\left( n\text{ odd} \right) \\ 0, \pm 1,\ldots, \pm \frac{n - 2}{2},\frac{n - 1}{2}\left( n\text{ even} \right) \end{cases}\)

Lemma 3.11

For \(f \in {\mathbb{Z}}\lbrack x\rbrack\), if \(\underset{\lbrack a\rbrack = \lbrack b\rbrack \in {\mathbb{Z}}_{n}}{a \equiv b\operatorname{mod}n}\), then \(\underset{\left\lbrack f(a) \right\rbrack = \left\lbrack f(b) \right\rbrack \in {\mathbb{Z}}_{n}}{f(a) \equiv f(b)\operatorname{mod}n}\).

Ex 3.12

Find a solution of \(x^{5} + x^{3} + x^{2} + 2 = 0\)

Consider \(x^{5} + x^{3} + x^{2} + 2 \equiv 0\operatorname{mod}4\) (no solution)

Conjecture

\(f(x) = 0\) has an integer solution iff \(f(x) \equiv 0\left( \operatorname{mod}n \right)\) has a solution for all \(n \in {\mathbb{N}}\).

Ex 3.13 (failure of Hasse Principle)

The polynomial \(f(x) = \left( x^{2} - 13 \right) \cdot \left( x^{2} - 17 \right) \cdot \left( x^{2} - 221 \right)\) has no integer root. But we will see later that for each integer \(n > 1\) there is a solution for \(f(x) \equiv 0\operatorname{mod}n\).

Ex 3.14

Euler found a remarkable polynomial \(f(x) = x^{2} + x + 41,(1,2,3,5,11,17,41)\) which is prime for each integer \(n\), \(- 41 < n < 40\).

(Conjecture the recurrence given by \(a_{n} = a_{n - 1} + \gcd(n,a_{n - 1})\) and \(a_{1} = 7\). Then the sequence of difference contains only \(1\) and primes.)2

Theorem 3.15

There is no non-constant polynomial \(f(x)\) with integer coefficients such that \(f(x)\) assume prime values at each integer \(x\).

Pf

Suppose \(f(x)\) is prime for each integer \(x\). Pick any \(a \in {\mathbb{Z}},f(a) = p\). Consider all \(b \equiv a\operatorname{mod}p\). Then by Lemma 3.11 \(f(b) \equiv f(a)\operatorname{mod}p\).\(f(b)\) as a prime \(\equiv p\left( \operatorname{mod}p \right) \Rightarrow f(b) = p \Rightarrow f - p\) has infinitely many zeros. \(↯\)

HW: 3.2, 3.4, 3.7(d), 3.21

Problem

  1. Prove that if \(a \equiv b\operatorname{mod}n\), then \(\gcd(a,n) = \gcd(b,n)\)

  2. Prove that the following:

    1. \(7|5^{2n} + 3 \cdot 2^{5n - 2}\)

    2. \(13|3^{n + 2} + 4^{2n + 1}\)

    3. \(27|2^{5n + 1} + 5^{n + 2}\)

  3. + If \(a \equiv b\operatorname{mod}n_{1}\) and \(a \equiv b\operatorname{mod}n_{2}\), prove that \(a \equiv b\operatorname{mod}n\) where \(n = \text{l.c.m}\left( n_{1},n_{2} \right)\)

    1. If \(a \equiv b\operatorname{mod}n_{1}\) and \(a \equiv c\operatorname{mod}n_{2}\), prove that \(b \equiv c\operatorname{mod}n\) where \(n = \text{g.c.d}\left( n_{1},n_{2} \right)\)

  4. If \(ca \equiv cb\operatorname{mod}n\), then \(a \equiv b\operatorname{mod}\frac{n}{d},d = \gcd(c,n)\)

  5. Prove that \(f\left( {\mathbb{Z}}\lbrack x\rbrack \right)\) has no integer solution if \(f(0)\) and \(f(1)\) are both odd.

3.3 Solving Linear Congruence3

Theorem 3.16

The linear congruence \(ax \equiv b\operatorname{mod}n\) has a solution iff \(d ≔ \gcd(a,n)\) divides \(b\). If \(d|b\), then general solution is given by \(x = x_{0}+\frac{(nt)}{d}\) where \(t \in {\mathbb{Z}}\). Moreover, the solutions have exactly \(d\) congruence classes \(\operatorname{mod}n\). The representative are given by \(t = 0,1,\ldots,d - 1\).

Pf

We only need to verify the moreover part. Note that \(x_{0}+\frac{(nt)}{d} \equiv x_{0}+\frac{(nt')}{d}\left( \operatorname{mod}n \right)\) iff \(n|\frac{n(t - t')}{d}\) iff \(d|t - t'\). So letting \(t\) ranging over \(0,1,\ldots,d - 1\) we get all congruence classes of solutions \(\operatorname{mod}n\).

Corollary 3.17

If \(\gcd(a,n) = 1\), then the linear congruence \(ax = b\operatorname{mod}n\) has a unique solution.

Rmk 3.18

This suggests that if \(\gcd(a,n) = 1\), then we can define division \(\frac{\lbrack b\rbrack}{\lbrack a\rbrack} \in {\mathbb{Z}}_{n}\) as the unique class \(\lbrack x\rbrack\) such that \(\lbrack a\rbrack\lbrack x\rbrack = \lbrack b\rbrack\). In particular, \({\mathbb{Z}}_{p}\backslash\left\{ \lbrack 0\rbrack \right\}\) forms a group.

Lemma 3.19

  1. If \(m\) divides \(a,b,n\) and let \((a',b',n') = (a,b,n)/m\), then \(ax \equiv n\operatorname{mod}n\text{ iff }a' x \equiv b'\operatorname{mod}n'\).

  2. If \(\gcd(a,n) = 1\), \(m \mid a,b\) and let \((a',b') = (a,b)/m\), then \(ax \equiv b\operatorname{mod}n\text{ iff }a' x \equiv b'\operatorname{mod}n\).

Pf

  1. easy.

  2. \(ax \equiv b\operatorname{mod}n \Rightarrow ax - b = qn \Rightarrow a' x - b' = \frac{qn}{m}\), so \(m|qn\). \(m\) as a factor of \(a\) must be coprime to \(n\), so \(m|q\). Therefore \(a' x \equiv b\operatorname{mod}n\)

    The converse if obvious.

Algorithm 3.20

Goal: using Lemma 3.19 to reduce \(a\) to \(1\).

Step 0: Calculate \(d = \gcd(a,n)\). If \(d \nmid b\), then no solution. Otherwise go to step 1.

Step 1: Now \(d\) divides \(a,b,n\), we use Lemma 3.19(a) to replace the original one by \(a' x \equiv b'\operatorname{mod}n'\) where \((a',b',n') = (a,b,n)/d\).

Step 2: Now we can use Lemma 3.19(b) to replace the previous one by a new congruence \(a'' x \equiv b''\operatorname{mod}n'\) where \((a'',b'') = (a',b')/\gcd(a',b')\). If \(a'' = 1\), then done; otherwise goes to step 3.

Step 3: Since \(\gcd(a'',b'') = 1\), we can replace \(b''\) by \(b'' + kn\) for appropriate \(k\) such that \(\gcd(a'',b'') > 1\). Then goes back to step 31 . This procedure must terminates until \(a'' = 1\).

Solve \(10x \equiv 6\operatorname{mod}14\)

Step 0: \(\gcd(10,14) = 2\)

Step 1: \(5x \equiv 3\operatorname{mod}7\)

Step 2,3: \(5x \equiv 10\operatorname{mod}7\)

\(x \equiv 2\operatorname{mod}7\)

  1. 原文如此，似为笔误 ↩↩

  2. 括号内部内容于3.15及其证明后写下 ↩

  3. 原文缺少3.2小节 ↩