L
lapblock
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
ĐIỀU KIỆN
ĐỂ CÓ ĐƯỢC MỘT SỐ NGUYÊN TỐ
mersenne
( Tặng đến các bạn yêu môn số học )
LapBlock
I. §Æt vÊn ®Ò:
❶ Xét chuổi số sau :
U = { un \ n ∈ ℕ ; un = 2n – 1 } = { 0 ; 1 ; 3 ; 7 ; 15; 31; .....}
Ta thấy : u2 = 3 , u3 = 7 , u5 = 31 .....thường là những số nguyên tố .
❷ Bằng nhận định như vậy ! Nhà toán học Mecxen đã đưa ra một giả thiết rằng : << Nếu p∈ ℘ ( p là số nguyên tố ) thì up = 2p- 1 là một số nguyên tố >>.
❸ Từ đó , giả thiết trên được mang tên ông . Sau đó người ta lại thấy rằng với p = 11 thì u11 = 211 – 1 = 2047 = 23 . 89 đây là một bằng chứng hùng hồn cho thấy giả thiết về số nguyên tố Mecxen sai trong trường hợp p=11 .( Nó còn sai trong nhiều trường hợp khác nữa ! ) .
❹ Người ta đã chứng minh được rằng << Nếu un ∈ ℘ thì n ∈ ℘ >> .
Nếu up là một số nguyên tố , người ta gọi Up là số nguyên tố Mecxen .
❺ Vấn đề đặt ra cho chúng ta ở đây là << Số nguyên tố p cần phải có điều kiện gì để cho up là một số nguyên tố Mecxen ? >>
II. Một số bổ đề :
Chúng ta sẽ tìm hiểu một số tính chất của chuổi số U .
❶ Bổ đề 1: << Với mỗi số p∈ ℘ và p> 2 , thì tồn tại một số nhỏ nhất e ∈ℕ+
sao cho ue M p >> .
Ta nhận thấy rằng :
_ Theo định lí Phec-ma nhỏ, ta có 2p-1 ≡ 1 ( mod p )
Þ 2p-1 – 1 ≡ 0 ( mod p ) Þ u( p-1) ≡ 0 ( mod p )
Þ Nếu k = p-1 thì uk M p
Þ Tồn tại một tập hợp những số k ∈ ℕ+ để uk M p
Þ Vì tập hợp những số k ∈ ℕ+ , k > 0 ( bị chặn dưới ) nên theo định lí
Weiestrass thì ∃ e∈ ℕ+, e là nhỏ nhất để ue M p đ.p.c.m.
_ Chú ý : + Dễ thấy rằng 2 < e ≤ ( p-1)
+ << Nếu số nhỏ nhất e ∈ ℕ+ và ue M p thì uke M p >> ( ∀ k ∈ ℕ ).
Thật vậy ! ta dễ dàng chứng minh được điều nầy bằng hằng
đẳng thức : uke = 2ke – 1 = ( 2e)k – 1k
= ( 2e - 1) [( 2e)k-1+ ( 2e)k-2+ ... + (2e) + 1 ]
= ue . [ (2e)k-1 + .......... + 1 ] .
Þ uke M ue và ue M p Þ uke M p đ.p.c.m.
Ngược lại , ta có bổ đề sau :
❷ Bổ đề 2 : << Với mổi số nguyên tố p cho trước, với mọi số n∈ ℕ và e là số tự nhiên nhỏ nhất sao cho un M p và ue M p thì ta có nM e >> .
Giả sử n không chia hết cho số e . Thế thì ∃ k, m ∈ℕ ; 1 ≤ m < e sao cho : n = ke + m
Þ un = 2n - 1 = 2ke+m - 1 Þ ( 2ke+m – 1) M p và (2e – 1 ) M p
Þ {( 2ke+m – 1) - ( 2e – 1 ) } M p Þ (2ke. 2m - 2e ) M p
Þ ( 2ke. 2m - 2m + 2m - 2e ) M p Þ {( 2ke. 2m – 2m) – (2e – 2m)} M p
Þ { 2m(2ke – 1 ) – 2m ( 2e-m – 1 )} M p Þ ( 2m.uke - 2m .u(e-m) ) M p
Theo chú ý ở phần bổ đề 1, vì ue M p nên uke M p Þ 2m uke M p
Þ 2mu(e-m) M p và Ư CLN ( 2m ; p ) = 1 Þ u(e-m) M p
Mà 0 < e-m < e ; nên tồn tại một số tự nhiên (e-m) < e sao cho u(e-m) chia hết cho p .Điều nầy trái với giả thiết rằng e là số tự nhiên nhỏ nhất có tính chất ue M p . Vậy bổ đề 2 đã được chứng minh .
❸ Bổ đề 3 :<< Với mỗi số nguyên tố p∈℘ cho trước, và với ∀ p’ ∈ ℘ ; sao
cho p’ < p thì up không chia hết cho p’ >> .
Thật vậy ! Giả sử up M p’ và ∃ e’ ∈ ℕ+ là nhỏ nhất để cho ue’ M p’ ; theo bổ đề 2 ở trên thì ta suy ra : p M e’ mà e’ ≤ p’-1 < p’ < p Þ e’ = 1 vô lí .Vậy bổ đề 3 đã được chứng minh .
III. Tìm điều kiện cho số nguyên tố Mecxen :
Ở phần trên , ta đã biết rằng luôn ∃ p ∈ ℘ mà up ∉ ℘ ( thí dụ p = 11 ).
Tức là ∃ p’ ; p” ∈ ℘ \ up = p’ p”. Theo bổ đề 3 , ta dễ thấy rằng p nhỏ hơn p’ và p” Û p < p’ , p” .
Theo bổ đề 1 và 3 , ta dễ thấy rằng số p chính là số nhỏ nhất có tính chất up M p’ và up M p” .
Þ up M p’ và u(p’-1) M p’ ( Phec-ma nhỏ ) theo bổ đề 2 thì (p’ –1) M p .
Bằng suy luận tương tự cho p” ta cũng có ( p” – 1 ) M p .
Þ ∃ m,n,k,l ∈ ℕ+ và k,l là số lẽ để;
p’ = 2m p k + 1
p” = 2n p l + 1 ( CT 1 )
Vậy ta có công thức sau :
up = 2p – 1 = (2m pk +1)( 2n pl +1 ) (CT 2 )
❶ Xét các trường hợp sau :
a. Nếu m = n = 1 thì CT 2 trở thành :
up = ( 2pk +1 )( 2pl + 1) = 22 pkpl + 2pk + 2pl + 1
= ( 22pkpl + 2pk + 2pl +2 ) - 1 = 2p – 1 = up
Þ ( 22 pkpl + 2pk +2pl + 2) = 2p
Þ 2(2pkpl + pk + pl + 1 ) = 2p = 2{ 2pkpl + p( k +l ) +1 }
Þ 2p-1 = 2pkpl + p( k +l ) + 1 (chú ý k, l là số lẻ )
= chẵn + chẵn + lẻ
Þ 2p-1 = lẻ Þ vô lí . Vậy trường hợp m = n = 1 không xảy ra .
b. Nếu m , n ≥ 2 : thì công thức 2 trở thành :
2p – 1 = ( 2m pk +1 )( 2n pl + 1 ) = ( 2m pk + 1 ){ (2n pl +2) –1}
= (2m pk +1 ){ 2( 2n-1 pl +1 ) - 1 }
= 2m+1pk( 2n-1pl +1) – 2mpk + 2(2n-1pl +1) - 1
Þ 2p-1 = = lẻ ( vô lí )
Vậy trường hợp nầy m, n ≥ 2 không xảy ra .
Căn cứ vào hai trường hợp trên ta suy ra : trong hai số m,n thì có một
số bằng 1 , còn một số lớn hơn bằng 2.
c. Giả sử m =1 và n ≥ 2 : CT 2 trở thành :
2p – 1 = (2pk +1)( 2n pl +1) với n ≥ 2 ( CT 3 )
Ta biến đổi vế phải như sau :
2p – 1 = ( 2pk +1){ 2( 2n-1 pl + 1) – 1 }
=22pk(2n-1pl +1) + 2(2n-1pl +1) – 2pk –1
Þ 2p = 22pk(2n-1pl +1) + 2(2n-1pl +1) – 2pk
Þ 2p-1 = 2pk(2n-1pl +1) + ( 2n-1pl +1) – pk
Þ 2p-1 = 2pk(2n-1pl +1) + 2n-1pl - ( pk – 1)
Þ 2p-2 = pk( 2n-1pl +1) + 2n-2pl - {( pk – 1) :2}
Þ = pk2n-1 pl + 2n-2pl + pk – {( pk –1): 2 }
Þ = 2n-1pkpl + 2n-2pl + {( pk + 1) : 2}
Þ 2p-2 = 2n-2pl( 2pk +1) + {( pk +1) : 2} ( CT 4 )
Nhận xét :
*Hệ thức trên cho ta những nhận định sau :
~ { ( pk + 1) :2 } có dạng = 2n-2 a ( với a∈ ℕ+, a lẻ ).Nếu không , thì sau khi rút gọn hai vế cho lũy thừa của 2; ta có vế phải của CT 4 là số lẽ , còn vế trái là số chẵn.Như vậy thì không thích hợp !Nên {( pk +1) : 2 } = 2 n- 2 a .
Þ pk +1 = 2 n-1a ( CT 5 )
~ Từ CT4 ta suy ra: 2 ≤ n < p ( CT 6 )
Theo nhận xét trên ,CT4 trở thành :
Þ 2p-2 = 2n-2pl( 2pk +1) + 2n-2 a Þ 2p-2 = 2n-2pl.(2n.a – 1) + 2n-2a
Þ 2p-n = pl( 2na – 1) + a = 2na.pl – pl +a = 2napl – ( pl – a)
Nhận xét : Tương tự như nhận xét vừa qua , ( pl – a) phải có dạng như sau :
Pl – a = 2 n .b ( CT 7 ) Với b ∈ ℕ+ ; b là số lẻ.
Thế thì : 2p-n = 2n apl – 2nb Þ 2p-2n = apl - b = a( 2nb + a) – b
Þ 2p-2n = 2nab + ( a2 – b ) ( CT 8 )
Nhận xét :Tương tự như trên, ( a2 – b ) phải có dạng như sau :
a2 - b = 2 n c ( CT 9 ) với c ∈ ℕ+ ,c là số lẻ.
Thế thì :
Þ 2p-2n = 2n.ab + 2n.c = 2n.( ab + c )
Þ 2p-3n = ab + c ( CT 10 ) Với a,b,c ∈ ℕ+ và a,b,c đều lẻ.
Nhận xét :Điều kiện của số n là n ∈ ℕ+ và 2 ≤ n < ( p – 1) : 3 ( CT 11 )
Ta có thể chứng minh chiều ngược lại để có kết luận như dưới đây .
❷ KẾT LUẬN :
Nếu dùng CT5, CT7 để thay vào CT3 ; ta được kết quả sau :
<< Với mỗi số nguyên tố p, nếu và chỉ nếu tồn tại bốn số a,b,c,n ∈ ℕ +, trong đó a,b,c là các số lẻ thỏa mãn các điều kiện : 1/. ab + c = 2 p-3n
2/. a 2 – b = 2 n c
3/. 2 ≤ n < ( p-1) : 3
thì u p = 2 p - 1 là một hợp số có dạng u p = ( 2 n a – 1).{ 2n( 2 n.b +a) +1} >>.
Với điều kiện nầy, ta có thể phát biểu như sau :
IV. ĐỊNH LÍ NVP:
❶ Định lí : << Với mổi số nguyên tố p cho trước, nếu không tồn tại bốn số a,b,c,n
∈ ℕ +, trong đó a,b,c là các số lẻ thỏa mãn các điều kiện :
1. ab + c = 2 p-3 n
2. a 2 – b = 2 n c
3. 2 ≤ n < (p-1) : 3
thì u p = 2p – 1 là một số nguyên tố Mecxen >>.
ĐỂ CÓ ĐƯỢC MỘT SỐ NGUYÊN TỐ
mersenne
( Tặng đến các bạn yêu môn số học )
LapBlock
I. §Æt vÊn ®Ò:
❶ Xét chuổi số sau :
U = { un \ n ∈ ℕ ; un = 2n – 1 } = { 0 ; 1 ; 3 ; 7 ; 15; 31; .....}
Ta thấy : u2 = 3 , u3 = 7 , u5 = 31 .....thường là những số nguyên tố .
❷ Bằng nhận định như vậy ! Nhà toán học Mecxen đã đưa ra một giả thiết rằng : << Nếu p∈ ℘ ( p là số nguyên tố ) thì up = 2p- 1 là một số nguyên tố >>.
❸ Từ đó , giả thiết trên được mang tên ông . Sau đó người ta lại thấy rằng với p = 11 thì u11 = 211 – 1 = 2047 = 23 . 89 đây là một bằng chứng hùng hồn cho thấy giả thiết về số nguyên tố Mecxen sai trong trường hợp p=11 .( Nó còn sai trong nhiều trường hợp khác nữa ! ) .
❹ Người ta đã chứng minh được rằng << Nếu un ∈ ℘ thì n ∈ ℘ >> .
Nếu up là một số nguyên tố , người ta gọi Up là số nguyên tố Mecxen .
❺ Vấn đề đặt ra cho chúng ta ở đây là << Số nguyên tố p cần phải có điều kiện gì để cho up là một số nguyên tố Mecxen ? >>
II. Một số bổ đề :
Chúng ta sẽ tìm hiểu một số tính chất của chuổi số U .
❶ Bổ đề 1: << Với mỗi số p∈ ℘ và p> 2 , thì tồn tại một số nhỏ nhất e ∈ℕ+
sao cho ue M p >> .
Ta nhận thấy rằng :
_ Theo định lí Phec-ma nhỏ, ta có 2p-1 ≡ 1 ( mod p )
Þ 2p-1 – 1 ≡ 0 ( mod p ) Þ u( p-1) ≡ 0 ( mod p )
Þ Nếu k = p-1 thì uk M p
Þ Tồn tại một tập hợp những số k ∈ ℕ+ để uk M p
Þ Vì tập hợp những số k ∈ ℕ+ , k > 0 ( bị chặn dưới ) nên theo định lí
Weiestrass thì ∃ e∈ ℕ+, e là nhỏ nhất để ue M p đ.p.c.m.
_ Chú ý : + Dễ thấy rằng 2 < e ≤ ( p-1)
+ << Nếu số nhỏ nhất e ∈ ℕ+ và ue M p thì uke M p >> ( ∀ k ∈ ℕ ).
Thật vậy ! ta dễ dàng chứng minh được điều nầy bằng hằng
đẳng thức : uke = 2ke – 1 = ( 2e)k – 1k
= ( 2e - 1) [( 2e)k-1+ ( 2e)k-2+ ... + (2e) + 1 ]
= ue . [ (2e)k-1 + .......... + 1 ] .
Þ uke M ue và ue M p Þ uke M p đ.p.c.m.
Ngược lại , ta có bổ đề sau :
❷ Bổ đề 2 : << Với mổi số nguyên tố p cho trước, với mọi số n∈ ℕ và e là số tự nhiên nhỏ nhất sao cho un M p và ue M p thì ta có nM e >> .
Giả sử n không chia hết cho số e . Thế thì ∃ k, m ∈ℕ ; 1 ≤ m < e sao cho : n = ke + m
Þ un = 2n - 1 = 2ke+m - 1 Þ ( 2ke+m – 1) M p và (2e – 1 ) M p
Þ {( 2ke+m – 1) - ( 2e – 1 ) } M p Þ (2ke. 2m - 2e ) M p
Þ ( 2ke. 2m - 2m + 2m - 2e ) M p Þ {( 2ke. 2m – 2m) – (2e – 2m)} M p
Þ { 2m(2ke – 1 ) – 2m ( 2e-m – 1 )} M p Þ ( 2m.uke - 2m .u(e-m) ) M p
Theo chú ý ở phần bổ đề 1, vì ue M p nên uke M p Þ 2m uke M p
Þ 2mu(e-m) M p và Ư CLN ( 2m ; p ) = 1 Þ u(e-m) M p
Mà 0 < e-m < e ; nên tồn tại một số tự nhiên (e-m) < e sao cho u(e-m) chia hết cho p .Điều nầy trái với giả thiết rằng e là số tự nhiên nhỏ nhất có tính chất ue M p . Vậy bổ đề 2 đã được chứng minh .
❸ Bổ đề 3 :<< Với mỗi số nguyên tố p∈℘ cho trước, và với ∀ p’ ∈ ℘ ; sao
cho p’ < p thì up không chia hết cho p’ >> .
Thật vậy ! Giả sử up M p’ và ∃ e’ ∈ ℕ+ là nhỏ nhất để cho ue’ M p’ ; theo bổ đề 2 ở trên thì ta suy ra : p M e’ mà e’ ≤ p’-1 < p’ < p Þ e’ = 1 vô lí .Vậy bổ đề 3 đã được chứng minh .
III. Tìm điều kiện cho số nguyên tố Mecxen :
Ở phần trên , ta đã biết rằng luôn ∃ p ∈ ℘ mà up ∉ ℘ ( thí dụ p = 11 ).
Tức là ∃ p’ ; p” ∈ ℘ \ up = p’ p”. Theo bổ đề 3 , ta dễ thấy rằng p nhỏ hơn p’ và p” Û p < p’ , p” .
Theo bổ đề 1 và 3 , ta dễ thấy rằng số p chính là số nhỏ nhất có tính chất up M p’ và up M p” .
Þ up M p’ và u(p’-1) M p’ ( Phec-ma nhỏ ) theo bổ đề 2 thì (p’ –1) M p .
Bằng suy luận tương tự cho p” ta cũng có ( p” – 1 ) M p .
Þ ∃ m,n,k,l ∈ ℕ+ và k,l là số lẽ để;
p’ = 2m p k + 1
p” = 2n p l + 1 ( CT 1 )
Vậy ta có công thức sau :
up = 2p – 1 = (2m pk +1)( 2n pl +1 ) (CT 2 )
❶ Xét các trường hợp sau :
a. Nếu m = n = 1 thì CT 2 trở thành :
up = ( 2pk +1 )( 2pl + 1) = 22 pkpl + 2pk + 2pl + 1
= ( 22pkpl + 2pk + 2pl +2 ) - 1 = 2p – 1 = up
Þ ( 22 pkpl + 2pk +2pl + 2) = 2p
Þ 2(2pkpl + pk + pl + 1 ) = 2p = 2{ 2pkpl + p( k +l ) +1 }
Þ 2p-1 = 2pkpl + p( k +l ) + 1 (chú ý k, l là số lẻ )
= chẵn + chẵn + lẻ
Þ 2p-1 = lẻ Þ vô lí . Vậy trường hợp m = n = 1 không xảy ra .
b. Nếu m , n ≥ 2 : thì công thức 2 trở thành :
2p – 1 = ( 2m pk +1 )( 2n pl + 1 ) = ( 2m pk + 1 ){ (2n pl +2) –1}
= (2m pk +1 ){ 2( 2n-1 pl +1 ) - 1 }
= 2m+1pk( 2n-1pl +1) – 2mpk + 2(2n-1pl +1) - 1
Þ 2p-1 = = lẻ ( vô lí )
Vậy trường hợp nầy m, n ≥ 2 không xảy ra .
Căn cứ vào hai trường hợp trên ta suy ra : trong hai số m,n thì có một
số bằng 1 , còn một số lớn hơn bằng 2.
c. Giả sử m =1 và n ≥ 2 : CT 2 trở thành :
2p – 1 = (2pk +1)( 2n pl +1) với n ≥ 2 ( CT 3 )
Ta biến đổi vế phải như sau :
2p – 1 = ( 2pk +1){ 2( 2n-1 pl + 1) – 1 }
=22pk(2n-1pl +1) + 2(2n-1pl +1) – 2pk –1
Þ 2p = 22pk(2n-1pl +1) + 2(2n-1pl +1) – 2pk
Þ 2p-1 = 2pk(2n-1pl +1) + ( 2n-1pl +1) – pk
Þ 2p-1 = 2pk(2n-1pl +1) + 2n-1pl - ( pk – 1)
Þ 2p-2 = pk( 2n-1pl +1) + 2n-2pl - {( pk – 1) :2}
Þ = pk2n-1 pl + 2n-2pl + pk – {( pk –1): 2 }
Þ = 2n-1pkpl + 2n-2pl + {( pk + 1) : 2}
Þ 2p-2 = 2n-2pl( 2pk +1) + {( pk +1) : 2} ( CT 4 )
Nhận xét :
*Hệ thức trên cho ta những nhận định sau :
~ { ( pk + 1) :2 } có dạng = 2n-2 a ( với a∈ ℕ+, a lẻ ).Nếu không , thì sau khi rút gọn hai vế cho lũy thừa của 2; ta có vế phải của CT 4 là số lẽ , còn vế trái là số chẵn.Như vậy thì không thích hợp !Nên {( pk +1) : 2 } = 2 n- 2 a .
Þ pk +1 = 2 n-1a ( CT 5 )
~ Từ CT4 ta suy ra: 2 ≤ n < p ( CT 6 )
Theo nhận xét trên ,CT4 trở thành :
Þ 2p-2 = 2n-2pl( 2pk +1) + 2n-2 a Þ 2p-2 = 2n-2pl.(2n.a – 1) + 2n-2a
Þ 2p-n = pl( 2na – 1) + a = 2na.pl – pl +a = 2napl – ( pl – a)
Nhận xét : Tương tự như nhận xét vừa qua , ( pl – a) phải có dạng như sau :
Pl – a = 2 n .b ( CT 7 ) Với b ∈ ℕ+ ; b là số lẻ.
Thế thì : 2p-n = 2n apl – 2nb Þ 2p-2n = apl - b = a( 2nb + a) – b
Þ 2p-2n = 2nab + ( a2 – b ) ( CT 8 )
Nhận xét :Tương tự như trên, ( a2 – b ) phải có dạng như sau :
a2 - b = 2 n c ( CT 9 ) với c ∈ ℕ+ ,c là số lẻ.
Thế thì :
Þ 2p-2n = 2n.ab + 2n.c = 2n.( ab + c )
Þ 2p-3n = ab + c ( CT 10 ) Với a,b,c ∈ ℕ+ và a,b,c đều lẻ.
Nhận xét :Điều kiện của số n là n ∈ ℕ+ và 2 ≤ n < ( p – 1) : 3 ( CT 11 )
Ta có thể chứng minh chiều ngược lại để có kết luận như dưới đây .
❷ KẾT LUẬN :
Nếu dùng CT5, CT7 để thay vào CT3 ; ta được kết quả sau :
<< Với mỗi số nguyên tố p, nếu và chỉ nếu tồn tại bốn số a,b,c,n ∈ ℕ +, trong đó a,b,c là các số lẻ thỏa mãn các điều kiện : 1/. ab + c = 2 p-3n
2/. a 2 – b = 2 n c
3/. 2 ≤ n < ( p-1) : 3
thì u p = 2 p - 1 là một hợp số có dạng u p = ( 2 n a – 1).{ 2n( 2 n.b +a) +1} >>.
Với điều kiện nầy, ta có thể phát biểu như sau :
IV. ĐỊNH LÍ NVP:
❶ Định lí : << Với mổi số nguyên tố p cho trước, nếu không tồn tại bốn số a,b,c,n
∈ ℕ +, trong đó a,b,c là các số lẻ thỏa mãn các điều kiện :
1. ab + c = 2 p-3 n
2. a 2 – b = 2 n c
3. 2 ≤ n < (p-1) : 3
thì u p = 2p – 1 là một số nguyên tố Mecxen >>.
