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 ...

Số Fermat và các tính chất

Các số tự nhiên có dạng $f_n=2^{2^n} +1$ được gọi là số Fermat

Ta có $f_0=1$

$f_1=5$

$f_2=17$

$f_3=257$

$f_4=65537$

$f_5=4294967295=641.6700417$

Như vậy ta có các tính chất sau:

i) $f_n=f_0.f_1..f_{n-1}+2$

ii) $(f_k,f_h)=1$

iii) $f_n$ tận cùng là 7 với n>1

i) ta có: $f_k=(2^{2^{k-1}})^2+1=(f_{k-1}-1)^2+1=f_{k-1}^2-2f_{k-1}+2$

Suy ra $f_n-2=f_0f_1..(f_0-2)=f_0.f_1...f_{n-1}$

ii) Suy ra từ i)

iii) Ta có $f_1=5$, các $f_n$ đều lẻ nên $f_n \equiv 5+2=7 (mod 10)$