初等数论学习笔记（持续更新）

这是一个初等数论学习笔记，使用的教材为Gareth A.Jones and J.Mary Jones的 Elementary Number Theory。不是全按照书本上的讲法来的，目前只学到第八章，，，

发布日志

2025-01-17

整理至 THm 5.3，美化页面

2025-01-15

发布文章。（整理至 THm 5.1）

NOTE

• 小标号以fjr老师的lecture为准，有跳跃的地方是因为觉得不是很重要所以没有记，可以忽略，，， 大标号按书本划分。
  由于是按照我的手写笔记整理的，有的地方思维会有些跳跃。 我就这样/bushi
• 大部分未给出证明的地方都是我认为很好理解且显然的；所有仅给出证明links的都是不需要掌握的，感兴趣了解即可。
• 现在正在整理第四章，，，，，，

1. Divisibility

1.1 Divisors

THm 1.1

If $a,b\in \mathbb{Z}$ with $b>0$, then there is a unique part of integers $q$ and $r$ such that $a=qb+r$ and $0\leq q <b$ .

pf. The set $S=\{ a-nb \mid n \in \mathbb{Z} \}$ contains some non-neg integers so $S \cap \mathbb{N}$ has at least one element,for some $q \in \mathbb{Z}$ , say $r=a-qb \geq 0$ . ■

Def 1.3

If $r=0$ , we say that $b$ divides $a$ , denoted by $b \mid a$ . In the case, we also say that $b$ is a factor of $a$ or $a$ is a multiple of $b$ . And if b dose not divide a , we write $b \nmid a$ .

Ex 1.4

Every integer divides $0$ ; if $n$ is a square ,then $n \equiv 0 \; \text{or} \; 1 ( \text{mod} \; 4)$ .

Prop 1.5

If $c$ is divisible by $a_1, \dots , a_n$ , then $c$ is divisible by an integer linear combination of $\{ a_1, a_2, \dots , a_n \}$ .

Def 1.6

If $d \mid a$ and $d \mid b$ , then $d$ is a common divisor of $a$ and $b$ , All common divosors are bounded. There is a biggest common divisor of $a$ and $b$ denoted by $\text{gcd} (a,b)$ .

