Chủ đề này có 25 trả lời

[kid tomboy]

Chào các đồng môn huynh đệ (tại Kid còn nhỏ nên xưng vậy cho...khiêm tốn), sau đây là một số kiến thức về phép đồng dư, hay còn gọi là đồng dư thức . Đồng dư thức là phép toán được ứng dụng rất nhiều trong các loại bài chia hết.

A_ĐỒNG DƯ THỨC

1_Định nghĩa:

Cho m là số nguyên dương. Hai số nguyên a và b được gọi là đồng dư với nhau theo module m nếu hiệu a - b m hay ( m\a - b)

Ký hiệu a b (mod m) được gọi là một đồng dư thức.
Nếu a - b không chia hết cho m, ta viết (chài ký hiệu này ko có sẵn nên phải tự mò ra đấy mệt wa' )

2_Các ví dụ:

3 -1 (mod 4)
5 17 (mod 6)
18 0 (mod 6)
Điều kiện a 0 (mod m) nghĩa là a m hay m\a

3_Một số tính chất cơ bản:

Tính chất 1:

Với mọi số nguyên a, ta có: a a (mod m)

Tính chất 2:

a b (mod m) => b a (mod m)

Bài viết đã được chỉnh sửa nội dung bởi kid tomboy: 09-04-2006 - 18:33

[kid tomboy]

T/C 3:

a b (mod m), b = c (mod m) a c (mod m)

Chứng minh:
a b(mod m) => m\(a-b)
b c (mod m) => m\(b-c)
Vì a - c= (a-b) + (b - c), suy ra: m\(a - c)

T/C4: a b(mod m), c d (mod m ) a + c=b + d (mod m)
Chứng minh:
a b=m.
c d (mod m) c - d=m. (, Z)
(a+c) - (b+d)=m.( + ) m\ac - bd



T/C 5:

a b (mod m), c d(mod m) ac bd (mod m)
Chứng minh:
Theo tính chất 4 ta có:
a - b=m. a = b + m.
c - d=m. c = d + m.

Nhân từng vế hai ĐT ta có:

).(d + m.)
ac - bd= m.(b. + d. + m.( + ) m\ac - bd

Bài viết đã được chỉnh sửa nội dung bởi kid tomboy: 09-04-2006 - 18:31

[kid tomboy]

Nhận xét:

1.Nếu a 1(mod 2) và b 1(mod 2) thì
a+b 2(mod 2), bà 2 0(mod 2) suy ra:
a+b 0(mod 2), còn a.b 1(mod 2)
Điều này có nghĩa : Tổng của hai số lẻ là một số chẵn; Tích của hai số lẻ là một số lẻ

2_Nếu a 3(mod 7) 9(mod 7) 2(mod 7)

Có nghĩa: Nếu một số chia cho 7 dư 3 thì bình phương số đó chia 7 dư 2.

Bài viết đã được chỉnh sửa nội dung bởi kid tomboy: 09-04-2006 - 18:30

[kid tomboy]

Các hệ quả của tính chất 4 và 5:

1. (mod m) ,
(mod m).... (mod m)

+ + +... + + +...

2_ (mod m) , (mod m)

. . .... . . . ...

3_a b(mod m) (mod m), với mọi n N


Chú ý:
1_Chia hai vế cho một đẳng thức, nói chung là không được.
VD: 2 12(mod 10) nhưng 1 6(mod 10)

2_a 0 (mod m), b 0 (mod m) nhưng ab có thể đồng dư với 0 theo module m. Chẳng hạn : 2 0 (mod 10) ; 5 0 (mod 10) nhưng 2.5 = 10 0 (mod 10)

Phép chia hai vế đồng dư thức đòi hỏi phải kèm thêm một số điều kiện

P/S: Còn nữa khi khác post tiếp, bây h ra xem hoạt hình cái đã (LA với TEX!!! MỆT!!! @_@ )

Bài viết đã được chỉnh sửa nội dung bởi kid tomboy: 09-04-2006 - 18:35

[hoang tuan anh]

mẹ cha ơi chăm dã man a.!!!
bổ xung thêm fecma nhỏ :

n nguyên tố
và 1 số bài tập ứng dụng
1)cm: 42p với p nguyên tố >3
2)cho a và b là 2 số nguyên tố lớn hơn 7
Cm chia hết cho 580608
3) cmr
24(n N)
4)cmr
- 100

Bài viết đã được chỉnh sửa nội dung bởi hoang tuan anh: 13-04-2006 - 20:25

