## MODULAR

Phép chia đồng dư:
$$a \equiv b \pmod{n}$$

với $n > 1$ gọi là modul, a và b gọi là đồng dư modul n nếu hiệu của chúng chia hết cho n $(a - b = kn)$

VD: $38 \equiv 14 \pmod{12}$

Đồng dư còn áp dụng cho số nguyên âm:

$2 \equiv -3 \pmod{5}$
$-3 \equiv 7 \pmod{5}$

### Tính chất:
* Phản xạ: $a \equiv a \pmod{n}$
* Đối xứng: $a \equiv b \pmod{n} \Leftrightarrow b \equiv a \pmod{n}$
* Bắc cầu: nếu $a \equiv b \pmod{n}$ và $b \equiv c \pmod{n}$ thì $a \equiv c \pmod{n}$

### Phép toán:
$a + k \equiv b + k \pmod{n}$ với mọi số nguyên $k$.

$k \cdot a \equiv k \cdot b \pmod{n}$ với mọi số nguyên $k$ nguyên tố cùng nhau với n.

$k \cdot a \equiv k \cdot b \pmod{kn}$ với mọi số nguyên $k$.

$a_1 + a_2 \equiv b_1 + b_2 \pmod{n}$.

$a_1 - a_2 \equiv b_1 - b_2 \pmod{n}$.

$a_1 \cdot a_2 \equiv b_1 \cdot b_2 \pmod{n}$.

$a^k \equiv b^k \pmod{n}$ với mọi số nguyên dương $k$.

$p(a) \equiv p(b) \pmod{n}$, với mọi đa thức $p(x)$ có hệ số nguyên.

## Thuật toán Euclid
Dùng để tìm UCLN của 2 số a, b dựa trên nguyên tắc là ước chung lớn nhất của hai số nguyên không thay đổi khi thay số lớn hơn bằng hiệu của nó với số nhỏ hơn.

def gcd(a, b):
while 1:
a, b = b, a % b
if b == 0:
return a

ví dụ: gcd(138, 28) = 2

## Thuật toán

Thuật toán Euclide mở rộng
Hai số nguyên dương a, b (a ≥ b)
Output: d = gcd(a, b) và số nguyên x, y thỏa mãn ax + by = d
1. If b = 0 then d < a, x <- 1, y < 0 and Return(d, x, y).
2. x2 <1, x10, y2+0, y1 <1
3. While b > 0 do
3.1. q +la/pl, r + a - qb, x < x2 - qx1, y <y2 - qy1
3.2. a + b, b +r, x2 x1, x1 < x, y2 < y1, y1 - y
4. d <a, x < X2, y < y2
5. Return(d, x, y)

def exGCD(a, b):
if b == 0:
d = a
x = 1
y = 0
return d, x, y
x1 = 0
x2 = 1
y1 = 1
y2 = 0
while b > 0:
q = a // b
r = a % b
x = x2 - q*x1 
y = y2 - q*y1
a, b = b, r
x2 = x1
x1 = x
y2 = y1
y1 = y
d = a
x = x2
y = y2
return d, x, y

## Định lý Ferma (Định lý Ferma nhỏ)
$a^{p-1} \pmod{p} \equiv 1$ trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội
của p: GCD(a, p) = 1.
Hay $\forall$ p và a không là bội p, ta luôn có $a^{p} \equiv a \pmod{p}$
Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn p.

## Hàm $\phi(n)$
Tập $Z_n$ = {0, 1, 2, ... , n -1} thường được gọi là thặng dư đầy đủ theo modul
Xét tập $Z_n ^ *$ = {a $\in Z_n$: gcd(a, n) = 1}. Tập này được gọi là tập các thặng dư thu gọn theo modul n
Nếu p là số nguyên tố thì $Z_p ^ *$ = {1, 2, ... , p - 1}
Kí hiệu $\phi(n)$ (hàm Euler) là số phần tử lớn hơn 0, nhỏ hơn n và nguyên tố cùng nhau với n

Các tính chất của hàm $\phi(n)$:
Dễ dàng thấy, nếu p là số nguyên tố $\phi(n) = p-1$
Nếu gcd(m, n) = 1, thì: $\phi(m.n)$ = $\phi(m). \phi(n)$
Nếu $n = p_1 ^ {e_1}. p_2 ^ {e_3} \dots p_k ^ {e_k}$ là phân tích ra thừa số nguyên tố của n thì:
$$\phi(n) = n.(1 - \frac{1}{p_1}).(1 - \frac{1}{p_2}) \dots (1 - \frac{1}{p_k})$$

## Định lý Ole:
Định lý Ole là tổng quát hóa của Định lý Fermat:
$$a ^ {\phi(n)} \equiv 1 \pmod{n}$$
với mọi cặp số nguyên dương nguyên tố cùng nhau a và n: gcd(a,n)=1.

