chứng minh tồn tại dãy số nguyên thỏa mãn điều kiện

skater · 07-12-2007, 06:06 PM

cho dãy $a_1, a_2,.., a_n $ nguyên và ko có số nào chia hết cho $m^{n-1}. $Chứng minh tồn tại bộ số nguyên $b_1, b_2,.. b_n $ ko đồng thời bằng 0 sao cho $|b_i| <m $ và $b_1a_1+b_2a_2+...+b_na_n $ chia hết cho $m^n $

dong1919 · 07-12-2007, 07:58 PM

[Only registered and activated users can see links. ]
Có bên này rồi mà Lộc , hình như đây là cách giải ngắn nhất ( cũng có thể là duy nhất) của bài này

modular · 07-12-2007, 08:03 PM

Bài này là IMO Shortlist năm 2002, bài N5.
[Only registered and activated users can see links. ]

skater · 08-12-2007, 05:02 PM

vấn đề là bài này được giải theo số phức, mà đến giờ mình vẫn chưa bít số phức nên có đọc đoạn sau mấy lần cũng ko hiểu. Chẳng lẽ nếu ko dùng số phức thì đây là bài toán cụt chăng???

skater · 08-12-2007, 09:45 PM

các anh em trên diễn đàn quan tâm bài này tí được ko, đừng thấy dẫn link mà phớt lờ đi. Thử làm xem, mình đã làm mất nhìu thời gian rùi mà ko đc

fool90 · 09-12-2007, 12:30 AM

Về sơ lược lời giải như sau.
Bổ đề .Với mọi $k=m^n $,tồn tại $x $ nguyen dương ,$p $nguyên tố sao cho $k $ là bậc của $x mod p $.