[kid tomboy]

À nhắc đến Phẹc ma mới nhớ

Luôn cho nóng nè:

Định lý lớn Fermat (hay còn gọi là giả thuyết fermat): Phương trình (m N, m 3) không có nghiệm nguyên.

Định lý nhỏ Fermat: Giả sử p là một số nguyên tố bất kỳ, khi đố với mọi số tự nhiên n , ta có ( - n) p

**BT ứng dụng(rất dễ):
Tìm số dư trong phép chia - 1 cho 9

Bài viết đã được chỉnh sửa nội dung bởi kid tomboy: 09-04-2006 - 19:33

[fecma21]

đã nhắc tới fecma trong đồng dư thì cũng phải đề cập tới EULER và WILSON chứ ?

định lí EULER : cho số nguyên n ; và số nguyên a thỏa (a,n) = 1 ;

1 số khi chia cho n sẽ có số dư thuộc tập hợp S= {1,2,.... n};

gọi m là số các số nguyên tố cùng nhau với n trong tập S .

ĐỊNH LÍ EULER : TA CÓ : 1 (mod n )

ĐẶC BIỆT : khi n=p là số nguyên tố thì thấy m=p-1;

=> a (mod n);

có thể thấy định lí fecma bé có thể cm trực tiếp => từ EULER .
CM EULER CÓ 3 DÒNG THÔI NHÉ /

ĐỊNH LÝ WILSON : p nguyên tố .CMR : 1.2.3...(p-1) (-1) (mod p)

CM BÀI NÀY KHÁ HAY . CÓ 1 BÀI THUỘC TÍNH CHẤT NHƯ SAU

CHO p nguyên tố , a nguyên , CMR nếu -1 p

THÌ -1

[hungnd]

bài của bác fecma21 thì em chỉ chứng minh được với p nguyên tố lẻ thui.
Đó là, với p nguyên tố lẻ ta có ngay http://dientuvietnam...tex.cgi?a^{p-1} chính phương.
Do http://dientuvietnam...mimetex.cgi?p^2
Còn nếu p nguyên tố chẵn thì chỉ có thẻ là http://dientuvietnam...mimetex.cgi?p^2

Bài viết đã được chỉnh sửa nội dung bởi hung_spider_man: 08-08-2006 - 21:31

[NkMAsTeR]

đã nhắc tới fecma trong đồng dư thì cũng phải đề cập tới EULER và WILSON chứ ?

định lí EULER : cho số nguyên n ; và số nguyên a thỏa  (a,n) = 1 ;

1 số khi chia cho n sẽ có số dư thuộc tập hợp S= {1,2,.... n};

gọi m là số các số nguyên tố cùng nhau với n trong tập S .

ĐỊNH LÍ EULER  : TA CÓ :  1      (mod n )

ĐẶC BIỆT : khi n=p là số nguyên tố thì thấy m=p-1;

=>     a          (mod n);

có thể thấy định lí fecma bé có thể cm trực tiếp => từ EULER .
CM EULER CÓ 3 DÒNG THÔI NHÉ /

ĐỊNH LÝ WILSON : p nguyên tố  .CMR :    1.2.3...(p-1) (-1) (mod p)

CM BÀI NÀY KHÁ HAY . CÓ 1 BÀI THUỘC TÍNH CHẤT NHƯ SAU

CHO p nguyên tố  , a nguyên , CMR  nếu -1   p

                          THÌ  -1

Cái này là hay vậy ạ?

[hoang tuan anh]

[quote name='fecma21' date='Jun 26 2006, 03:23 PM'] đã nhắc tới fecma trong đồng dư thì cũng phải đề cập tới EULER và WILSON chứ ?

định lí EULER : cho số nguyên n ; và số nguyên a thỏa (a,n) = 1 ;

1 số khi chia cho n sẽ có số dư thuộc tập hợp S= {1,2,.... n};

gọi m là số các số nguyên tố cùng nhau với n trong tập S .

ĐỊNH LÍ EULER : TA CÓ : http://dientuvietnam...gi?a^{p}-1=(a-1)(a^{p-1}+a^{p-2}+..+a+1)
có http://dientuvietnam... a^{p-2} .. a 1) p(vì có p số hạng)
do đó =>dpcm

[fecma21]

ĐỊNH LÝ WILSON : p nguyên tố .CMR : 1.2.3...(p-1) (-1) (mod p)

ừ thì anh bảo bài ấy dễ mà ;

CM CÁI NÀY ĐI