Lemma 1.7 (Euclid's Algorithm)

If $a=q_1 b+r_1$ , then $\text{gcd} (a,b)= \text{gcd} (b,r_1)$ , write $r_1=a-q_1 b$ , using Prop 1.5 , we can repeat this operation and reduce the number $r_n$ to $0$ . And $r_{n-1}$ is the least common divisor of $a$ and $b$ . We have $d= \text{gcd} (a,b) = r_{n-1}$ .

Remark 1.10: The result extends to any Euclidean ring .

1.2 Bezout's identity

THm 1.11

If $a,b \in \mathbb{Z}$ , not both $0$ , then there exist integers $u$ and $v$ , s. t. $\text{gcd} (a,b) = au + bv$ .

pf. using Lemma 1.7 and induction. Start from $\text{gcd} (a,b)= r_{n-1} =r_{n-3} - q_{n-1} r_{n-2}= \dots$ ■

Ex 1.11

Extend the result to k numbers.

$\text{gcd} (a_1 , a_2 , \dots , a_k ) =g_1 a_1+g_2 a_2 + \dots +g_k a_k. (g_i \in \mathbb{R}^1)$

Corollary 1.13

Suppose that $\text{gcd} (a,b)=d$ , then an integer $e$ is of the form $ax+by$ for some $x \in \mathbb{Z}$ , iff $c$ is a multiple of $d$ . In particular, $d$ is the least positive integer of such form.

pf. Because $\text{gcd} (a,b) \mid a$ and $\text{gcd} (a,b) \mid b$ . So $\text{gcd} (a,b) \mid ax+by$ . ■

Def 1.14

Two integers $a$ and $b$ are coprime (or relatively prime) if $\text{gcd} (a,b) = 1$ . More generally a set of integers are coprime if $\text{gcd} (a_1 ,a_2 , \dots ,a_k)=1$ . (If the integers are mutually coprime , then they are collectively coprime)

Corollary 1.15

$\text{gcd} (a,b) =1$ iff $ax+by=1$ ,for some $x$ and $y$ .

Corollary 1.16

For $a$ , $b$ are coprime, we have that if $a \mid c$ and $b \mid c$ then $ab \mid c$ ; if $a \mid bc$ , then $a \mid c$ .

1.3 Least common multiples

Def 1.17

If $a \mid c$ and $b \mid c$ , we say $c$ is a common multiple of $a$ and $b$ . The set of all positive common multiple of $a \neq 0$ and $b \neq 0$ is clearly non-empty and bounded below. So there is a unique least common multiple of $a$ and $b$ , denoted by $\text{lcm} (a,b)$ .

THm 1.18

Lets $d=\text{gcd} (a,b) \text{ and } m= \text{lcm} (a,b)$ , then $ab=dm$ .

1.4 Linear Diophantine equations

THm 1.19 (Application of the Diophantine Equations)

Let $a,b,c \in \mathbb{Z}$ with $a$ , $b$ are not both $0$ and let $d=\text{gcd} (a,b)$ . Then the equation $ax+by=c$ has an integer solution $x$ , $y$ iff $c$ is a multiple of $d$ .
In this case, there are infinitely many solution given by $\left\{ \begin{aligned} x = x_0 + \frac{bn}{d} \\ y = y_0 - \frac{an}{d} \end{aligned} \right.$ where $b \in \mathbb{Z}$ and $x_0$ , $y_0$ is any particular solution.

pf. The existence of solution is guaranteed by Corollary 1.13 . The infinite solutions are easy to verify. ■

2. Prime Numbers

2.1 Prime numbers and prime-power factorisations

Def 2.1

We call a positive integer a prime iff its only positive divisor is itself. (the opposite is called coprime)

Lemma 2.3

If p is a prime and $p \mid a_1a_2 \dots a_k$ , then $p$ must divide some $a_i$ .

Remark: Such a polynomial $f(x)$ is reducible if $f(x)=g(x)h(x)$ , where $g(x)$ and $h(x)$ are non-constant polynomials with integer coefficients; otherwise, $f(x)$ is irreducible.

2.2 Distribution of primes

THm 2.4 (Fundamental Theorem of Arithmetic)

A number can be factored uniquely as a product of prime powers.

pf. We prove this by contradiction. Suppose the factorization is not unique. Let $n = p_1 p_2 \dots p_j = q_1 q_2 \dots q_k$ be the smallest such composite number that can be factored in two different ways.

By Lemma 2.3 , we know that if a prime $p$ divides a product of numbers, it must divide at least one of the numbers in the product. Therefore, if $n = p_1 p_2 \dots p_j = q_1 q_2 \dots q_k$ , there must be some overlap between the prime factors in these two factorizations.

Without loss of generality, suppose that $p_1$ divides one of the $q_i$ 's. Then, by Lemma 2.3 , we know that $p_1$ must divide some $q_i$ , and we can continue this process recursively to break down $n$ into smaller numbers that must still obey the uniqueness of factorization. However, this contradicts the assumption that $n$ was the smallest number with two different factorizations.

Thus, the assumption that the factorization of $n$ is not unique leads to a contradiction, and we conclude that the factorization must be unique. ■

Remark: If $p$ is prime, we write $p^e \parallel n$ to indicate that $p^e$ is the highest power of $p$ dividing $n$ , that is, $p^e$ divides $n$ but $p^{e+1}$ does not. We have that if $p^e \parallel a$ and $p^f \parallel b$ then $p^{e+f} \parallel ab$ , $p^{e-f} \parallel \frac{a}{b}$ , $p^{me} \parallel a^m$ .

Lemma 2.5

Suppose that $a_1,a_2, \dots ,a_r$ are mutually coprime positive integers. If $a_1a_2 \dots a_r$ is an m-th power, then so is each $a_i$ .

pf. Assume that $a_1, a_2, \dots , a_r$ are mutually coprime positive integers, and that their product $a_1 a_2 \dots a_r$ is an m-th power. That is, there exists an integer $k$ such that: $a_1 a_2 \dots a_r = k^m$

We need to show that each $a_i$ is also an m-th power.

Since $a_1, a_2, \dots , a_r$ are mutually coprime, no pair $a_i$ and $a_j$ share any common prime divisor. Therefore, for any prime $p$ that divides $a_i$ , $p$ cannot divide any other $a_j$ for $j \neq i$ .

Now, consider the prime factorization of $a_1 a_2 \dots a_r$ . Since $a_1 a_2 \dots a_r = k^m$ , every prime factor of $a_1 a_2 \dots a_r$ must appear to a power that is divisible by $m$. Specifically, if a prime $p$ divides $a_i$ , the exponent of $p$ in the prime factorization of $a_1 a_2 \dots a_r$ must be divisible by $m$ . Since $a_i$ is coprime with all other $a_j$ 's, the exponent of $p$ in the prime factorization of $a_i$ must also be divisible by $m$ . Thus, each $a_i$ must be an m-th power. ■

Corollary 2.6

If a positive integer $m$ is not a perfect square, then $\sqrt{m}$ is irrational.

pf. We use contradiction to prove it, assume that $m$ is rational, then we have $\sqrt{m} = \frac{a}{b}$ , $m= \frac{a^2}{b^2}$ , where $a=p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ and $b=p_1^{f_1} p_2^{f_2} \dots p_k^{f_k}$ . So $m=( \frac{ p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} }{ p_1^{f_1} p_2^{f_2} \dots p_k^{f_k} } )^2 \implies p_1^{2e_1} p_2^{2e_2} \dots p_k^{2e_k} = m p_1^{2f_1} p_2^{2f_2} \dots p_k^{2f_k}$ . For m is not a square, the prime factorization of $m$ must include at least one prime with an odd exponent. And this creates a contradiction. ■

THm 2.7 (Infinitude of Primes)

There are infinitely many prime numbers.

pf. I just give 3 proofs here.
Euclid's Proof (Contradiction)

1. Assume there are finitely many primes: $p_1, p_2, \dots, p_n$ .
2. Construct $N = p_1 \cdot p_2 \cdots p_n + 1$ .
3. $N$ is either prime or divisible by a prime:

• If $N$ is prime, it is not in the list.
• If $N$ is divisible by a prime $p_i$ , then $N \mod p_i = 1$ , a contradiction.

4. Thus, primes are infinite.

Proof Using the Fundamental Theorem of Arithmetic

1. Every integer $n > 1$ has a unique prime factorization.
2. Suppose there are only finitely many primes $p_1, p_2, \dots, p_n$ .
3. The number of distinct products $p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n}$ is finite.
4. This contradicts the fact that there are infinitely many integers.
5. Hence, primes must be infinite.

