LÝ EULER , ĐỊNH LÝ FERMAT
1.Định lý Fermat : Chắc hẳn rằng các bạn đã từng gặp bài toán sau :
Chứng minh rằng với mọi số nguyên n:
a)$\large n^2-n$ chia hết cho 2
b)$\large n^3-n$ chia hết cho 3
c)$\large n^5-n$ chia hết cho 5
Bài toán này có thể giải được bằng cách phân tích $\large n^2-n , n^3-n , n^5-n$ ra thừa số
a) $\large n^2 - n = n(n-1)$ . Trong hai số nguyên liên tiếp $\large n-1 , n$ bao giờ cũng có một số chia hết cho 2.
b)$\large n^3-n = n(n-1)(n+1)$ . Trong ba số nguyên liên tiếp $ \large n-1, n , n+1$ bao giờ cũng có một số chia hết cho 3
c)$\large n^5-n = n(n-1)(n+1)(n^2+1)$
Nếu$ \large n$ chia hết cho 5 thì $\large n^5-n$ chia hết cho 5
Nếu$ \large n$ không chia hết cho 5 , thì $\large n$ có dạng $\large 5k \pm 1$ hoặc $\large 5k \pm 2$ trong ba số $\large n-1 , n+1 , n$ luôn có một số chia hết cho 5
- với $\large n = 5k+1$ thì $\large n-1 = 5k $, chia hết cho 5
- với $\large n = 5k -1$ thì $\large n+1 = 5k $, chia hết cho 5
- với $\large n = 5k \pm 2$ thì $\large n^2 = 25k \pm 20k +4$ do đó $\large n^2 + 1 = 25k^2 \pm 20k +5$ , chia hết cho 5
Ta chú ý rằng nếu như $\large 2|n^2-n ; 3|n^3-n ; 5| n^5-n$ với mọi số nguyên $\large n$ , thì $\large n^4- n$ không phải luôn chia hết cho 4 ( với $\large n=2$ , ta có $\large 2^4-2 =14 $không chia hết cho 4 )
Các số $ 2,3,5 $là các số nguyên tố và bài tập ta vừa giải là trường hợp riêng của định lý sau đây :
Định lý Fermat ( Phec-ma) Nếu$ \large p$ là số nguyên tố thì $\large n^{p} \equiv n ( mod p ) $
$(\large n^p - n $ chia hết cho $\large p$ ) với mọi số nguyên $\large n$
Chứng minh : Nếu$ \large n$ chia hết cho $\large p$ thì rõ ràng $\large n^{p} \equiv n (mod p )$
Nếu $\large n$ không chia hết cho $\large p$ thì $\large 2n,3n ,... , (p-1)n$ đều là không chia hết cho $\large p$ , nghĩa là :
$\large n \equiv a_{1} (mod p )$ với $\large 1 \leq a_{1} \leq p-1$
$\large 2n \equiv a_{2} (mod p )$ với $1 \leq a_{2} \leq p-1$
....
$\large (p-1)n \equiv a_{p-1} (mod p )$ với $1 \leq a_{p-1} \leq p-1$
$\large p-1$ số$ \large a_{1} , a_{2} .... , a_{p-1}$ (mỗi số lấy một trong các giá trị từ $\large 1$ đến $\large p-1$ là đôi một khác nhau , bởi vì nếu có hai số nào bằng nhau , thí dụ $\large a_{k} = a_{h} (k]h)$ thì từ hai đồng dư thức trên đây mà vế phải là $\large a_{k}$ và $\large a_{h}$ , ta sẽ có $\large kn \equiv hn (mod p )$ do đó $\large (k-h)n \equiv 0 (mod p)$ , trong đó $\large 1 \leq k-h \leq p-1$
$\large \Rightarrow n$ chia hết cho $\large p$ trái với giả thiết
Nếu$ \large p-1 $ số $\large a_{1} , a_{2} ,... , a_{p-1}$ đôi một khác nhau mà mỗi số lại lấy giá trị từ $\large 1$ đến $\large p-1$ thì tích của $\large p-1$ số đó phải bằng tích của các số từ $ \large 1$ đến $\large p-1 $:
$\large a_{1}a_{2}....a_{p-1}=1.2.3.....(p-1) $
Nhân từng vế $\large p-1 $đồng dư thức trên ta được :
$\large n.2n.3n.....(p-1}n \equiv a_{1}a_{2}....a_{p-1} (mod p ) $
$\large n.2n.3n.....(p-1}n \equiv 1.2.3.....(p-1) (mod p ) $
$\large 1.2.3.....(p-1).n^{p-1} \equiv 1.2.3....(p-1) (mod p ) $
Chia hai vế của đồng dư thức cho tích$ \large 1.2.3....(p-1)$ nguyên tố với $\large p$ , và được :
$\large n^{p-1} \equiv 1 (mod p ) $
Từ đó : $\large n^p \equiv n (mod p) $
2.Định lý Euler : Euler đã mở rộng định lý
Fermat cho trường hợp modun m bất kỳ và có định lý sau đây :
$\large m$ là số nguyên dương gọi $\large \gamma (m)$ là số các số bé hơn $\large m$ và nguyên tố cùng nhau với $\large m , \gamma (m)$ được gọi là hàm Euler
Công thức tính $\large \gamma (m)$ . Phân tích ra thừa số nguyên tố :
$\large m=p_{1}^{\alpha_{1}}.p_{2}^{\alpha_{2}}.......p_{k}^{\alpha_{k}}$
$\large \gamma (m) = m(1-\dfrac{1}{p_{1}})(1-\dfrac{1}{p_{2}}).....(1-\dfrac{1}{p_{k}})$
Định lý Euler : Với $\large (a,m)=1$ thì $\large a^{\gamma (m)} \equiv 1 (mod m)$
Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 14-05-2009 - 13:26
