tailieunhanh - Lý thuyết số học

Định lý về phép chia: Cho a,b là các số nguyên tuỳ ý và b khác 0, khi đó có hai số nguyên q, r duy nhất sao cho: a = bq +r với 0 | Lý thuyết số học 1. Định lý về phép chia: Cho a,b là các số nguyên tuỳ ý và b khác 0, khi đó có hai số nguyên q, r duy nhất sao cho: a = bq +r với 0 có số nguyên q sao cho a = bq 2. Nguyên tắc Dirichlet : nếu đem nk+1 vật xếp vào n ngăn kéo thì có ít nhất một ngăn kéo chứa từ k+1 vật trở lên 3. Định lý Fermat: với p là số nguyên tố ta có a^p đồng dư với a ( mod p) đặc biệt nếu (a,p) = 1 thì a^(p-1) đồng dư với 1 ( mod p) 4. Nếu (a,b) = d thì có 2 số nguyên m,n sao cho an + bm = d 5. Mỗi số tự nhiên lớn hơn 1 được phân tích thành tích các thừa số nguyên tố và phân tích là duy nhất nếu không kể đến thứ tự 6. Tập hợp tất cả các số nguyên tố là vô hạn 7. Ước số nguyên tố nhỏ nhất của một hợp số N là một số không vượt quá căn bậc hai của N 8. Định lý Thébault: Nếu một cấp số cộng n số hạng gồm toàn nguyên tố lẻ thì công sai của nó chia hết cho mọi số nguyên tố nhỏ hơn hoặc bằng n 9. Định lý Derichlet: Nếu (a,b) = 1 thì trong các số hạng của cấp số cộng ak +b (k=1,2,.) có vô số số nguyên tố 10. Định lý Tsébusep : Với mọi số nguyên n>1 thì giữa n và 2n luôn có một số nguyên tố. 11. Định lý Lagrange : Mọi số tự nhiên đều có thể phân tích được thành tổng của 4 số nguyên tố Định lý Wilson : p thuộc P, (p-1)! +1 đồng dư với 0 (mod p) ( P là tập hợp số nguyên tố) 12. Định lý Liuvile : Không tồn tại số nguyên tố p > 5 và m thuộc N thoả (p-1)! +1 = p^m 13. THUẬT TOÁN EUCLIT Tìm ước số chung lớn nhất của hai số nguyên với sự trợ giúp của thuật toán nối tiếng từ thời Euclit. Cho hai số nguyên a và b >0. Ta kí hiệu q là thương, còn r là số dư của phép chia a cho b. Khi đó ta có a = bq + r, với b>r> hoặc=0 Nếu r = 0, ta dừng lại. Nếu r > 0, ta chia b cho r và ta nhận được đẳng thức tương tự b=rq1+r1,với r>r1 lớn hơn hoặc = 0 tiếp tục quá trình trên, ta nhận được a=bq+r b=rq1+r r=r1q2+r2 . r(k-2)=r(k-1)qk+rk r(k-1)=rkq(k+1)+r(k+1) --> rk là ước số chung lớn nhất của hai số a và b , tức là rk=(a,b)