Proof Using the Density of Primes

1. For any $n$ , consider the numbers $2, 3, \dots, n$ .
2. By the Prime Number Theorem, the number of primes $\leq n$ grows approximately as $\frac{n}{\log n}$ .
3. Since $\frac{n}{\log n} \to \infty$ as $n \to \infty$ , there are infinitely many primes. ■

THm 2.8 (Dirichlet's Theorem on Arithmetic Progressions)

If $a$ and $b$ are coprime integers (i.e., $\gcd(a, b) = 1$ ), then there are infinitely many primes of the form $aq+b$ .

pf. The proof of Dirichlet's Theorem is highly non-trivial and relies on advanced number theory, so we only prove the case when $a=4$ and $b=3$ .
Suppose that there have only finitely many primes of this form say $p_1, \dots ,p_k$ .
Consider

$c= 4 \prod_{i=1}^{k} p_i -1$

where c must be an odd integer, if c has prime divisor, it must be of the form $4q+1$ or $4q+3$ . The integer $c$ is not divisible by any of the primes $p_1, p_2, \dots, p_k$ because of its form. So the divisor of $c$ can all be writen as $4q+1$ , then $c=(4q_1+1) \dots (4q_t+1) =4k+1$ , this creates a contradiction. ■

THm 2.10 (Prime Number Theorem)

$\lim_{x \to \infin} \frac{\pi (x)}{ \frac{x}{ \ln x} } =1 \; \; \; \; \text{"Density"} \; \; \; \frac{ \pi (x)}{ \lfloor x \rfloor} \approx \frac{1}{ \ln x}$

$\mathrm{li} (x)= \int_{2}^{x} \frac{ \mathrm{d} t}{ \ln x} = \mathrm{Li} (x) - \mathrm{Li} (2) \sim \frac{x}{ \ln x}$

Experiments indicate that $\pi (x)$ is always less than $\mathrm{Li} (x)$ when $x$ is small. But Littlewood in 1914 proved that there is a crossover point, when $x$ is bigger than it, there is $\pi (x) > \mathrm{Li} (x)$ ,and crossovers like this are infinitely many. (It has been proven that the first crossover is before $10^{19}$ )

note: $\pi (x)$ denotes the number of primes $p \leq x$ .The above is conjectured by Gans and proven by Hadnard.

pf. See the proof at Newman's proof . ■

THm 2.11 (Riemann Hypothesis)

$\pi (x) = \mathrm{li} (x) - \frac{1}{2} \mathrm{li} (\sqrt{x}) - \sum_p \mathrm{li} (x^p) + \text{(lower-order components)}$

The heuristic reason for the term $\frac{1}{2} \mathrm{li} ( \sqrt{x})$ is that $\mathrm{li} (x)$ actually counts powers of primes with $p^n$ weightd by $\frac{1}{n}$ .
Conjecture $\forall x \geq 2.01$ , $| \pi (x) - \mathrm{Li} (x)| \leq \sqrt{x} * \ln x$ , is equivalent to Riemann Hypithesis.

仅作了解。

2.3 Fermat and Mersenne primes

Lemma 2.12

If $2^m+1$ is a prime, then $m=2^n$ for some integer $n \geq 0$ .

pf. If $m$ has an odd factor $q$ , then $m=2^n *q$ , then $2^m+1=( 2^{2^n} )^q+1$ , which has factor $2^{2^n} +1$ , this contradicts the fact that
$2^m +1$ is a prime number. ■

Def 2.13

Numbers of the form $F_n = 2^{2^n} +1$ are called Fermat numbers, and primes of the form are called Fermat prime. $\; \; \; \;$ Numbers of the form $M_p = 2^p -1$ are called Mersenne numbers, and primes of the form are called Mersenne prime.

Lemma 2.14

Different Fermat Numbers are mutually coprime.

pf.

$F_n -2 = 2^{2^n} -1 = \prod_{k=0}^{n-1} F_k$

So $F_n$ is coprime with $F_1 , \dots , F_{n-1}$ . ■

Remark: (Gauss–Wantzel theorem) A number $n$ is constructible with a straightedge and compass iff $n=2^e p_1 p_2 \dots p_k$ , where $p_i$ 's are Fermat primes.
See the proof at Proof of Gauss-Wantzel Theorem. (A graceful proof!!!)

2.4 Primality-testing and factorisation

Skip, it will be mentioned in the later chapters.

3. Congruences

NOTE

由于这一章的笔记完全没按照小节划分来，所以小节标号就不加了。
似乎从这里开始标号就和书本错开了，，，
今天刷到一篇很有意思的科普，感兴趣的可以看看： 从循环小数到群作用 。

Def 3.1

A binary relation $\sim$ on a set $X$ is said to be an equiv relation if it is reflexive( $a \sim a$ ), symmetric( $a \sim b$ iff $b \sim a$ ) and transitive( $a \sim b$ , $b \sim a \implies a \sim c$ ).
The equivalence class of $a$ under $\sim$ is defined as $[a]= \{ x \in X \mid x \sim a \}$ . $a$ is called a representative of $[a]$ . Clearly $[a] = [b]$ 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 \; ( \! \! \! \mod n)$ written as $a \equiv b \; \; ( \! \! \! \mod n)$ if $n \mid a-b$ . We denote the equivalence classes modular $n$ by $\mathbb{Z}_n$ .
$[a] \pm [b] = [a \pm b]$ , $[a] [b] = [ab]$ , the three modular operqtions are well defined.

---

abstract algebra

To better understand the following content, we interrupt the note with something about abstract algebra.

Def 3.6 (Group)

A group $G$ is a set $G$ with a binary operation $(*)$ , satisfying 1 ) Associativity 2 ) Identity 3 ) Inverse. A group is called alelian group if the operation $(*)$ is commutative.