Xét $(b_1;b_2...b_n) $ chạy trên $[0,(m-1)]^n -(0,0,....,0) $, khi đó cho ta $ m^n-1 $ tổng $S(b_1;b_2,...b_n)=\sum\limit_{i=1}^{n} b_i a_i $
*)nếu tồn tại 2 tổng đồng dư mod $m^n $ , giả sử là $S(c_1;c_2;..c_n) =S(d_1,d_2,....d_n) ( mod m^n) $khi đó $S(c_1-d_1,c_2-d_2,..c_n-d_n) \vdots m^n \Rightarrow $ dpcm.
*)bây giờ giả sử không tồn tại 2 tổng nào đồng dư với nhau ,và không có tổng nào chia hết cho m^n
Khi đó rõ ràng $S(b_1,b_2,....b_n) $ lập thành một thặng dư khuyết 0 mod $m^n. $
Xét đa thức$ P(x)=\prod\limits_{i=1}^{n} (1+x^{a_1} +....+x^{a_1^(m-1)}
=\prod\limits_{i=1}^{n} \frac{x^{m.a_i}-1}{x^{a_i-1}}=A(X) $
Với$ A(x)=\sum x^{a_1.b_1+a_2.b_2+....+a_n.b_n} $ (khi $(b_1.b_2,,,....b_n) $ chạy trên $[0,(m-1)]^n- (0,0,...0) $
Chọn a nguyên dương ,p nguyên tố sao cho$ m^n $ là bậc của a mod p.
Do đó $a^{m^n} \equiv 1 (mod p) $
chú ý rằng khi ($b_1;b_2;....b_n) $ chạy trên $[0,(m-1)]^n -(0,0,...0) \ \ \Rightarrow S(b_1;b_2;....b_n) $ là thặng dư khuyết 0 mod$ m^n $
nên $A(a)\equiv \sum\limits_{i=1}^{m^n-1} a^i =\frac{a^{m^n}-1 }{a-1} \vdots p $
nên $P(a) \vdots m^n \Rightarrow \prod\limits_{i=1}^{n} \frac{x^{m.a_i}-1}{a^{a_i-1}} \vdots p $
=> tồn tại i sao cho $\frac{x^{m.a_i}-1}{x^{a_i-1}} \vdots p $
=> tồn tại i : $a^{m.a_i } -1 \vdots p $
=> tồn tại i:$ m.a_i \vdots m^n $ ( do $m^n $là bậc của a mod p)
=> $a_i \vdots m^{n-1} $( vô lí)
Vậy tồn tại $(b_1,b_2,....b_n) $ sao cho $a_1.b_1+...+a_n.b_n \vdots m^n $

From psquang_pbc Tích =\prod ông anh ạ

fool90 · 09-12-2007, 12:41 AM

Ở đây mình đã dùng một biến đổi so với lời giải phức ! hiện mình đang tìm hiểu sâu về vấn đề này ,mong dc sự giúp đỡ bằng cácg góp ý kiến với bổ đề sau:
Chứng minh rằng mọi k nguyên dương ,tồn tại a nguyên dương ,p nguyên tố , sao cho k là bậc của a mod p.

n.t.tuan · 09-12-2007, 07:05 PM

Để thày giúp Thực nhé!
Với mỗi số nguyên dương k>1, lấy p là số nguyên tố để p-1=kn, điều này làm được theo Định lý Dirichlet. Sau đó chọn phần tử a có bậc p-1, thì phần tử $a^n $ sẽ có bậc k.

skater · 09-12-2007, 08:43 PM

Định lí Đrichlet là như thế nào hả anh??

anh phát biểu định lí đó được ko??

n.t.tuan · 10-12-2007, 12:22 AM

Một cấp số cộng với số đầu và công sai là các số nguyên dương nguyên tố cùng nhau chứa vô hạn các số nguyên tố.

P/S: Đừng post hai bài quá gần nhau trong một topic.

skater · 10-12-2007, 08:46 PM

Trích:

Nguyên văn bởi n.t.tuan

Để thày giúp Thực nhé!
Với mỗi số nguyên dương k>1, lấy p là số nguyên tố để p-1=kn, điều này làm được theo Định lý Dirichlet. Sau đó chọn phần tử a có bậc p-1, thì phần tử $a^n $ sẽ có bậc k.

phần tử $a^n $ thuộc cấp số cộng à thầy

n.t.tuan · 10-12-2007, 08:54 PM

Không hiểu chú hỏi cái gì? Ý anh nói là áp dụng Định lý Dirichlet cho cấp số cộng
{1+kn|n=0,1,...}.

fool90 · 12-12-2007, 05:15 PM

Mời các bạn xem ở đây để giải đáp những câu hỏi của mình và chứng minh 1 định lí có tầm ứng dụng rất cao (

) -gọi là bổ đề CNN.
[Only registered and activated users can see links. ]

07-12-2007, 06:06 PM	#1
skater +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Vinh, Nghệ An Bài gởi: 85 Thanks: 0 Thanked 0 Times in 0 Posts	chứng minh tồn tại dãy số nguyên thỏa mãn điều kiện cho dãy $a_1, a_2,.., a_n $ nguyên và ko có số nào chia hết cho $m^{n-1}. $Chứng minh tồn tại bộ số nguyên $b_1, b_2,.. b_n $ ko đồng thời bằng 0 sao cho $\|b_i\| <m $ và $b_1a_1+b_2a_2+...+b_na_n $ chia hết cho $m^n $ __________________ lonely thay đổi nội dung bởi: skater, 07-12-2007 lúc 07:06 PM

08-12-2007, 05:02 PM	#4
skater +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Vinh, Nghệ An Bài gởi: 85 Thanks: 0 Thanked 0 Times in 0 Posts	vấn đề là bài này được giải theo số phức, mà đến giờ mình vẫn chưa bít số phức nên có đọc đoạn sau mấy lần cũng ko hiểu. Chẳng lẽ nếu ko dùng số phức thì đây là bài toán cụt chăng??? __________________ lonely

08-12-2007, 09:45 PM	#5
skater +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Vinh, Nghệ An Bài gởi: 85 Thanks: 0 Thanked 0 Times in 0 Posts	các anh em trên diễn đàn quan tâm bài này tí được ko, đừng thấy dẫn link mà phớt lờ đi. Thử làm xem, mình đã làm mất nhìu thời gian rùi mà ko đc __________________ lonely

09-12-2007, 12:30 AM	#6
fool90 +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Ninh Bình Bài gởi: 49 Thanks: 1 Thanked 13 Times in 4 Posts	Về sơ lược lời giải như sau. Bổ đề .Với mọi $k=m^n $,tồn tại $x $ nguyen dương ,$p $nguyên tố sao cho $k $ là bậc của $x mod p $. Xét $(b_1;b_2...b_n) $ chạy trên $[0,(m-1)]^n -(0,0,....,0) $, khi đó cho ta $ m^n-1 $ tổng $S(b_1;b_2,...b_n)=\sum\limit_{i=1}^{n} b_i a_i $ )nếu tồn tại 2 tổng đồng dư mod $m^n $ , giả sử là $S(c_1;c_2;..c_n) =S(d_1,d_2,....d_n) ( mod m^n) $khi đó $S(c_1-d_1,c_2-d_2,..c_n-d_n) \vdots m^n \Rightarrow $ dpcm. )bây giờ giả sử không tồn tại 2 tổng nào đồng dư với nhau ,và không có tổng nào chia hết cho m^n Khi đó rõ ràng $S(b_1,b_2,....b_n) $ lập thành một thặng dư khuyết 0 mod $m^n. $ Xét đa thức$ P(x)=\prod\limits_{i=1}^{n} (1+x^{a_1} +....+x^{a_1^(m-1)} =\prod\limits_{i=1}^{n} \frac{x^{m.a_i}-1}{x^{a_i-1}}=A(X) $ Với$ A(x)=\sum x^{a_1.b_1+a_2.b_2+....+a_n.b_n} $ (khi $(b_1.b_2,,,....b_n) $ chạy trên $[0,(m-1)]^n- (0,0,...0) $ Chọn a nguyên dương ,p nguyên tố sao cho$ m^n $ là bậc của a mod p. Do đó $a^{m^n} \equiv 1 (mod p) $ chú ý rằng khi ($b_1;b_2;....b_n) $ chạy trên $[0,(m-1)]^n -(0,0,...0) \ \ \Rightarrow S(b_1;b_2;....b_n) $ là thặng dư khuyết 0 mod$ m^n $ nên $A(a)\equiv \sum\limits_{i=1}^{m^n-1} a^i =\frac{a^{m^n}-1 }{a-1} \vdots p $ nên $P(a) \vdots m^n \Rightarrow \prod\limits_{i=1}^{n} \frac{x^{m.a_i}-1}{a^{a_i-1}} \vdots p $ => tồn tại i sao cho $\frac{x^{m.a_i}-1}{x^{a_i-1}} \vdots p $ => tồn tại i : $a^{m.a_i } -1 \vdots p $ => tồn tại i:$ m.a_i \vdots m^n $ ( do $m^n $là bậc của a mod p) => $a_i \vdots m^{n-1} $( vô lí) Vậy tồn tại $(b_1,b_2,....b_n) $ sao cho $a_1.b_1+...+a_n.b_n \vdots m^n $ From psquang_pbc Tích =\prod ông anh ạ thay đổi nội dung bởi: psquang_pbc, 09-12-2007 lúc 07:47 PM

09-12-2007, 07:05 PM	#8
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Để thày giúp Thực nhé! Với mỗi số nguyên dương k>1, lấy p là số nguyên tố để p-1=kn, điều này làm được theo Định lý Dirichlet. Sau đó chọn phần tử a có bậc p-1, thì phần tử $a^n $ sẽ có bậc k. __________________ T.

07-12-2007, 07:58 PM	#2
dong1919 Sư tổ Kim Dung-CÁI BANG Tham gia ngày: Nov 2007 Đến từ: A1K35PBC-Nghệ An Bài gởi: 291 Thanks: 0 Thanked 33 Times in 23 Posts	[Only registered and activated users can see links. ] Có bên này rồi mà Lộc , hình như đây là cách giải ngắn nhất ( cũng có thể là duy nhất) của bài này

07-12-2007, 08:03 PM	#3
modular B&S-D Tham gia ngày: Nov 2007 Bài gởi: 589 Thanks: 395 Thanked 147 Times in 65 Posts	Bài này là IMO Shortlist năm 2002, bài N5. [Only registered and activated users can see links. ]

09-12-2007, 12:41 AM	#7
fool90 +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Ninh Bình Bài gởi: 49 Thanks: 1 Thanked 13 Times in 4 Posts	Ở đây mình đã dùng một biến đổi so với lời giải phức ! hiện mình đang tìm hiểu sâu về vấn đề này ,mong dc sự giúp đỡ bằng cácg góp ý kiến với bổ đề sau: Chứng minh rằng mọi k nguyên dương ,tồn tại a nguyên dương ,p nguyên tố , sao cho k là bậc của a mod p.

09-12-2007, 08:43 PM	#9
skater +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Vinh, Nghệ An Bài gởi: 85 Thanks: 0 Thanked 0 Times in 0 Posts	Định lí Đrichlet là như thế nào hả anh?? anh phát biểu định lí đó được ko?? __________________ lonely

10-12-2007, 12:22 AM	#10
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Một cấp số cộng với số đầu và công sai là các số nguyên dương nguyên tố cùng nhau chứa vô hạn các số nguyên tố. P/S: Đừng post hai bài quá gần nhau trong một topic. __________________ T.

10-12-2007, 08:54 PM	#12
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Không hiểu chú hỏi cái gì? Ý anh nói là áp dụng Định lý Dirichlet cho cấp số cộng {1+kn\|n=0,1,...}. __________________ T.

12-12-2007, 05:15 PM	#13
fool90 +Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Ninh Bình Bài gởi: 49 Thanks: 1 Thanked 13 Times in 4 Posts	Mời các bạn xem ở đây để giải đáp những câu hỏi của mình và chứng minh 1 định lí có tầm ứng dụng rất cao () -gọi là bổ đề CNN. [Only registered and activated users can see links. ]