MỘT SỐ DẠNG TOÁN LIÊN QUAN ĐẾN BỒI DƯỠNG HỌC SINH GIỎI MÁY TÍNH BỎ TÚI
PHẦN I: SỐ HỌC
I. QUY NẠP TOÁN HỌC:
1. Nguyên lý quy nạp toán học:
* Bài toán: Chứng minh P(n) đúng với mọi n.
* Phương pháp:
Bước 1: Thử xem khi n=1 hoặc n=2 thì các P(n) tương ứng có đúng không?
Bước 2: ( Bước giả thiết quy nạp)
Giả sử P(k) đúng.
Bước 3: Dùng bước 2 và các phép biến đổi toán học để chứng minh P(k+1) đúng.
Kết luận P(n) đúng với mọi n là số tự nhiên.
2. Các khái niện cơ bản:
a. Giai thừa: , , ,
( Tích các số từ 1 đến n).
b. Tổ hợp: ( )
* Các tính chất:
+
+
+
+ Các là các hệ số trong khai triển .
+ Tam giác Pascal:
+ Hằng đẳng thức:
+ Cho x=y=1, ta được:
+ Cho x=1, y=-1, ta được:
II. SỐ NGUYÊN:
1. Số nguyên tố:
a. Định nghĩa:
Số nguyên tố là số chỉ có hai ước số 1 và chính nó hay số chỉ chia hết cho hai số là 1 và chính nó thì được gọi là số nguyên tố.
Các số tự nhiên lớn hơn 1 và không phải là số nguyên tố thì được gọi là hợp số.
b. Tính chất:
+ Mọi số tự nhiên lớn hơn 1 đều có ước là số nguyên tố.
+ Có vô hạn số nguyên tố.
+ Nếu n là hợp số thì n có ước nguyên tố không vượt quá .
* Cách kiểm tra một số là số nguyên tố: (chỉ áp dụng cho các số tương đối nhỏ).
+ Xem số đó có chia hết cho hai không.
+ Ta gọi số đó là P, ta lập quy trình bấm phím như sau:
Gán D=3, P/D : D=D+2.
Ấn dấu bằng liên tục cho đến khi D thì dừng.
Nếu kết quả của các phép chia P/D là các số không nguyên, thì P là số nguyên tố
2. Ước số chung, bội số chung:
a. Định nghĩa: Cho a,b là hai số tự nhiên.
* k được gọi là ước số chung của a và b khi và chỉ khi k là ước số của a và của b.
Số k lớn nhất ở trên gọi là ước chung lớn nhất của a và b, kí hiệu là: (a,b).
* n được gọi là bội số chung của a và b khi và chỉ khi n là bội số của a lẫn b.
Số n khác không nhỏ nhất được gọi là bội số chung nhỏ nhất của a và b, kí hiệu: [a,b].
* Nếu (a,b)=1 thì ta nói a, b nguyên tố cùng nhau.
b. Tính chất:
+ (a,b).[a,b]=ab.
+ (a,b)=(a-b,b)=(a+b,b)=(a-kb,b).
c. Các kí hiệu về số:
+ Số có chữ số, được kí hiệu là: (2 chữ số), (3 chữ số), (4 chữ số),…
+ Phần nguyên của số x là số nguyên lớn nhất không lớn hơn x, kí hiệu:
III. ĐỒNG DƯ:
1. Định nghĩa:
( a đồng dư b theo modun p ).
( Hay a và b khi chia cho p có cùng số dư)
2. Tính chất:
+ Hai số tự nhiên a và b chia cho p có cùng số dư thì hay .
+ .
+ .
+ .
+ .
+ .
+ .
+ .
3. Các định lý:
a. Định lý Fermat: Cho a,n là hai số tự nhiên nguyên tố cùng nhau. Khi đó ta có:
* Nếu lấy n=p là một số nguyên tố, khi đó . Nên ta có:
* Ở đây (n) là số các số tự nhiên bé hơn n và nguyên tố cùng nhau với n.
* Công thức tính (n) : Nếu thì (n)=.
Ví dụ: (10)==4.
nguon VI OLET