Def 3.7 (Ring)

A ring is a set $R$ with two binary relations $(+,*)$ . Additive structure $(R,+)$ is an abelian group (with zero element $0$ ) A ring satisfying 1 )Associativity 2 ) Distributivity 3 ) (not-necessary) Identity.

Ex. matrix ring, polynomial ring.

abstract algebra end

---

THm 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 congruence class is called a complete set of residue mod $n$ .

Lemma 3.11

For $f \in \mathbb{Z} [x]$ if $a \equiv b \; ( \! \! \! \mod n)$ , then $f(a) \equiv f(b) \; (\! \! \! \mod n)$ .

Ex 3.13 (failure of Hasse Principle)

The polynormial $f(x) = (x^2 -13) (x^2 -17)(x^2 -221)$ has no integer roots. But we can see that for each integer $n>1$ , there is a solution for $f(x) \equiv 0 \; (\! \! \! \mod n)$ .

Ex 3.14 (Euler's polynormial)

Euler found a remarkable polynormial $f(x)= x^2 +x +41$ , $f(x)$ is a prime for each $-41<x<40$ . (only 7 lucky numbers of Euler exists : $1,2,3,5,11,17,41$ )

THm 3.15

There is no non-constant polynormial $f(x)$ with integer coefficient such that $f(x)$ assume prime value at each integer $x$ .

pf. Suppose that $f(x)$ is prime for all $x \in \mathbb{Z}$ and $f$ is non-constant.Pick an integer $a$ , then $f(a)=b$ and Lemma 3.11 for $b \equiv a \; ( \! \! \! \mod p)$ we have $f(a) \equiv f(b) \equiv 0 \; (\! \! \! \mod p)$ . But $p$ is a prime , so $f(a)=f(b)=p$ in this we get infinitely many $x$ s. t. $f(x) = p$ , then $( x) - p$ has infinitely many zero-point. Obviously there does not exist such $f(x)$ . ■

Ex. If $a_1=7$ , $a_n = a_{n-1} + \gcd (n, a_{n-1} )$ , then $\gcd (n , a_{n-1} )$ can only be a prime or $1$ .

THm 3.16

The linear congruence $ax \equiv b \; (\! \! \! \mod n)$
1 ) has a solution iff $d= \gcd (a,n)$ divides $b$ ( $d \mid b$ ) , then the general solution is given by $x= x_0 + \frac{nt}{d} \; \; \;(t \in \mathbb{Z} )$ .
2 ) Moreover, the slolution have exactly $d$ congreuence classes $\mod n$ . The representatives are given by $t=1,2, \dots ,d-1$ .