## Định lý Euler:
Nếu $a \in Z_n ^ *$ thì $a ^ {\phi n } \equiv 1 \pmod{n}$
Nếu n là tích các số nguyên khác nhau và nếu $r \equiv s \pmod{\phi n}$ thì $a^r \equiv a^s \pmod{n}$; $\forall$a
## Định nghĩa cấp của phần tử:
Cho $a \in Z_n ^ *$. Cấp a kí hiệu ord(a) là số nguyên dương nhỏ nhất t sao cho: $a^t \equiv 1 \pmod{n}$
Lưu ý: Cho $a \in Z_n ^ *$, ord(a) = t và $a^s \equiv 1 \pmod{n}$ khi đó t là ước của s. Đặc biệt
t|$\phi n$

## Định nghĩa phần tử sinh:
$a \in Z_n ^ *$ được gọi là phần tử sinh của $Z_n ^ *$ nếu:
$$Z_n ^ * = \{{a ^ i \mod n| 0 ≤ i ≤ \phi n- 1}\}$$

Cho $a \in Z_n ^ *$. Nếu cấp của a = $\phi n$ thì a được gọi là phần tử sinh của $Z_n ^ *$
(hay còn được gọi là phần tử nguyên thuỷ).
Nếu $Z_n ^ *$ có phần tử sinh thì $Z_n ^ *$ được gọi là nhóm xyclic

Các tính chất:
Nếu a là một phần tử sinh của $Z_n ^ *$ thì:
$$Z_n ^ * = \{a ^ i \pmod n | 1 ≤i ≤ \phi n -1\}$$

Giả sử a là một phần tử sinh của $Z_n ^ *$. Khi đó: $b \equiv a ^ i \pmod n$ cũng là phần tử sinh của $Z_n ^ *$ nếu và chỉ nếu gcd(i, (n)) = 1.

Nếu $Z_n ^ *$ là xyclic thì số phần tử sinh là $\phi(\phi n)$

$a \in Z_n ^ *$ là phần tử sinh Z* nếu và chỉ nếu $a ^ {\phi n / pi} \pmod n \neq 1$ đối với mỗi nguyên tố của $\phi n$

$Z_n ^ *$ có phần tử sinh nếu và chỉ nếu n = 2, 4, $p ^ k$ hoặc 2.$p ^ k$
Trong đó p là số nguyên tố lẻ và $k >= 1$.

## Định lý Thặng dư Trung Hoa
n1, ... , nk nguyên tố cùng nhau từng đôi một thì hệ sau có nghiệm duy nhất theo modulo n = n1...nk

$x \equiv a_1 \pmod n$
$x \equiv a_2 \pmod n$
$x \equiv a_3 \pmod n$

Giải hệ phương trình modulo:
Cho:

$x \equiv a_1 \pmod n_1$
$x \equiv a_2 \pmod n_2$
$\vdots$
$x \equiv a_k \pmod n_k$

Với GCD($n_i$, $n_j$) = 1, $\forall i \neq j$. Khi đó ta cũng áp dụng Định lý phần dư Trung Hoa để tìm x.
Nghiệm x của hệ phương trình được tính như sau:
$$x \equiv \displaystyle\sum_{i=1}^{k} a_i.N_i.M_i \pmod n$$
Trong đo: N = n1 ... nk. $N_i$ = N/n,. $M_i \equiv N ^ {-1} \mod n$

## Định nghĩa thặng dư bậc 2 và bất thặng dư bậc 2:
Cho $Z_n ^ *$, a đuợc gọi là thặng dư bậc hai theo modulo n (hay bình phương modulo n) nếu $\exists x \in Z_n ^ *: x^2 \equiv a \pmod p$. Nếu không tồn tại x như vậy thì a được gọi là bất thặng dư bậc hai mod n.
Tập tất cả các thặng dư bậc hai modulo n được KH: $Q_n$.
Tập tất cả các bất thặng dư bậc ha hai modulo n được KH: $\overline{Q_n}$

Định lý:
Cho p là nguyên tố lẻ và a là phần tử sinh của $Z_n ^ *$. Khi đo $\exists a \in Z_n ^ *$ la một thặng dư bậc hai modulo p nếu và chỉ nếu $a \equiv a^i \pmod p$ với i là số nguyên chẵn

Hệ quả: |$Q_n$| = $(p-1)/2$ ; |$\overline{Q_n}$| = $(p-1)/2$

Định nghĩa căn bậc hai của một số modulo n:
Cho a $\in Q_n$,. Nếu $\exists x \in Z_n ^ *$,. thỏa mãn $x^2 \equiv a \pmod n$ thì x được gọi là căn bậc hai của a mod n.
Định lý về số căn bậc hai của một số modulo n:
Cho $n = p_1 ^ {e_1}. p_2 ^ {e_3} \dots p_k ^ {e_k}$ , trong đó p, là các số nguyen tố lẻ phân biệt và
e ≥ 1. Nếu a $\in Q_n$ thì có đúng $2^k$ căn bậc hai khác nhau theo modulo n

## Ký hiệu Legendre và Jacobi:
Định nghĩa: p là số nguyên tố lẻ, a là số nguyên. KH Legendre $(\frac{a}{p})$ được xác định như sau:


Cách tính ký KH Legendre $(\frac{a}{p})$

$$(\frac{a}{p}) = a^{(p-1)//2} \mod p$$