Thặng dư bình phương và các tính chất

Định nghĩa 1: Một số nguyên a được gọi là thặng dư bình phương mod n nếu tồn tại số nguyên x sao cho

$x^2 \equiv a (mod n)$
Ta cũng có thể gọi a là số chính phương mod p
Định nghĩa 2: Giả sử p là một số nguyên tố lẻ, a là một số nguyên, Kí hiệu Legendre $\left ( \frac{a}{p} \right )$được xác định như sau:

$\left ( \frac{a}{p} \right )=1$ Khi (a,p)=1 và a là thặng dư bình phương mod p

$\left ( \frac{a}{p} \right )=-1$ Khi (a,p)=1 và a không là số chính phương mod p

$\left ( \frac{a}{p} \right )=0$ nếu $a \vdots p$

Định lý:
1) (Tiêu chuẩn Euler) Cho p là một số nguyên tố và a là một số nguyên. Khi đó ta có $a^{\frac{p-1}{2}}\equiv \left ( \frac{a}{p} \right ) (mod p)$

Chứng minh:

Gọi g là một căn nguyên thủy của p (có nghĩa là g là một số nguyên sao cho p-1 là số mũ lớn nhất để $g^{p-1} \equiv 1 (mod p)$ Khi đó ta được hệ thặng dư thu gọn mod p {$1,g,g^2,..g^{p-2}$}.

Giả sử $a=g^i$ Ta cần chứng minh:

$a^{\frac{p-1}{2}} \equiv (g^i)^{\frac{p-1}{2}} \Rightarrow i.\frac{p-1}{2}\equiv 0 (mod p-1)$

$\Rightarrow$ i là số chẵn

Suy ra tồn tại j sao cho i=2j $\Rightarrow a=(g^j)^2 \Rightarrow \left ( \frac{a}{p} \right )=1$

Ngược lại  $\left ( \frac{a}{p} \right )=1 \Rightarrow$ tồn tại j sao cho $a \equiv (g^j)^2 (mod p) \Rightarrow g^i\equiv (g^j)^2 (mod p) \Rightarrow i \equiv 2j(mod p-1) \Rightarrow i\equiv 0(mod 2)$

Do đó $a^{\frac{p-1}{2}}\equiv (g^i)^{\frac{p-1}{2}}=g^{(p-1)k}\equiv 1 (mod p)$

Bài tập áp dụng:
Cho $f_n$ là số Fermat chứng minh rằng ước nguyên tố p của $f_n$ có dạng $p=s.2^{n+2}+1$ với s là số tự nhiên.

Giải
Gọi $m=ord_2(p)$ suy ra m có dang $2^k$ rõ ràng k không thể $\le n$
Vậy $k=n+1$, áp dụng định lý Fermat bé ta có $p=h.2^{n+1}+1$

Ta xét $p=8t+1$ khi đó theo tiêu chuẩn euler thì 2 là số chính phương mod p.

Suy ra $2^{n+1} | (p-1)/2$ suy ra điều phải chứng minh
Định lí 2: Luật tương hỗ Gauss;


$\left ( \frac{p}{q} \right )\left ( \frac{q}{p} \right )=(-1)^{\frac{(p-1)(q-1)}{4}}$

Chứng minh

Đặt A={a|(a,pq)=1,$1 \le a \le \frac{pq-1}{2}$}, $B=\prod_{x \in A}x$

Còn tiếp ...