pf.
1 ) is almost a reformulation of THm 1.19 .
2 ) Suppose $x' = \frac{nt'}{d}$ is another solution, then there is $x_0+ \frac{nt}{d} \equiv x_0 + \frac{nt'}{d} \; (\! \! \! \mod n) \iff n \mid \frac{n(t-t')}{d} \iff d \mid t-t'$ so there are only $d$ congruence classes. ■

Corollary 3.17

If $\gcd (a,n) =1$ , then the linear congruence $ax \equiv b \; (\! \! \! \mod n)$ has a unique class of solution.

Remark 3.18: This suggests thai if $\gcd (a,n) =1$ , then we can define division $[b]/[a]$ in $\mathbb{Z}$ as the unique class $[x]$ such that $[a][x]=[b]$ .
In particular, $\mathbb{Z}_p \backslash \{ 0\}$ forms a group.

Lemma 3.18

(a) If $m$ divides $a,b,n$ and let $(a',b',n')=(a,b,n)/m$ , then $ax \equiv b \; (\! \! \! \mod n)$ iff $a' x \equiv b' \; (\! \! \! \mod n')$ .
(b) If $\gcd (a,n) =1$ , $m$ divides $a,b$ ,and let $(a',b')=(a,b)/m$ , then $ax \equiv b \; (\! \! \! \mod n)$ iff $a' x \equiv b' \; (\! \! \! \mod n')$ .

Algorithm 3.19

Solve $ax \equiv b \; (\! \! \! \mod n)$ .
The goal is using Lemma 3.18 to reduce $a$ to $1$ .

• Step 1 : Calculate $d= \gcd (a,n)$ (If $d \nmid b$ , then no solution )
• Step 2 : Now $d$ divides $a,b,n$ ,use Lemma 3.18 (a) to replace the original equation by a new congruence $a' x \equiv b' \; (\! \! \! \mod n')$ . (where $(a',b',n')=(a,b,n)/m$ )
• Step 3 : Use Lemma 3.18 (b) to replace the previous one by a new congruence $a'' x \equiv b'' \; (\! \! \! \mod n')$ (where $(a'',b'')=(a',b')/m$ )
• Step 4 : If $a''=1$ , then we have done , otherwise we need to find a $k$ such that $\gcd (a'',b'' + kn) \neq 1$ , replace $b''$ by $b''+ kn$ , go back to Step 3 and repeat until $a=1$ .

THm 4.1 (Chinese Remainder Theorem)

Let $n_1 ,n_2 , \dots , n_k$ be mutually coprime, and $b_1,b_2, \dots , b_k$ be any integer. Then the solution of the system of congruences $x \equiv b_i \mod n_i \; \; (i=1,2, \dots ,k)$ form a single congreuence class $\mod n$ , where $n= \prod_{i=1}^{k} n_i$ .

pf. Let $c_i= \frac{n}{n_i} \; \; (i=1,2, \dots ,k)$ , $c_i$ is coprime to $n_i$ . Then Corollary 3.17 implies that $c_i x \equiv 1 \mod n_i$ has a single class $[d_i]$ of solution. Now let $x_0=\sum_{i=1}^{k} b_i c_i d_i$ , claim $x_0$ is a particular solution $(x \equiv b_i c_i d_i \mod n_i \; , \; \; c_i d_i \equiv 1 \mod n_i \implies x \equiv b_i \mod n_i)$ .
If $x$ is another solution, then there is $n_i \mid x-x_0$ for each $i$ , then there is $n \mid x-x_0$ . ■

Corollary 4.2

Let $n=p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ be a prime power factorization. Then for any $a,b \in \mathbb{Z}$ , we have that $a \equiv b \mod n$ iff $a \equiv b \mod p_i^{e_i}$ for each $i=1,2, \dots ,k$ .

---

abstract algebra

To better understand the following content, we interrupt the note with something about abstract algebra.
A diagresion on groups and rings.

Def

Produce of sets $X \times Y= \{ \; (x,y) \mid x \in X ,y \in Y \}$
Suppose $G_1 ,G_2$ are groups, define $G_1 \times G_2$ be the set $G_1 \times G_2$ with multiplication given by $(g_1,g_2)*(h_1,h_2)=(g_1*h_1,g_2*h_2)$ .
And similarly for the rings.

Def (Homonorphism)

(Group Homonorphism) $\varphi: G \rightarrow H$ (preserve multiplication)
(Ring Homonorphism) $\varphi: R \rightarrow S$ (preserve multiplication and addition)

Remark: If $R$ has identity, then $S$ has identity and $\varphi(I_R)=I_S$ .
Easy Fact: A group homonorphism must preserve identity and inverse.

Def

The kernal of a group homonorphism $\varphi: G \rightarrow H$ is $\ker( \varphi )= \{ g \in G \mid \varphi (g) = e_H\}$

Lemma

A group homonorphism $\varphi: G \rightarrow H$ is injective iff $\ker( \varphi )= \{ e_G \}$ .

pf. Suppose not injective, then $\exists g_1 \neq g_2$ s.t. $\varphi (g_1) = \varphi (g_2) \\ \iff \varphi (g_1) \varphi (g_2)^{-1} = e_H = \varphi(g_1) \varphi (g_2^{-1}) \\ \iff \varphi(g_1 * g_2^{-1}) = e_H$
又 $g_1 \neq g_2 \implies g_1 * g_2^{-1} \neq e_G \in \ker(\varphi)$ , creates contradiction. ■

Remark: More generally, $\mathbb{Z}_m \rightarrow \mathbb{Z}_n$ is well defined iff $n \mid m$ . In this case, the map is a ring homonorphism.
More generally, if $f_i: R \rightarrow S \; (i=1,2, \dots ,k)$ are ring homonorphism, then $R \rightarrow S_1 \times S_2 \times \dots \times S_k$ is ring homonorphism.

Def

Group homonorphism $\varphi: G \rightarrow H$ is called an isomorphism is $\exists \varphi^{-1}$ and it is a group homonorphism. Then $G$ and $H$ are equivalent naturally.

abstract algebra end

---

THm 4.6 (Reformulation of CRT)

Suppose that $\gcd (n_i,n_j)=1 \; ( \forall i \neq j)$ . Then the map $\varphi : \mathbb{Z_n} \rightarrow \mathbb{ Z_{ n_1 } } \times \mathbb{ Z_{ n_2 } } \times \dots \times \mathbb{ Z_{ n_k } }$ is a ring isomorphism.

pf. The two rings have the same number of elements, so we only need injectivity. $\iff \ker ( \varphi ) = 0$. That is, if $\varphi ([a]_n)=0$ then each $[a]_{n_i}=0 \iff n_i \mid a \implies n \mid a \implies [a]_n = 0$ in $\mathbb{Z}_n \implies \varphi$ is injective. ■

Remark: This proof is shorter than no explicit solution to this system of congruence.

(Extension of CRT)

THm 4.7 (Extension to nonlinear cases)

Let $f \in \mathbb{Z}_{[x]}$ , let $A(n)= \{ [a] \in \mathbb{Z}_n \mid f(a) \equiv 0 \mod n \}$ . If $n_1, \dots , n_k$ are mutually coprime, and $n= \prod_{i=1}^{k} n_i$ , then the map $A(n) \rightarrow A(n_1) \times \dots \times A(n_k)$ is bijective.
In particular, $|A(n)| = |A(n_1)| \times \dots \times |A(n_k)|$ .

pf. Since $n_1 , \dots , n_k$ are mutually coprime, $f(a) \equiv 0 \mod n$ iff $f(a) \equiv 0 \mod n_i$ for $i=1,2, \dots , n$ . Therefore the map $\varphi$ in THm 4.6 is restricts to the class of solution for $f(a) \equiv 0 \mod n$ , which is still bijective. ■

THm 5.1 (Extension to non-coprime cases)

$x \equiv b_i \mod{n_i}$ $(i=1, \dots ,k) (*)$

Let $n_1, \dots , n_k$ be positive integers. Then the solutions of the system $(*)$ has a solution iff $\gcd{ (n_i,n_j) }$ divides $b_i-b_j$ whenever $i \neq j$ . In the case, the general solution forms a single congruence class $\mod{ (n) }$ where $n= \text{lcm} (n_1, \dots , n_k)$ .

pf. Set $n_{ij}= \gcd{ (n_1,n_j) }$ . If a solution $x$ exists, then $n_i \mid x-b_i$ , then $n_{ij} \mid b_i-b_j$ . Let $x_0$ be any solution, then for any solution $x$ we have $n_i \mid x-x_0$ for each $i$ , this is equivalent to $n \mid x-x_0$ .
We remain to show the condition $n_{ij} \mid b_i-b_j$ guarantee the existence of a solution. We can replace each congruence $x \equiv b_i \mod{n_i}$ by an equivalent set of congruence $x \equiv b_i \mod{p^e}$ , where $p^e$ ranges over all the prime power factorization of $n_i$ . We can apply the original CRT to this situation, there is only one congruence for each $p$ . Let $e$ be the highest power of $p$ in all $n_i$ 's. We use the condition that $\gcd{ (n_i,n_j) } \mid b_i-b_j$ to discard all congruence $\mod{p^d}$ for $d<e$ . ■
*Suppose that $p^e \parallel n_i$ and $p^d \parallel n_j$ then $p^d \mid n_{ij} \mid b_i-b_j$ , so $p^e \mid x-b_i \implies p^d \mid x-b_j$ , so $x \equiv b_j \mod{p^d}$ .

4. Congruence with a Prime-power Modulus

4.1 The arithmetic of $\mathbb{Z}_p$

THm 5.3 (lagrange)

Let $p$ be a prime, and let $f(x) \in a_d x^d + \dots + a_1 x +a_0$ where $p \nmid a_i$ for some $i$

4.2 Pseudoprimes and Carmicheal numbers

4.3 Solving congruences mod ( $p^e$ )

5. Euler's Function

5.1 Units

5.2 Eulae's Function

5.3 Application of Euler's Function

6. The Group of Units

6.1 The group $U_n$

6.2 Primitive roots

6.3 The group $U_{p^e}$ , where $p$ is an odd prime

6.4 The group $U_{2^e}$

6.5 The existence of primitive roots

6.6 Applications of primitive roots

6.7 The algebraic structure of $U_n$

6.8 The universal exponent