4 Hàm Euler, định Lý Euler Và định Lý Fermat - Tài Liệu Text - 123doc

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Kỹ thuật lập trình >

4 Hàm Euler, định lý Euler và định lý Fermat

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (260.32 KB, 19 trang )

Chú ý rằng các phần dư của phép chia xi a cho n là khác nhau. Nếu điều này không đúng, có nghĩa làtồn tại i1 ≠ i2 , sao choxi1 a ≡ xi 2 a mod nCho nên ( xi1 − xi2 ) a ≡ 0 mod n . Bởi vì a nguyên tố cùng nhau với n, nên biểu thức cuối cùng tươngđương vớixi1 − xi2 ≡ 0 mod nĐiều này là mâu thuẫn, bởi các số x1 , ..., xφ ( n ) là các cặp khác nhau theo modulo n.Hãy nhân tất cả đẳng thức xi a ≡ x j mod n , thì thu được:x1... xφ ( n ) a φ ( n ) ≡ x1... xφ ( n ) mod nHayx1...xφ ( n ) ( aφ ( n ) − 1) ≡ 0 mod nBởi vì số x1... xφ ( n ) mod n nguyên tố cùng nhau với n nên đẳng thức cuối cùng tương đương vớia φ ( n ) − 1 ≡ 0 mod n hay a φ ( n ) ≡ 1 mod nTa có một công thức quan trọng sau: aφ (n ) + 1 ≡ a mod n.Định lý Fermat nhỏ: Cho p là số nguyên tố, a là số nguyên dương không chia hết cho p. Khi đó ta cóa p −1 ≡ 1 mod p .Chứng minh: Ta có φ ( p) = p − 1 , áp dụng định lý Euler ta có điều phải chứng minh.Từ định lý Fermat chúng ta có các hệ quả quan trọng sau:1. Cho a ∈ Z , p là số nguyên tố, thì ta có: a p ≡ a mod p2. Cho a, b ∈ Z , p là số nguyên tố (a + b) n ≡ a n + b n mod pVí dụ 2.16: Chứng mình rằng 118 +218 +318 +418 +518 +618 ≡ –1 mod 7Giải: Các số 1, 2, 3, 4, 5, 6 là số nguyên tố cùng nhau với 7. Nên theo định lý Fermat chúng ta có cácphương trình sau:16 ≡ 1 mod 7 ; 2 6 ≡ 1mod 7 ; 36 ≡ 1mod 7 ; 4 6 ≡ 1 mod 7 ; 56 ≡ 1 mod 7 ; 66 ≡ 1 mod 7Lấy bậc ba hai vế từng phương trình và cộng lại ta được:118 +218 +318 +418 +518 +618 ≡ 6 mod 7 = −1 mod 72.5 Thuật toán Euclide và thuật toán Euclide mở rộng2.5.1Thuật toán EuclideĐịnh lý Euclide: Cho a, b ∈ Z , b ≠ 0 , tồn tại duy nhất cặp giá trị (q, r) với q ∈ Z và r ∈ N thỏa mãn:a = bq + r , 0 ≤ r < b .ở đây r gọi là số dư.Có một số ký hiệu cho số dư như sau:r = Rb (a ) , r = a mod b .6Một số tính chất đơn giản của về số dư:1. R−b ( a) = Rb ( a) , bởi vìa = qb + r  a = (− q )(−b) + r⇔0 ≤ r < b  0 ≤ r < b2. R b ( a + ib) = Rb ( a), ∀i ∈ Z , bởi vìa + ib = ( q + i )b + r .Nếu như r = 0 thì ta nói a chia hết cho b, ký hiệu là a .bĐịnh lý 2.1: Đối với bất kỳ các số a, b, i ∈ Z :gcd(a, b) = gcd(a + ib, b) .dChứng minh: Nếu như ad và bd , thì a = q1d , b = q2 d . Lúc này a + ib = d ( q1 + iq 2 ) ⇒ (a + ib) .Có nghĩa là:gcd(a, b) ≤ gcd(a + ib, b) . (*)Tương tự giả sử rằng (a + ib) d và bd ⇒ a + ib = q1d , b = q2 d . Lúc này a = d ( q1 − iq 2 ) ⇒ ad .Có nghĩa là:gcd(a, b) ≥ gcd(a + ib, b) . (**)Từ (*) và (**) chúng ta có đẳng thức gcd(a,b)=gcd(a+ib,b).Định lý 2.2: Đối với bất kỳ a, b ∈ Z , b ≠ 0 , ta có:gcd(a, b) = gcd(b, Rb (a ))Chứng minh.Bởi vì a = bq + Rb (a) ,gcd(a, b) = gcd(a − qb, b) = gcd( Rb ( a), b) .Từ định lý 2.2 ta có thuật toán Euclide. Đây là thuật toán giúp tìm UCLN của hai số nguyên dương a0và a1 với a0 > a1.Thuật toán được miêu tả bằng dãy các phép chia như sau:a0 = a1q1 + a 2 , 0 < a2 < a1a1 = a 2 q 2 + a3 , 0 < a3 < a2…ak −2 = ak −1qk −1 + ak , 0 < ak < |ak-1|ak −1 = ak qk + 0Dựa vào định lý 2.1, nhận được gcd(a0, a1) = gcd(a1, a2) = … = gcd(ak, 0) = ak.Ví dụ 2.17 (Thuật toán Euclide): Tìm gcd(814, 187).Giải: Khai triển dãy phép tính theo thuật toán Euclide:814 = 4 * 187 + 66187 = 2 * 66 + 5566 = 1 * 55 + 11755 = 5 * 11 + 0Vậy gcd(814, 187) = 11.Thuật toán có thể viết như sau:Vào: Hai số nguyên dương a và b với a > bRa: UCLN của a và b(1) While b # 0 dor ← a mod b, a ← b, b ← r(2) Return (a).2.5.2Thuật toán Euclide mở rộngĐịnh nghĩa 2.3 (Phần tử nghịch đảo)Cho a ∈ Z n . Phần tử nghịch đảo của a là phần tử b ∈ Z n sao cho a * b ≡ b * a ≡ 1 mod n . Kí hiệuphần tử nghịch đảo của a là a-1.Định lý 2.2: Cho số nguyên a > 0 nguyên tố cùng nhau với n, thì luôn tồn tại phần tử nghịch đảo củaa theo modulo n.Chứng minh: Hãy xét tập hợp {1, 2, ..., n − 1} . Nhân từng phần tử của tập hợp với a theo modulo n, nhậnđược tập hợp { ( a mod n), ( 2a mod n), ..., ((n − 1) a mod n)} , tập này sẽ bao gồm các số 1, 2,…, n – 1, cónghĩa đối với một số giá trị i nào đó sẽ thỏa mãn điều kiện ia mod n = 1 . Điều này dẫn đến một mâuthuẫn nếu như tồn tại hai giá trị h và k thỏa mãn điều kiện trên, nghĩa là ha mod n = ka mod n . Điều nàydẫn đến h ≡ k mod n , vì gcd(a, n) = 1, suy ra h = k. Vậy ta tìm được i là phần tử nghịch đảo của a và i làduy nhất.Hệ quả 2.1: Nếu như p là số nguyên tố, thì bất kỳ số a, 0 < a < p, luôn tồn tại phần tử nghịch đảotheo modulo p.Chúng ta sẽ tìm hiểu về cách tìm phần tử nghịch đảo thông qua thuật toán Euclide mở rộng.Từ dãy chia của thuật toán Euclidea0 = a1q1 + a2 , 0 < a2 < a1a1 = a2 q2 + a3 , 0 < a3 < a2…ak − 2 = ak −1qk −1 + ak , 0 < ak < ak-1Ta dễ dàng rút ra dãy sau:ak = ak − 2 − qk −1ak −1 mà ak −1 = ak − 3 − qk − 2 ak − 2 nên suy ra ak = ak − 2 − qk −1 ( ak − 3 − qk − 2 ak − 2 ) , tương tựnhư thế, chúng ta rút ra ak − 2 , đến cuối cùng chúng ta có được biểu thức dạng sau:ak = a0 x + a1 y (2.1)Nếu như gcd(a0 , a1 ) = 1 , chúng ta có x là phần tử nghịch đảo của a0 theo modulo a1.Ví dụ 2.18 (Thuật toán Euclide mở rộng):1. Tìm x và y trong biểu thức (2.1) với a0 = 814 và a1 = 187.8Giải: Theo ví dụ 2.17 ta thu được dãy:814 = 4 * 187 + 66187 = 2 * 66 + 5566 = 1 * 55 + 1155 = 5 * 11 + 0Suy ra: 11 = 66 – 1 * 55 = 66 – 1 * (187 – 2 * 66) = 3 * 66 – 1 * 187 = 3 * (814 – 4 * 187) –187 = 3 *814 – 13 * 187. Vậy x = 3 và y = –13.2. Tìm phần tử nghịch đảo của 17 theo modulo 74.Giải: Theo ví dụ trên ta có được 3 * 74 – 13 * 17 = 1. Nên phần tử nghich đảo của 17 là –13,nhưng chỉ lấy số dương, nên phần tử nghịch đảo của 17 là 74 – 13 = 61.2.6 Giải phương trình đồng dư trong nhóm thương Z nCó nhiều phương pháp giải phương trình đồng dư, nhưng chúng tôi muốn trình bày với bạn đọc mộtphương pháp khá hay dựa vào định lý sau:Định lý 2.3: Cho n > 1, gcd(a, n) = 1. Khi đó phương trình đồng dư ax ≡ b mod n có nghiệm duynhất, và nghiệm đó là:x = baφ ( n ) − 1 mod nChứng minh: Theo định lý Euler, ta có aφ ( n ) ≡ 1 mod n , suy ra a.baφ ( n ) −1 ≡ b mod n . Vậy nghiệmx = baφ ( n ) −1 mod n.Ví dụ 2.19: Giải phương trình 7x ≡ 3 mod 10.Chúng ta tính như sau:φ (10) = 4; x ≡ 3 * 74-1 mod 10 ≡ 1029 mod 10 ≡ 9.Thế nhưng cách này sẽ khó thực hiện nếu bậc của a đủ lớn. Bởi vậy chúng ta xem cách sau.Chúng ta đã biết định lý về phần tử nghịch đảo, nếu như gcd(a, n) = 1, thì luôn tồn tại phần tử nghịchđảo a-1. Nên từ phương trình ax ≡ b mod n , suy ra x ≡ ba −1 mod n.Ví dụ 2.20: Giải phương trình 7 x ≡ 3 mod 10 .Chúng ta thấy 7 −1 mod 10 = 3 . Nên nghiệm của phương trình x = 3 * 3 mod 10 = 9.Định lý 2.4: Cho n >1, để phương trình ax ≡ b mod n có nghiệm thì điều kiện cần và đủ là gcd(a, n)|b.Chứng minh: Phương trình ax ≡ b mod n có thể viết dưới dạng phương trình tuyến tính sauax + kn = b, (2.2),k là số nguyên.Ta chứng minh điều kiện cần. Giả sử hoàn thành điều kiện (2.2). Bời vì số gcd(a, n) là ước của vếtrái, nên nó cũng phải là ước của vế phải.Chứng minh điều kiện đủ. Ứng dụng thuật toán Euclide đối với hai số a và n, có thể tínhaλ + µn = gcd(a, n) (2.3)9Bởi vì b/gcd(a, n) là số nguyên, nên nhân hai vế (2.3) cho b/gcd(a, n) và nhận được công thức (2.2),và ở đây x =λbmod n là một nghiệm.gcd(a, n)Dễ dàng kiểm tra phương trình đã có nghiệm dạngx+nimod n , i = 0, 1, 2, .., gcd(a, n) – 1.gcd(a, n)Tức là phương trình đã cho có gcd(a, n) nghiệm khác nhau, nghiệm này nhỏ hơn n.Ví dụ 2.21:1. Giải phương trình 2 x ≡ 5 mod 10Vì gcd(2, 10) = 2, vì 2 không là ước của 5 nên phương trình trên vô nghiệm, nếu không dựa vào địnhlý cũng dễ dàng thấy rằng 2x + 10y = 5 cũng vô nghiệm, vì vế trái là số chẳn, còn vế phải là số lẻ. Điềunày là không thể.2. Giải phương trình 6 x ≡ 18 mod 36 . Vì gcd(6, 36)|18. Nên phương trình này có 6 nghiệm: 3, 9,15, 21, 27 và 33.2.7 Định lý phần dư Trung Hoa.Định lý này nhằm giúp chúng ta giải hệ phương trình đồng dư thức, định lý phát biểu như sau:Giả sử cho các số n1, n2, …, nk là các số nguyên dương nguyên tố cùng nhau từng đôi một và c1, c2,…, ck là các số nguyên khi đó hệ phương trình đồng dư:x ≡ c1 mod n1x ≡ c2 mod n2…x ≡ ck mod nkCó nghiệm duy nhất theo modulo n và nghiệm đó là:kx = ∑ ci N i ( N i−1 mod ni ) mod n (2.4)i =1ở đây n = n1n2 ...nk và N i =M.niChứng minh:Nếu ta chứng minh hệ trên tương đương với một phương trình sau:x ≡ x0 mod nk−1ở đây x0 = ∑ ci N i ( N i mod ni ) thì coi như chúng ta đã chứng minh được định lý trên.i =1Ta có Ni chia hết cho ns, khi s ≠ i. Điều này dẫn đến x0 ≡ N i ( N i−1 mod ni )ci (mod ni ) , từ đóx0 ≡ ci (mod ni ) . Điều này có nghĩa hệ trên tương đương với hệ sau:x ≡ x0 mod n1x ≡ x0 mod n210...x ≡ x0 mod nkĐiều này tương đương với một phương trình sau x ≡ x0 mod n . Mà ta đã biết phương trình này cónghiệm duy nhất là x0 mod n.Ví dụ 2.22: Giải hệ phương trình đồng dư sau:x ≡ 5 mod 7x ≡ 3 mod 11x ≡ 10 mod 13Giải: Ta có n = 7 * 11 * 13 = 1001; N1 = n/5 = 143; N2= n/11 = 91; N3 = n/13 = 77Ta đi tính phần tử nghịch đảo của Ni theo modulo ni143-1 mod 7 = 5; 91-1 mod 11 = 4 và 77-1 mod 13 = 12.Áp dụng công thức (2.4) ta có được nghiệm của hệ phương trình là:x = (5.143.5 + 3.91.4 + 10.77.12) mod 1001 = 894.2.8 Bậc và căn nguyên thủyĐịnh nghĩa 2.4 (Bậc)Cho gcd(a, n) = 1. Bậc a mod n là số nguyên dương nhỏ nhất γ thỏa mãn phương trình đồng dưthức:a γ ≡ 1 mod n ,Kí hiệu bậc là Ordn(a).Ví dụ 2.23: Tìm bậc của 2 mod 5Giải: 21 mod 5 = 2; 22 mod 5 = 4; 23 mod 5 = 3; 24 mod 5 = 1; vậy Ord5(2) = 4.Định nghĩa 2.5 (Căn nguyên thủy)Nếu như bậc của a modulo n bằng giá trị của hàm Euler của n. Thì a gọi là căn nguyên thủy của n.Ví dụ 2.24: Số 2 là căn nguyên thủy của 5. Vì Ord5(2) = φ (5) = 4.2.9 Thặng dư bậc haiThặng dư bậc hai đóng vai trò rất quan trọng trong lý thuyết số. Ví dụ, thuật toán phân tích sốnguyên ra thừa số. Ngoài ra thặng dư bậc hai cũng ứng dụng lớn trong mật mã cũng như trong các giaothức mã hóa.Định nghĩa 2.6 (Thặng dư bậc hai)*Cho n là số nguyên và n > 1 . Số từ nhóm Z n gọi là thặng dư bậc hai theo modulo n, nếu trong nhóm*Z n tồn tại số x, thỏa mãn điều kiện x 2 ≡ a mod n , trường hợp ngược lại gọi là không thặng dư bậc hai.Tập hợp các số thặng dư bậc hai theo modulo n ký hiệu QRn, tập hợp không thặng dư bậc hai ký hiệu làQNRn.Ví dụ 2.25: Tính QR11 là tập tất thặng dư bậc hai theo modulo 11.11{}Chúng ta có QR11 = 12 , 2 2 , 32 , 4 2 , 52 , 6 2 , 7 2 , 82 , 9 2 ,10 2 mod 11 = {1, 3, 4, 5, 9} , trong ví dụ, chúng ta*tính QR11 bằng cách lựa chọn các phần tử của nhóm Z11 .{}Độc giả có thể kiểm tra lại rằng QR11 = 12 , 22 , 32 , 4 2 , 52 mod 11 = {1, 3, 4, 5, 9} . Điều này sẽ tìm hiểuqua định lý sau:Định lý 2.5: Cho p là số nguyên tố. Khi đó những khẳng định sau đây là đúng.{}1.QR p = x 2 (mod p) | 0 < x ≤ ( p − 1) / 2 .2.*Nhóm Z p chia ra hai tập con, QRp và QNRp có số phần tử bằng nhau.Chứng minh:Chúngtachứngminh{điềukhẳngđịnhthứnhất.Rõràngrằng}S = x 2 (mod p) | 0 < x ≤ ( p − 1) / 2 ⊆ QR p . Để chứng minh QR p = S , điều này sẽ đúng nếu như chúng tachứng minh được rằng QR p ⊆ S .Chọn một số a bất kỳ a ∈ QR p . Tồn tại số x < p, thỏa mãn điều kiện x 2 ≡ a (mod p ) . Nếu nhưx ≤ ( p − 1) / 2 , thìa ∈ S . Giả sử rằng x > (p – 1)/2. Như thếy = p − x ≤ ( p − 1) / 2vày 2 ≡ ( p − x) 2 ≡ p 2 − 2 px + x 2 ≡ x 2 ≡ a(mod p ) . Chứng tỏ, QR p ⊆ S .Ta đi chứng minh điều khẳng định thứ hai. Để chứng minh # QR p = ( p − 1) / 2 ,thì nó sẽ tương đươngvới việc chứng minh rằng đối với tất cả số x, thỏa mãn bất đẳng thức 0 < x < y ≤ ( p − 1) / 2 , thì thỏa mãnđiều kiện x 2 ≠ y 2 (mod p ) . Giả sử điều này sai: x 2 − y 2 ≡ ( x + y )( x − y ) ≡ 0(mod p). Dẫn đến, p|(x + y)hoặc p|(x – y). Bởi vì x + y < p và p là số nguyên tố. Nên chỉ có thể là x = y. Điều này trái ngược với giả*thuyết. Vậy # QR p = ( p − 1) / 2 . Mà # Z p = p − 1 , nên điều khẳng định thứ hai hoàn toàn đúng.Thường xuất hiện bài toán, xác định xem số n có phải là thặng dư bậc hai theo modulo đã cho haykhông. Vấn đề này gọi là bài toán về thặng dư bậc hai. Bài toán này được giải quyết thông qua định lýsau:*Định lý 2.6 (Tiêu chuẩn Euler): Cho p là số nguyên tố. Đối với bất kỳ số x ∈ Z p , x là thặng dư bậchai khi và chi khi thỏa mãn điều kiện sau:x ( p −1) / 2 ≡ 1 mod p .*Chứng minh: Đối với x ∈ QR p thì tồn tại số y ∈ Z p sao cho y 2 ≡ x(mod p ) . Theo định lý Fermatchúng ta có, x ( p −1) / 2 ≡ y p −1 ≡ 1 mod p .Ngược lại, nếu như x ( p −1) / 2 ≡ 1 mod p , như vậy x là nghiệm của đa thức y ( p −1) / 2 − 1 ≡ 0 mod p .Chúng ta đã biết Z p là một trường. Mà ta dễ dàng thấy rằng mỗi phần tử của trường là nghiệm của đathức y p − y ≡ 0 mod p . Hay nói cách khác, mỗi phần tử khác không của trường là nghiệm của đa thức:12y p −1 − 1 ≡ ( y ( p −1) / 2 − 1)( y ( p −1) / 2 + 1) ≡ 0 mod p.Mà tất cả các nghiệm này phải khác nhau, bởi vì đa thức có bậc p – 1. Điều này dẫn đến (p – 1)/2nghiệm của đa thức y ( p −1) / 2 − 1 ≡ 0 mod p phải khác nhau. Mà theo định lý về số phần tử của tập thặngdư bậc hai ta có tập QRp có (p – 1)/2 phần tử, mỗi phần tử là nghiệm của phương trình*y ( p −1) / 2 − 1 ≡ 0 mod p . Và bất kỳ phần tử nào khác của nhóm Z p cũng phải thỏa mãn phương trìnhy ( p −1) / 2 + 1 ≡ 0 mod p . Vậy x ∈ QR p .Khi chứng minh định lý này chúng ta có thể điều khẳng định sau: Nếu như x ∈ Z p mà tiêu chuẩnEuler không thỏa mãn thì:x ( p −1) / 2 ≡ −1 mod p .2.10 Các ký hiệu Legendre và JacobiKý hiệu Legendre là một công cụ hữu ích để xem xét liệu một số nguyên a có là thặng dư bậc haitheo modulo của một số nguyên tố p hay không?2.10.1 Ký hiệu LegendreĐịnh nghĩa 2.7Nếu p là số nguyên tố lẻ và a là một số tự nhiên, thì ký hiệu Legendrea  được xác định như sau: p o0nếu a|p;o1nếu a ∈ QR p ;o−1nếu a ∈ QNR pCác tính chất của ký hiệu Legendre:Cho p là một số nguyên tố lẻ và a, b ∈ Z. Khi đó ký hiệu Legendre có các tính chất sau: ab   a  b 1.   ≡    p    b  p a b2. Nếu a ≡ b mod p , thì   =   p  p   13.   = 1 p  14.  −  = ( −1) p25.   = ( −1) p p −12p 2 −18 p +16 36.   = ( −1)  p 1 khi p ≡ 1 mod 4− 1 khi p ≡ 3 mod 4 1 khi p ≡ 1, 7 mod 8=− 1 khi p ≡ 3, 5 mod 8 1 khi p ≡ 1,11 mod 12=− 1 khi p ≡ 5, 7 mod 1213 p−25  1 khi p ≡ 1, 4 mod 5=− 1 khi p ≡ 2, 3 mod 5 p +1 6  1 khi p ≡ 1, 3, 9,19, 25, 27 mod 28=− 1 khi p ≡ 5,11,13,15,17, 23 mod 2857.   = ( −1)  p 78.   = ( −1)  p  q   p9. Nếu p và q là các số nguyên tố lẻ thì   =  ( −1) p  q   q −1 p −12 2Tiêu chuẩn Euler có thể viết lại như sau: Euler chứng minh rằng với mọi số nguyên tố p và số a,1≤ a ≤ p ,a  ≡ a ( p −1) / 2 mod p . p Ví dụ 2.26: Tính ký hiệu Legendre 12345  331  3  5  823 = 331  331  331  3  5  161 = 331  331  331  3  5  7  23 = 331  331  331  331  331  331  331  331 = ( − 1) ( − 1) ( − 1) ( − 1)  3  5  7  23  1  1  2  9 = −     3  5  7  23 2 1  1  2  3 = −     3  5  7  23  1  1  2  9 = −     3  5  7  23 = −(1)(1)(1)(1) = −12.10.2 Ký hiệu JacobiĐịnh nghĩa 2.8ααKý hiệu Jacobi là tổng quát hóa của ký hiệu Legendre cho số tự nhiên lẻ n. Giả sử n = p1 1 p2 2 ... pαkklà dạng phân tích tiêu chuẩn của n. Với số nguyên a bất kỳ, ký hiệu Jacobi là:αα12 aa  a   a =     ...     p n   p1   p2  kαk, trong đó tất cả các ký hiệu bên vế phải là ký hiệu Legendre.Các tính chất của ký hiệu Jacobi:Cho n là các số tự nhiên lẻ và a, b ∈ Z. Kí hiệu Jacobi có các tính chất sau:1. Nếu n là số nguyên tố thì ký hiệu Jacobi là ký hiệu Legendrea2.   ∈ { 0, 1, − 1}n14a3.   = 0 khi gcd( a, n ) ≠ 1n ab   a  b 4.   ≡    n   n  n  a   a  b  a 5.  ≡    , điều này dẫn tới  2  là 0 hoặc 1. mn   m  n n a b6. Nếu a ≡ b mod n , thì   =  n n17.   = 1n 18.  −  = ( −1) n29.   = ( −1) nn −121 khi n ≡ 1 mod 4− 1 khi n ≡ 3 mod 4n 2 −18 1 khi n ≡ 1, 7 mod 8=− 1 khi n ≡ 3, 5 mod 8( m −1)( n −1)nm10.   = ( )( − 1) 4n mVí dụ 2.27: 37035   294  2  147 = = 1. 331   331  331  331  147   331   37   147 = −=== 331   147   147   37 2 36   2   9   37   1 =   =     =   =   =1 37   37   37   9   9 Vì 331 là số nguyên tố nên từ đó 37035 là thặng dư bậc hai mod 331.Có hai tính chất đúng với ký hiệu Legendre nhưng không thể mở rộng cho ký hiệu Jacobi.+ Khác với ký hiệu Legendre, ký hiệu Jacobi không cho biết liệu a có phải là một thặng dư bậc haiaatheo modulo n hay không. Sự thực nếu a ∈ QRn thì   = 1 . Tuy nhiên   = 1 thì không có nghĩa là a ∈nnQRn.a( p −1) / 2mod p với số+ Tính chất thứ hai không thể mở rộng gắn với đồng dư thức Euler   ≡ a p nguyên tố p và số nguyên a bất kỳ. Một cách tự nhiên đồng dư thức Euler mở rộng từ ký hiệu Legendrea( n −1) / 2mod n với hợp số lẻ dương n. Tuy nhiên đồng dư thức này là saisang ký hiệu Jacobi là   ≡ anvới ít nhất một nửa của các a mod n khi n là hợp số.2.10.3 Bổ đề GaussNếu như p và q là 2 số nguyên tố khác 2 thì:15 q   p  =  ( −1) p  q   q −1 p −12 2Hay nói cách khác, nếu như một trong 2 số p hoặc q có dạng 4n + 1, thì p bình phương theo modulo qkhi và chỉ khi q là bình phương theo modulo p. Nếu như cả 2 số p và q có dạng 4n + 3, thì p bình phươngtheo modulo q khi và chỉ khi q không là bình phương theo modulo p.Chứng minh:Cho rằng p ≠ q , xét trường Fp q −1 và cũng biết đây là cũng là nhóm cyclic. Theo định lý nhỏ Fermatthì p q −1 − 1 chia hết cho q, nên trong nhóm tồn tại phần tử có bậc là q. Chúng ta xem nó là w, lúc nàyw ≠ 1 và w q = 1 trong F p q −1 . Bây giờ xác định tổng Gauss:xy = ∑  w x x∈Z q  q Chúng ta sẽ chứng minh 2 điều khẳng định sau:Điều khẳng định 1: Ta có đẳng thức sauy 2 = (−1)q −12 q.Chứng minh: xz  x (u − x ) y 2 = ∑   w x + z = ∑ wu ∑ qqx,z u∈Z qx∈Z q Từ tổng cuối cùng x lấy giá trị trong tập Z q \ { 0} . Khi x ≠ 0 , có:q −1 1 − ux −1  x(u − x)   − x 2  1 − ux −1  = (−1) 2 = q .qq  q  Từ đây(−1)với Cu =q −12y 2 = ∑ Cu wu ,u∈Z q 1 − ux −1 ∑  q .x∈Z q \{ 0} Rõ ràngC0 =1∑   = q −1. x∈Z q \{ 0}  q Nếu như u ≠ 0 , thì s = 1 − ux −1 nhận các giá trị trong tập Z q \ {1} , cho nên: s 11Cu = ∑   −   = −  ,q qqs∈Z q     16

Xem Thêm

Tài liệu liên quan

• Tài liệu Kỹ thuật lập trình - Chương 2: Giới thiệu lý thuyết số
  • 19
  • 1,353
  • 1

Tải bản đầy đủ (.doc) (19 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(918.5 KB) - Tài liệu Kỹ thuật lập trình - Chương 2: Giới thiệu lý thuyết số-19 (trang) Tải bản đầy đủ ngay ×