[hoang tuan anh]

thực ra định lý wwilson là hệ quả của cái sau

ứng dụng định lý euler
với mọi p ng/tố xét đa thức
http://dientuvietnam...mimetex.cgi?f(x)=(x-1)(x-2)...(x-p+1)-x^{p-1}+1
cmr: tất cả các hệ số nguyên của đa thức đều p

để cm điều trên hãy sử dụng định lý lagrange

[hungnd]

Em được học cách chứng minh định lí Wilson bằng phương pháp:
Xét bổ đề:Nghịch đảo của a theo modulo m tồn tại và duy nhất nếu và chỉ nếu (a;m)=1

Chứng minh sơ sơ định lí Wilson:
Xét (p-1)! p 2(vì nếu p= 2 thì sẽ không có cặp nghịch đảo nào hết mà chỉ có duy nhất 1 1 (mod 2)), kết quả sau đây có được là nhờ nhóm từng cặp nghịch đảo ấy với nhau: 1.2.3.4.....(p-1) 1.1.1...(p-1) -1 (mod p) ĐPCM

Bài viết đã được chỉnh sửa nội dung bởi hung_spider_man: 11-08-2006 - 18:03

[mathmath]

hic mấy cái bài áp dụng của hta chờ mãi mà không thấy ai lên tiếng thôi thì mình lên tiếng(tức quá vì không có cuốn chuyên đề số của hta-nhớ mặt nhau đấy)
http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Rightarrow\3^p\equiv\3(modp)
vàhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?2^p\equiv\2(modp)
suy ra http://dientuvietnam....cgi?3^p-(2^p 1)\equiv\3^p-3\equiv\3(mod3)và http://dientuvietnam...etex.cgi?(3^p-1)-2^p\equiv\2(mod2)
euler tiếp để cm chia hết cho 7
suy ra dpcm

Bài viết đã được chỉnh sửa nội dung bởi mathmath: 11-08-2006 - 22:27

[fecma21]

THÊM BÀI NỮA :

1/ cmr số 895 không thể viết thành tổng 3 số chính phương ;

2/ cm pt đồng dư (mod p ) không có quá n nghiệm với p nguyên tố ;

[hoang tuan anh]

1 sai sót ngớ ngẩn
làm lại
tổng 3 số cp có dạng
lần lượt xét các th số dư cho 8 của 3 số trên (chú ý rằng scp chia 8 dư 0;1;4) ta có dpcm
bài 2 cần xem lại đề

Bài viết đã được chỉnh sửa nội dung bởi hoang tuan anh: 13-08-2006 - 13:00

[hungnd]

895 chia hết cho 5 nên bắt buộc 3 số chính phương đó đồng thời chia hết cho 5
dẫn đến 895  25 dẫn đến vô lý

bài 2 cần xem lại đề

Anh hãy xét số 30 5
http://dientuvietnam...2 2^2 5^2.Nhưng đâu phải cả 3 số chính phương đó đều chia hết cho 5 .Mong anh chỉ rõ hơn cái

Bài viết đã được chỉnh sửa nội dung bởi hung_spider_man: 13-08-2006 - 12:48

[fecma21]

THÊM BÀI NỮA :

1/ cmr số 895 không thể viết thành tổng 3 số chính phương ;

2/ cm pt đồng dư (mod p ) không có quá n nghiệm với p nguyên tố ;

thực ra cái bài 1 là : số n=8.k+7 không thể viết thành tổng 3 số chính phương . nhưng thế thì lộ mất đề rồi .

còn bai2 hta bảo anh sai cái gì đấy ? đúng đề rồi

[hoang tuan anh]

THÊM BÀI NỮA :

1/ cmr số 895 không thể viết thành tổng 3 số chính phương ;

2/ cm pt đồng dư (mod p ) không có quá n nghiệm với p nguyên tố ;

thực ra cái bài 1 là : số n=8.k+7 không thể viết thành tổng 3 số chính phương . nhưng thế thì lộ mất đề rồi .

còn bai2 hta bảo anh sai cái gì đấy ? đúng đề rồi

anh ơi , em tưởng định lý lagrange phát biểu phải cần thêm 1 số điều kiện chứ

[fecma21]

KHÔNG HỀ THIẾU ĐK ĐÂU . ĐÚNG MÀ

bổ đề 1 : với pt đồng dư bậc n ( mod p ) thì có thể coi ; (cm dễ mà )

bổ đề 2 : pt đồng dư bậc n > p có thể chuyển về pt bậc n p