# Thặng dư Trung Hoa
- Cho hệ sau:
$$x \equiv a_1 \pmod{m_1}$$ $$x \equiv a_2 \pmod{m_2}$$ $$\vdots$$ $$x \equiv a_n \pmod{m_n}$$
- Thỏa mãn yêu cầu: $m_1, m_2, ...., m_n$ đôi một nguyên tố cùng nhau.
- Ta có công thức tổng quát như sau:
$$\prod_{i=\ 1}^{n} \ m_i$$ $$M_i= \frac{M}{m_i}$$
- Với:
$$y_1 \equiv {M_1}^{-1} \pmod{m_1}$$ $$y_2 \equiv {M_2}^{-1} \pmod{m_2}$$ $$\vdots$$ $$y_n \equiv {M_n}^{-1} \pmod{m_n}$$
- Khi đó: $x \equiv \sum_{1}^n\ (y_i.M_i.a_i) \pmod{M}$
# Euclid mở rộng
- Sử dụng để giải phương trình vô định nguyên có dạng:
\begin{align*}
ax + by &= c, \\
\text{Với } a, b, c &\in \mathbb{Z} \text{ là hệ số}.
\end{align*}
Giả sử tồn tại $d = \text{UCLN}(a, b)$. Khi đó, tồn tại các số nguyên $x$ và $y$ thỏa mãn:
\begin{align*}
ax + by &= d.
\end{align*}

**Chứng minh:**

Theo định lý Bezout, ta có:

$$ax + by = d \cdot \text{gcd}(a, b) = d \cdot \text{gcd}(a, b) \cdot \frac{a}{d} \cdot \frac{b}{d} = \frac{ad}{d} \cdot \frac{bd}{d} = \frac{ab}{d}.$$

Vì $a$ và $b$ là các số nguyên, nên $\frac{ab}{d}$ cũng là một số nguyên. Do đó, tồn tại các số nguyên $x$ và $y$ sao cho $ax = \frac{ab}{d}$ và $by = \frac{ab}{d}$. Từ đó, ta có:

$$ax + by = \frac{ab}{d} + \frac{ab}{d} = \frac{2ab}{d} = d.$$

**Kết luận:**

Vậy, giả sử tồn tại $d = \text{UCLN}(a, b)$ thì tồn tại các số nguyên $x$ và $y$ thỏa mãn $ax + by = d$.

\begin{align*}
\text{Bài toán tổng quát:}\
\text{Cho }\ a, b &\in \mathbb{Z} (a> b> 0)\ \text{tìm x, y thỏa mãn:}\
x.a +y.b= d\ \text{với}\ d= UCLN(a; b)$.
\end{align*}
**Giải:**
$$\text{Đặt: }\ r_0= a,\ r_1= b$$\begin{align*}
\text{Ta có: }\
r_0= r_1q_1+\ r_2\\
r_1= r_2q_2+\ r_3\\
&\vdots\\
r_n= r_{n+1}+\ r_{n+2}\\
\text{Với: }\ r_{n+2}= 0
\end{align*}
Bài toán đặt ra là tìm x, y thỏa mãn:
\begin{align*}
ax+ by= r_{n+2}\ (=\ d)
\end{align*}
Truy hồi:
$\text{Ta cần tìm}\ x_n, y_n\ \text{thỏa mãn: }\\
ax_n+ by_n= r_n (n \in \mathbb{N})$
Với:
$$x_0=\ 1,\ y_0=\ 1$$ $$=> r_0= a$$
Đặt (I): $$x_1= 0, y_1= 1$$ $$=> r_1= b$$
Tổng quát:
Giả sử ta có: $$ax_i+ by_i= r_i (i \in \mathbb{N})$$ $$ax_{i+ 1}+ by_{i+ 1}= r_{i+ 1}$$
Khi đó: $$r_i= q_{i+ 1}r_{i+ 1}+ r_{i+ 2}$$ $$=>r_i- q_{i+ 1}r_{i+ 1}= r_{i+ 2}$$ $$<=>(ax_i+ by_i)- q_{i+ 1}r_{i+1}= r_{i+2}$$
Đặt (II):
$$x_{i+ 2}= x_i- q_{i+ 1}x_{i+ 1}$$ $$y_{i+ 2}= y_i- q_{i+ 1}y_{i+1}$$
Từ (I) và (II) sử dụng truy hồi để tìm x, y.
## Modulo
Tính chất:
$${1.\ (a+ b) mod(n)= [(a mod(n))+ (b mod(n))] mod(n)}$$ $${2.\ ab mod(n)= [a mod(n).b mod(n)] mod(n)}$$ $${3.\ a= b^{-1} mod(n)}$$ $${<=> ab= 1 mod(n)\ (\in d(b;n)= 1)}$$ $${4.\ a= b^{-1} mod(n)<=> ab= 1 mod(n)\ hay\ a= \frac{1}{b} mod(n)(\forall d(b; n)= 1)}$$
**Fermat nhỏ:**
$$a^{p-1} \equiv 1 mod(p) (\forall \text{p là số nguyên tố và}\ d(a;p)= 1)$$
**Euler:**
$$a^{\phi{(n)}} \equiv 1 mod(n) (\forall d(a;n)= 1)$$
Xét:
\begin{cases}{}
a; p \in \mathbb{Z}\\
\text{p là số nguyên tố}\\
d(a;p)= 1
\end{cases}
Ta có
$$a^{\frac{p-1}{2}} \equiv \begin{cases}{}
1 \text{nếu }\exists\ x:\ x^2 \equiv a\ mod(p)\\
-1 \text{nếu }\nexists\ x:\ x^2 \equiv a\ mod(p)
\end{cases}$$
Mặt khác ta có thể suy ra: $$\frac{a}{p} \equiv a^\frac{p-1}{2}\ mod(p) \text{(Legendre symbol)}$$
**Fermat- Euler:**
Nếu $p= 4k+1\ thì\ \exists a;b\ \text{thỏa mãn: }p= a^2+b^2$
Nếu $snt p= 4k+3\ và\ d(a;b)=1\ thì\ a^2 +b^2 \not \vdots p$.
# Lý thuyết nhóm
## Nhóm
$$\text{Nhóm là:}\begin{cases} \text{tập hợp G} \\
\text{phép toán 2 ngôi $*$(G; $*$)} \end{cases} \text{ thỏa mãn các yêu cầu sau:}$$
- Tính đóng $\forall a;\ b \in G$ ta có $a*b \in G$.
- Tính kết hợp: $\forall a;\ b;\ c \in G$ ta có $(a*b)*c=a*(b*c)$.
- Phần tử đơn vị: $\exists\ e \in G$ thỏa mãn $e*a=a*e=a\ (\forall a \in G)$ (e là phần tử đơn vị). Và nếu $\exists$ thì e là duy nhất.
- Phần tử nghịch đảo: với mỗi $a \in G: \forall b \in G$ thỏa mãn: $a*b=b*a=e$ (e là phần tử đơn vị).=> Phần tử nghịch đảo: $a^{-1}$.

**Nhóm con:**
- Cho G với phép toán $*$, tập hợp con H của G được gọi là nhóm con nếu: H và $*$ cũng tạo thành một nhóm.
- Khi H là nhóm con của G ta ký hiệu: $H \leqslant G$. Khi ấy phần tử đơn vị của G cũng là phần tử đơn vị của H.
## Cấp
- **ĐN$_1$**: Cho một nhóm hữu hạn G có phần tử đơn vị là e. Cấp của phần tử $u \in G$ là số nguyên dương nhỏ nhất của n thỏa man: $u^{n}= e$.
- **ĐN$_2$**: Cho n> 1 và a là các số nguyên dương thỏa mãn $gcd(a; n)= 1$. Số nguyên dương k nhỏ nhất thỏa mãn $a^{k} \equiv 1\ mod(n)$ được gọi là cấp của a theo modulo n, ký hiệu là $k= ord_n(a)$.
- **Tính chất:** $a^{x} \equiv 1\ mod(n) <=> ord_n(a)|x$
- **Hệ quả:** Cho a; n thỏa mãn:
$$n> 1\ và\ gcd(a; n)= 1$$ $$=> \phi(n)\ \vdots\ ord_n(a).$$
## Cyclic, phần tử sinh
- **ĐN$_1$**: Nhóm X được gọi là nhóm cyclic nếu $\exists a \in X\ và X= <a>$, tức X trúng nhóm con sinh bởi phần tử a, bao gồm tất cả các lũy thừa nguyên của a.
- Vậy: $$X= <a>= {a^{n}: n \in \mathbb{Z}}.$$
- **ĐN$_2$**: Cho nhóm X và $a \in X$, ord của phần tử a là ord của nhóm con cyclic sinh bởi a.
- Nếu $\exists g \in G$, sao cho mỗi $(a \in G\ ; a= g^{k})$ $(\forall k \in \mathbb{Z})$, G có dạng: $$.... ,g^{-3}, g^{-2}, g^{-1}, g^{0}(= e), g^{1}, .....$$ thì G là nhóm cyclic.
- **Tính chất:**
- $\mathbb{Z^*}_n$ có phần tử sinh nếu và chỉ nếu $n= 2,4, p^k$ hoặc $n= 2p^k$ với p là snt > 2.
- Nếu $\alpha$ là phần tử sinh của $\mathbb{Z^*}_n$ thì: $$\mathbb{Z^*}_n= {\alpha ^i mod(n)|1 \leqslant i \leqslant \phi(n)- 1}.$$
- Giả sử $\alpha$ là phần tử sinh của $\mathbb{Z^*}_n$. Khi đó $b= \alpha ^i mod(n)$, b cũng là phần tử sinh của $\mathbb{Z^*}_n$ nếu và chỉ nếu $d(i; \phi(n))= 1.$
- Nếu $\mathbb{Z^*}_n$ là cyclic thì số phần tử sinh là $\phi(\phi(n))$.
- Phần tử $a \in \mathbb{Z^*}_n$ là phần tử sinh của $\mathbb{Z^*}_n$ nếu và chỉ nếu $a^k \neq 1 \pmod{n}$ đối với mọi ước nguyên tố $k$ của $\phi(n)$.
- **Định lý:** Cho p là số nguyên tố khác 2, $\alpha$ là phần tử sinh của $\mathbb{Z^*}_p$. Khi đó $a \in \mathbb{Z^*}_p$ là một thặng dư bậc 2 modulo p$(a= x^2\ mod(p))$ $<=> a= \alpha ^i\ mod(p) (i\ \vdots\ 2)$.
- Hệ quả: $|Q_p|= \frac{p-1}{2}$; $|\bar{Q_p}|= \frac{p-1}{2}$.
- Với $Q_p$: là tập hợp các thặng dư bậc 2 modulo p.
- Với $\bar{Q_p}$: là tập hợp các bất thặng du bậc 2 modulo p.
- Cho $a \in Q_n$, nếu $x \in \mathbb{Z^*}_n$ thỏa mãn $x^2= a\ mod(n)$ thì x được gọi là căn bậc 2 của a mod(n).
- Cho $n= p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ trong đó $p_i$ là số nguyên tố lẻ phân biệt và $e_i \geqslant 1$. Nếu $a \in Q_n$ thì có đúng $2^k$ căn bậc hai phân biệt modulo n.