Hợp số hoàn toàn có thể được sắp xếp thành những hình chữ nhật, còn số nguyên tố thì không
Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Chẳng hạn, 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một tích, 1 × 5 hoặc 5 × 1, có một thừa số là chính số 5. Tuy nhiên, 4 là hợp số vì nó là tích của hai số (2 × 2) mà cả hai số đều nhỏ hơn 4. Số nguyên tố là nội dung trọng tâm trong lý thuyết số theo định lý cơ bản của số học: mọi số tự nhiên lớn hơn 1 hoặc là số nguyên tố hoặc có thể được phân tích ra thừa số nguyên tố một cách duy nhất xê xích một phép hoán vị.
Tính chất của một số nguyên tố được gọi là tính nguyên tố. Một phương pháp đơn giản để kiểm tra tính nguyên tố của một số
n
{\displaystyle n}
n
{\displaystyle n}
có phải là bội số của bất kỳ số nguyên nào giữa 2 và
n
{\displaystyle {\sqrt {n}}}
Có vô số số nguyên tố, như đã được Euclid chứng minh vào khoảng năm 300 TCN. Hầu như không có công thức đơn giản nào để phân biệt số nguyên tố và hợp số. Tuy nhiên, sự phân phối các số nguyên tố trong tập hợp các số tự nhiên có trong một khoảng giá trị lớn có thể được mô hình hóa theo thống kê. Kết quả đầu tiên theo hướng đó là định lý số nguyên tố, được chứng minh vào cuối thế kỷ 19, cho rằng xác suất để một số bất kỳ là số nguyên tố tỉ lệ nghịch với số chữ số của nó, nghĩa là với logarit của nó.
Bạn đang đọc: Số nguyên tố – Wikipedia tiếng Việt
Một số bài toán lịch sử vẻ vang tương quan đến số nguyên tố vẫn chưa có giải thuật. Chúng gồm có giả thuyết Goldbach, cho rằng mọi số nguyên chẵn lớn hơn 2 hoàn toàn có thể được trình diễn thành tổng của hai số nguyên tố, và phỏng đoán về số nguyên tố sinh đôi, cho rằng có vô số cặp số nguyên tố chỉ có một số ít chẵn giữa chúng. Những bài toán như vậy đã góp thêm phần thôi thúc sự tăng trưởng của nhiều nhánh trong triết lý số tập trung chuyên sâu vào góc nhìn đại số và giải tích của những số. Số nguyên tố cũng có ứng dụng trong 1 số ít nghành của công nghệ thông tin, ví dụ điển hình như mật mã hóa khóa công khai minh bạch, dựa vào sự phức tạp trong việc nghiên cứu và phân tích những số nguyên lớn ra thừa số nguyên tố. Trong đại số trừu tượng, còn có một số ít đối tượng người dùng khác có đặc thù và đặc thù giống với số nguyên tố, trong đó gồm thành phần nguyên tố và i-đê-an nguyên tố .
Định nghĩa và ví dụ[sửa|sửa mã nguồn]
Một số tự nhiên (1, 2, 3, 4, 5, 6,…) được gọi là số nguyên tố nếu nó lớn hơn 1 và không thể được biểu diễn thành tích của hai số tự nhiên nhỏ hơn khác 1. Các số lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.[2] Nói cách khác,
n
{\displaystyle n}
là số nguyên tố nếu
n
{\displaystyle n}
vật không thể chia đều thành nhiều nhóm nhỏ gồm nhiều hơn một vật,[3] hoặc
n
{\displaystyle n}
dấu chấm không thể được sắp xếp thành một hình chữ nhật có chiều dài và chiều rộng nhiều hơn một dấu chấm.[4] Chẳng hạn, trong các số từ 1 đến 6, số 2, 3 và 5 là số nguyên tố vì không có số nào khác có thể chia hết được chúng (số dư bằng 0).[5] 1 không phải là số nguyên tố vì nó đã được loại trừ ra khỏi định nghĩa. 4 = 2 × 2 và 6 = 2 × 3 đều là hợp số.
Hình minh họa cho thấy 7 là số nguyên tố vì không có số nào trong những số 2, 3, 4, 5, 6 hoàn toàn có thể chia hết 7
Ước số của một số tự nhiên
n
{\displaystyle n}
là các số tự nhiên có thể chia hết được
n
{\displaystyle n}
. Mọi số tự nhiên đều có ít nhất hai ước số là 1 và chính nó. Nếu nó còn có thêm một ước số khác thì nó không thể là số nguyên tố. Từ ý tưởng đó mà ta có một định nghĩa khác về số nguyên tố: đó là những số chỉ có đúng hai ước số dương là 1 và chính nó.[6] Ngoài ra, còn có một cách diễn đạt khác nữa:
n
{\displaystyle n}
là số nguyên tố nếu nó lớn hơn 1 và không có số nào trong các số
2
,
3
,
…
,
n
−
1
{\displaystyle 2,3,\dots ,n-1}
25 số nguyên tố tiên phong ( tổng thể những số nguyên tố nhỏ hơn 100 ) là : [ 8 ]
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (dãy số A000040OEIS).
Không có số chẵn
n
{\displaystyle n}
lớn hơn 2 nào là số nguyên tố vì một số chẵn bất kỳ có thể được biểu diễn thành
2
×
n
2
{\displaystyle 2\times {\frac {n}{2}}}
Tập hợp các số nguyên tố được ký hiệu là
P
{\displaystyle \mathbf {P} }
P
{\displaystyle \mathbb {P} }
Giấy cói Rhind
Giấy cói Rhind (từ khoảng năm 1550 trước Công nguyên) có chứa các khai triển phân số Ai Cập theo nhiều dạng khác nhau cho số nguyên tố và hợp số.[13] Tuy nhiên, các công trình nghiên cứu cụ thể về số nguyên tố được lưu lại sớm nhất đến từ toán học Hy Lạp cổ đại. Bộ Cơ sở của Euclid (khoảng 300 TCN) có phần chứng minh sự tồn tại vô số số nguyên tố và định lý cơ bản của số học, đồng thời nêu cách tạo ra một số hoàn thiện từ số nguyên tố Mersenne.[14][15] Một phát minh khác từ Hy Lạp là sàng Eratosthenes vẫn còn được dùng để lập danh sách các số nguyên tố.[16][17]
Khoảng năm 1000, nhà toán học Hồi giáo Ibn al-Haytham (Alhazen) tìm ra định lý Wilson, xác định số nguyên tố là các số
n
{\displaystyle n}
chia hết
(
n
−
1
)
!
+
1
{\displaystyle (n-1)!+1}
Năm 1640, Pierre de Fermat phát biểu định lý nhỏ Fermat (về sau được Leibniz và Euler chứng minh).[19] Fermat cũng đã nghiên cứu và kiểm tra tính nguyên tố của số Fermat
2
2
n
+
1
{\displaystyle 2^{2^{n}}+1}
2
p
−
1
{\displaystyle 2^{p}-1}
p
{\displaystyle p}
1
2
+
1
3
+
1
5
+
1
7
+
1
11
+
⋯
{\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }
x
{\displaystyle x}
x
{\displaystyle x}
tiệm cận về
x
/
log
x
{\displaystyle x/\log x}
log
x
{\displaystyle \log x}
x
{\displaystyle x}
. Ý tưởng của Bernhard Riemann trong công trình năm 1859 về hàm zeta của ông đã góp phần vạch ra hướng đi để chứng minh phỏng đoán đó. Mặc dù một phỏng đoán liên quan là giả thuyết Riemann vẫn chưa có lời giải, đại cương của Riemann đã được hoàn thành vào năm 1896 bởi Hadamard và de la Vallée Poussin và kết quả này hiện được biết đến với tên gọi định lý số nguyên tố.[24] Một thành tựu quan trọng khác trong thế kỷ 19 là định lý Dirichlet về cấp số cộng cho rằng một cấp số cộng nhất định chứa vô số số nguyên tố.[25]
Nhiều nhà toán học đã điều tra và nghiên cứu những thuật toán kiểm tra tính nguyên tố với những số lớn hơn so với những số mà giải thuật chia thử hoàn toàn có thể vận dụng được. Các thuật toán số lượng giới hạn về một dạng số đơn cử gồm có kiểm tra Pépin cho số Fermat ( 1877 ), [ 26 ] định lý Proth ( khoảng chừng 1878 ), [ 27 ] kiểm tra Lucas – Lehmer ( 1856 ) và dạng tổng quát của nó, kiểm tra Lucas. [ 17 ]Từ năm 1951, tổng thể những số nguyên tố lớn nhất đã biết đều được tìm ra trải qua những thuật toán trên máy tính. [ a ] Công cuộc tìm ra số nguyên tố lớn hơn thế đã gây chú ý quan tâm ngoài khoanh vùng phạm vi toán học với dự án Bất Động Sản Great Internet Mersenne Prime Search và nhiều dự án Bất Động Sản điện toán phân tán khác. [ 8 ] [ 29 ] Quan niệm rằng số nguyên tố ít được ứng dụng ngoài toán học thuần túy [ b ] đã bị xóa bỏ vào những năm 1970 khi mật mã hóa khóa công khai minh bạch và mã hóa RSA được ý tưởng dựa trên số nguyên tố. [ 32 ]Tầm quan trọng ngày càng lớn của việc kiểm tra tính nguyên tố và nghiên cứu và phân tích số nguyên tố trên máy tính dẫn đến sự tăng trưởng của nhiều thuật toán khác hoàn toàn có thể triển khai được với những số rất lớn không thuộc bất kể dạng đặc biệt quan trọng nào. [ 16 ] [ 33 ] [ 34 ] Lý thuyết toán học về số nguyên tố cũng liên tục tăng trưởng trong thời kỳ tân tiến với định lý Green – Tao ( 2004 ) phát biểu rằng sống sót những cấp số cộng dài bất kể chỉ chứa số nguyên tố, và chứng tỏ của Yitang Zhang năm 2013 rằng sống sót vô số khoảng cách nguyên tố với kích cỡ số lượng giới hạn. [ 35 ]
Tính nguyên tố của số 1[sửa|sửa mã nguồn]
Đa số nhà toán học Hy Lạp cổ không cho rằng 1 là một số ít nên họ không hề xét được tính nguyên tố của nó. [ 36 ] [ 37 ] Một số nhà toán học thời gian đó cũng cho rằng số nguyên tố có được từ sự chia nhỏ những số lẻ nên họ không xem số 2 là số nguyên tố. Tuy nhiên, Euclid và đa phần nhà toán học Hy Lạp cổ xem 2 là số nguyên tố. Các nhà toán học Hồi giáo cũng nối tiếp theo Hy Lạp, không công nhận 1 là một số ít. [ 36 ] Đến thời Trung Cổ và Phục Hưng, những nhà toán học khởi đầu thừa nhận 1 là 1 số ít, và một vài trong số đó cho rằng số 1 là số nguyên tố tiên phong. [ 38 ] Giữa thế kỷ 18, Christian Goldbach công nhận số 1 là số nguyên tố trong thư gửi Leonhard Euler, nhưng Euler lại không thừa nhận như vậy. [ 39 ] Nhiều nhà toán học thế kỷ 19 vẫn cho rằng 1 là số nguyên tố, [ 40 ] và list số nguyên tố có chứa số 1 vẫn liên tục được xuất bản cho đến năm 1956. [ 41 ] [ 42 ]Nếu định nghĩa số nguyên tố bị đổi khác để công nhận 1 là số nguyên tố, nhiều định lý tương quan đến nó sẽ phải được diễn đạt lại một cách rắc rối. Chẳng hạn, định lý cơ bản của số học khi đó sẽ bị sửa lại về mặt nghiên cứu và phân tích thành những số nguyên tố lớn hơn 1, vì mọi số đều có vô số cách nghiên cứu và phân tích mà trong đó số 1 Open với số lần bất kể. [ 40 ] Tương tự, sàng Eratosthenes cũng sẽ không hoạt động giải trí đúng cách, vì khi đó nó vô hiệu toàn bộ những bội của 1 ( tức là toàn bộ những số khác ) và cho đầu ra chỉ có duy nhất số 1. [ 42 ] Một số đặc thù của số nguyên tố cũng không đúng so với số 1 : ví dụ, công thức của hàm phi Euler hoặc hàm tổng những ước số khác nhau với số nguyên tố so với số 1. [ 43 ] Đến đầu thế kỷ 20, những nhà toán học mở màn thừa nhận rằng số 1 không nên nằm trong list số nguyên tố, mà thay vào đó cần nằm trong khái niệm đặc biệt quan trọng : ” đơn vị chức năng ” trong triết lý vành. [ 40 ]
Tính chất cơ bản[sửa|sửa mã nguồn]
Sự nghiên cứu và phân tích duy nhất[sửa|sửa mã nguồn]
Viết một số thành tích của các số nguyên tố được gọi là phân tích nguyên tố của số đó. Chẳng hạn:
- 34866 = 2 ⋅ 3 ⋅ 3 ⋅ 13 ⋅ 149 = 2 ⋅ 3 2 ⋅ 13 ⋅ 149. { \ displaystyle { \ begin { aligned } 34866 và = 2 \ cdot 3 \ cdot 3 \ cdot 13 \ cdot 149 \ \ và = 2 \ cdot 3 ^ { 2 } \ cdot 13 \ cdot 149. \ end { aligned } } }
Các thừa số trong tích được gọi là thừa số nguyên tố. Một thừa số nguyên tố có thể xuất hiện nhiều lần, khi đó có thể dùng lũy thừa để gộp nhiều thừa số giống nhau đó lại thành một. Trong ví dụ trên, số 3 xuất hiện 2 lần và
3
2
{\displaystyle 3^{2}}
Tầm quan trọng thiết yếu của số nguyên tố trong lý thuyết số và toán học nói chung có được từ định lý cơ bản của số học.[44] Định lý này phát biểu rằng bất kỳ số nguyên nào lớn hơn 1 đều có thể được viết thành tích của một hoặc nhiều số nguyên tố. Hơn nữa, tích đó là duy nhất, vì dễ thấy trong hai phân tích nguyên tố của cùng một số, các thừa số nguyên tố luôn xuất hiện với số lần bằng nhau dù thứ tự của chúng có thể khác nhau.[45] Do đó, mặc dù có nhiều cách khác nhau để tìm cách phân tích một số thông qua thuật toán phân tích số nguyên nhưng chúng đều phải cho cùng một kết quả. Số nguyên tố vì vậy còn được gọi là “khối gạch cơ bản” của số tự nhiên.[46]
Một số chứng minh về tính duy nhất của phân tích nguyên tố được dựa trên bổ đề Euclid: Nếu
p
{\displaystyle p}
là số nguyên tố và
p
{\displaystyle p}
chia hết một tích
a
b
{\displaystyle ab}
a
{\displaystyle a}
b
{\displaystyle b}
p
{\displaystyle p}
cũng chia hết
a
{\displaystyle a}
hoặc
b
{\displaystyle b}
(hoặc cả hai).[47] Ngược lại, nếu một số
p
{\displaystyle p}
có tính chất khi chia hết một tích thì nó cũng chia hết ít nhất một thừa số trong tích, thì
p
{\displaystyle p}
phải là số nguyên tố.[48]
Sự sống sót vô số số nguyên tố[sửa|sửa mã nguồn]
Có vô số số nguyên tố. Nói cách khác, dãy những số nguyên tố
- 2, 3, 5, 7, 11, 13,…
không bao giờ kết thúc. Phát biểu trên còn được gọi là định lý Euclid theo tên của nhà toán học Hy Lạp cổ đại Euclid vì ông là người đầu tiên chứng minh được phát biểu này. Một số cách chứng minh khác về sự tồn tại vô số số nguyên tố bao gồm một chứng minh bằng giải tích của Euler, chứng minh của Goldbach dựa trên số Fermat,[49] chứng minh của Furstenberg từ tô pô học,[50] hay cách chứng minh đơn giản của Kummer.[51]
Chứng minh của Euclid cho thấy rằng một tập hợp hữu hạn các số nguyên tố bất kỳ là chưa hoàn thành.[52] Thật vậy, xét một tập hợp hữu hạn gồm các số nguyên tố
p
1
,
p
2
,
…
,
p
n
{\displaystyle p_{1},p_{2},\ldots ,p_{n}}
- N = 1 + p 1 ⋅ p 2 ⋯ p n. { \ displaystyle N = 1 + p_ { 1 } \ cdot p_ { 2 } \ cdots p_ { n }. }
Theo định lý cơ bản của số học thì
N
{\displaystyle N}
- N = p 1 ′ ⋅ p 2 ′ ⋯ p m ′ { \ displaystyle N = p ‘ _ { 1 } \ cdot p ‘ _ { 2 } \ cdots p ‘ _ { m } }
với một hoặc nhiều thừa số nguyên tố. N { \ displaystyle N } hoàn toàn có thể được chia hết bởi bất kể thừa số nào trong tích trên, nhưng lại có phần dư bằng 1 khi được chia bởi bất kể số nguyên tố nào trong tập hợp đã cho, nên không có thừa số nguyên tố nào của N { \ displaystyle N } có trong tập hợp đó. Vì không sống sót một tập hợp hữu hạn nào chứa toàn bộ những số nguyên tố nên phải có vô số số nguyên tố .Các số được tạo ra khi cộng thêm 1 vào tích của những số nguyên tố nhỏ nhất được gọi là số Euclid. [ 53 ] Năm số Euclid tiên phong là số nguyên tố, nhưng số Euclid thứ sáu ,
- 1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) = 30031 = 59 ⋅ 509, { \ displaystyle 1 + { \ big ( } 2 \ cdot 3 \ cdot 5 \ cdot 7 \ cdot 11 \ cdot 13 { \ big ) } = 30031 = 59 \ cdot 509, }
là hợp số .
Công thức số nguyên tố[sửa|sửa mã nguồn]
Không có công thức số nguyên tố hiệu suất cao nào được biết đến. Chẳng hạn, không có đa thức khác hằng số nào, kể cả đa thức đa biến, chỉ cho duy nhất những giá trị nguyên tố. [ 54 ] Tuy nhiên, có 1 số ít biểu thức hoàn toàn có thể tạo ra những giá trị nguyên tố, nhưng hiệu suất cao hoạt động giải trí khá thấp. Một công thức như vậy được dựa trên định lý Wilson và hoàn toàn có thể cho giá trị 2 nhiều lần, những giá trị nguyên tố khác đúng một lần. [ 55 ] Một hệ phương trình Diophantine gồm 9 biến và một tham số cũng sống sót với đặc thù : tham số đó là số nguyên tố khi và chỉ khi hệ phương trình thu được có một nghiệm trên tập hợp số tự nhiên. Tính chất đó hoàn toàn có thể được dùng để suy ra một công thức với đặc thù là toàn bộ những giá trị dương của nó đều là số nguyên tố. [ 54 ]
Hai công thức số nguyên tố khác đến từ định lý Mills và một định lý của Wright, cho rằng tồn tại hằng số thực
A
>
1
{\displaystyle A>1}
- ⌊ A 3 n ⌋ và ⌊ 2 ⋯ 2 2 μ ⌋ { \ displaystyle \ left \ lfloor A ^ { 3 ^ { n } } \ right \ rfloor { \ text { và } } \ left \ lfloor 2 ^ { \ cdots ^ { 2 ^ { 2 ^ { \ mu } } } } \ right \ rfloor }
là số nguyên tố với mọi số tự nhiên
n
{\displaystyle n}
bất kỳ ở công thức thứ nhất và bất kỳ số lũy thừa nào trong công thức thứ hai.[56] Ở đây
⌊
⋅
⌋
{\displaystyle \lfloor {}\cdot {}\rfloor }
A
{\displaystyle A}
μ
{\displaystyle \mu }
.[54]
Các bài toán mở[sửa|sửa mã nguồn]
Đã có nhiều giả thuyết được đặt ra liên quan đến số nguyên tố, và đa số giả thuyết như vậy không được chứng minh trong nhiều thập kỷ: cả bốn bài toán của Landau từ năm 1912 vẫn chưa có lời giải.[57] Một trong số đó là giả thuyết Goldbach cho rằng mọi số nguyên chẵn
n
{\displaystyle n}
lớn hơn 2 có thể được viết thành tổng của hai số nguyên tố.[58] Tính đến năm 2014, giả thuyết này đã được xác nhận là đúng với các số lớn đến
n
=
4
⋅
10
18
{\displaystyle n=4\cdot 10^{18}}
Một dạng bài toán khác có liên quan đến khoảng cách nguyên tố, tức là chênh lệch giữa hai số nguyên tố liên tiếp. Có thể thấy được sự tồn tại của các khoảng cách nguyên tố lớn tùy ý bằng cách chú ý rằng dãy số
n
!
+
2
,
n
!
+
3
,
…
,
n
!
+
n
{\displaystyle n!+2,n!+3,\dots ,n!+n}
n
−
1
{\displaystyle n-1}
n
{\displaystyle n}
là số tự nhiên.[64] Tuy nhiên, khoảng cách nguyên tố lớn này bắt đầu xuất hiện sớm hơn so với thời điểm mà lập luận này đã cho.[65] Chẳng hạn, khoảng cách nguyên tố đầu tiên với độ dài bằng 8 nằm giữa hai số 89 và 97, nhỏ hơn nhiều so với
8
!
=
40320
{\displaystyle 8!=40320}
k
{\displaystyle k}
2
k
{\displaystyle 2k}
n
{\displaystyle n}
phải là xấp xỉ
n
{\displaystyle {\sqrt {n}}}
, một kết quả được cho là suy ra từ giả thuyết Riemann, trong khi giả thuyết Cramér đặt khoảng cách lớn nhất đó bằng
O
(
(
log
n
)
2
)
{\displaystyle O((\log n)^{2})}
k
{\displaystyle k}
số nguyên tố, một bộ gồm khoảng cách giữa nhiều hơn hai số nguyên tố. Tính vô hạn và mật độ của chúng là vấn đề chính trong giả thuyết Hardy–Littlewood đầu tiên, vốn có thể được suy ra từ thuật giải heuristic rằng dãy số nguyên tố có tính chất tương tự như một dãy số ngẫu nhiên với mật độ được cho bởi định lý số nguyên tố.[70]
Tính chất trong giải tích[sửa|sửa mã nguồn]
Lý thuyết số giải tích điều tra và nghiên cứu triết lý số qua những khái niệm hàm số liên tục, số lượng giới hạn, chuỗi vô hạn và những khái niệm tương quan đến vô hạn và số nhỏ vô hạn .
Leonhard Euler là người đầu tiên khởi xướng ra ngành nghiên cứu này với thành tựu quan trọng đầu tiên là lời giải cho bài toán Basel. Bài toán yêu cầu tìm giá trị của tổng vô hạn
1
+
1
4
+
1
9
+
1
16
+
…
{\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots }
ζ
(
2
)
{\displaystyle \zeta (2)}
ζ
(
2
)
=
π
2
/
6
{\displaystyle \zeta (2)=\pi ^{2}/6}
6
/
π
2
{\displaystyle 6/\pi ^{2}}
Sự phân phối những số nguyên tố trong khoảng chừng giá trị lớn đó, ví dụ điển hình như có bao nhiêu số nguyên tố nhỏ hơn 1 số ít lớn cho trước, được miêu tả bởi định lý số nguyên tố, nhưng không có công thức cho số nguyên tố thứ n { \ displaystyle n } được biết đến. Ở dạng cơ bản nhất, định lý Dirichlet về cấp số cộng phát biểu rằng đa thức tuyến tính
- p ( n ) = a + b n { \ displaystyle p ( n ) = a + bn }
với a { \ displaystyle a } và b { \ displaystyle b } nguyên tố cùng nhau cho vô số những giá trị nguyên tố. Dạng ngặt nghèo hơn của định lý phát biểu rằng tổng của nghịch đảo những giá trị nguyên tố đó phân kỳ, và những đa thức tuyến tính khác nhau với b { \ displaystyle b } bằng nhau có tỉ lệ số nguyên tố gần như nhau. Mặc dù đã có nhiều giả thuyết được đặt ra về tỉ lệ số nguyên tố trong những đa thức bậc cao nhưng chúng vẫn chưa được chứng tỏ, và không rõ có sống sót một đa thức bậc hai nào hoàn toàn có thể luôn cho những giá trị nguyên tố một cách liên tục hơn hay không .
Chứng minh định lý Euclid bằng giải tích[sửa|sửa mã nguồn]
Chứng minh của Euler về sự sống sót vô số số nguyên tố xét tổng nghịch đảo những số nguyên tố
- 1 2 + 1 3 + 1 5 + 1 7 + ⋯ + 1 p. { \ displaystyle { \ frac { 1 } { 2 } } + { \ frac { 1 } { 3 } } + { \ frac { 1 } { 5 } } + { \ frac { 1 } { 7 } } + \ cdots + { \ frac { 1 } { p } }. }
Euler chứng tỏ được rằng với một số thực x { \ displaystyle x } bất kể, sống sót một số nguyên tố p { \ displaystyle p } sao cho tổng trên lớn hơn x { \ displaystyle x }. [ 73 ] Nếu chỉ có một số ít hữu hạn những số nguyên tố thì tổng này phải đạt giá trị lớn nhất tại số nguyên tố lớn nhất thay vì tăng dần qua những giá trị của x { \ displaystyle x }, do đó có vô số số nguyên tố. Tốc độ ngày càng tăng giá trị của tổng này được miêu tả rõ hơn trong định lý thứ hai của Mertens. [ 74 ] Để so sánh, tổng
- 1 1 2 + 1 2 2 + 1 3 2 + ⋯ + 1 n 2 { \ displaystyle { \ frac { 1 } { 1 ^ { 2 } } } + { \ frac { 1 } { 2 ^ { 2 } } } + { \ frac { 1 } { 3 ^ { 2 } } } + \ cdots + { \ frac { 1 } { n ^ { 2 } } } }
không tăng đến vô hạn khi n { \ displaystyle n } tiến đến vô hạn ( xem bài toán Basel ). Trong trường hợp này, số nguyên tố Open tiếp tục hơn so với bình phương những số tự nhiên, mặc dầu cả hai tập hợp đều là vô hạn. [ 75 ] Định lý Brun phát biểu rằng tổng nghịch đảo những số nguyên tố sinh đôi
- ( 1 3 + 1 5 ) + ( 1 5 + 1 7 ) + ( 1 11 + 1 13 ) + ⋯ { \ displaystyle \ left ( { { \ frac { 1 } { 3 } } + { \ frac { 1 } { 5 } } } \ right ) + \ left ( { { \ frac { 1 } { 5 } } + { \ frac { 1 } { 7 } } } \ right ) + \ left ( { { \ frac { 1 } { 11 } } + { \ frac { 1 } { 13 } } } \ right ) + \ cdots }
là hữu hạn. Do định lý này nên không hề vận dụng cách của Euler để chứng tỏ giả thuyết số nguyên tố sinh đôi rằng có vô số cặp số nguyên tố sinh đôi. [ 75 ]
Số lượng số nguyên tố nằm dưới 1 số ít cho trước[sửa|sửa mã nguồn]
Hàm đếm số nguyên tố
π
(
n
)
{\displaystyle \pi (n)}
n
{\displaystyle n}
.[76] Ví dụ,
π
(
11
)
=
5
{\displaystyle \pi (11)=5}
π
(
n
)
{\displaystyle \pi (n)}
nhanh hơn so với khi liệt kê tất cả các số nguyên tố lớn đến
n
{\displaystyle n}
, chẳng hạn như thuật toán Meissel–Lehmer.[77] Định lý số nguyên tố phát biểu rằng
π
(
n
)
{\displaystyle \pi (n)}
tiệm cận với
n
/
log
n
{\displaystyle n/\log n}
- π ( n ) ∼ n log n, { \ displaystyle \ pi ( n ) \ sim { \ frac { n } { \ log n } }, }
nghĩa là tỉ số giữa
π
(
n
)
{\displaystyle \pi (n)}
và phân số ở vế phải tiến về 1 khi
n
{\displaystyle n}
tăng đến vô hạn.[78] Kéo theo đó, xác suất để một số nhỏ hơn
n
{\displaystyle n}
được chọn ngẫu nhiên là số nguyên tố tỉ lệ nghịch với số chữ số của
n
{\displaystyle n}
.[79] Đồng thời, số nguyên tố thứ
n
{\displaystyle n}
tỉ lệ thuận với
n
log
n
{\displaystyle n\log n}
log
n
{\displaystyle \log n}
π
(
n
)
{\displaystyle \pi (n)}
được cho bởi tích phân logarit bù[78]
- π ( n ) ∼ Li ( n ) = ∫ 2 n d t log t. { \ displaystyle \ pi ( n ) \ sim \ operatorname { Li } ( n ) = \ int _ { 2 } ^ { n } { \ frac { dt } { \ log t } }. }
Cấp số cộng[sửa|sửa mã nguồn]
Cấp số cộng là một dãy số hữu hạn hoặc vô hạn sao cho những số liên tục trong dãy đều có chênh lệch bằng nhau. [ 81 ] Chênh lệch đó được gọi là mô đun ( công sai ) của cấp số cộng. [ 82 ] Ví dụ ,
- 3, 12, 21, 30, 39,…
là cấp số cộng vô hạn với mô đun 9. Trong một cấp số cộng, phép chia của toàn bộ những số cho mô đun đều cho số dư bằng nhau ; trong ví dụ trên, số dư đó bằng 3. Vì cả mô đun 9 và số dư 3 đều là bội của 3 nên những thành phần khác trong dãy cũng vậy. Do đó, cấp số cộng đã cho chỉ chứa một số nguyên tố duy nhất, đó chính là số 3. Tổng quát, cấp số cộng vô hạn
- a, a + q, a + 2 q, a + 3 q, … { \ displaystyle a, a + q, a + 2 q, a + 3 q, \ dots }
có thể chứa nhiều hơn một số nguyên tố chỉ khi số dư
a
{\displaystyle a}
và mô đun
q
{\displaystyle q}
Số nguyên tố trong cấp số cộng mô đun 9. Mỗi hàng trong thanh nhỏ nằm ngang chỉ một trong chín cấp số cộng mod 9 khác nhau, trong đó số nguyên tố được ghi lại màu đỏ. Cấp số cộng 0, 3 hoặc 6 mod 9 chỉ chứa nhiều nhất một số nguyên tố ( số 3 ) ; những cấp số cộng còn lại là 2, 4, 5, 7 và 8 mod 9 chứa vô số số nguyên tố với số lượng số nguyên tố như nhau trong mỗi cấp số cộngĐịnh lý Green – Tao cho thấy sống sót những cấp số cộng hữu hạn dài tùy ý chỉ chứa những số nguyên tố. [ 35 ] [ 84 ]
Giá trị nguyên tố của đa thức bậc hai[sửa|sửa mã nguồn]
4 n 2 − 2 n + 41 { \ displaystyle 4 n ^ { 2 } – 2 n + 41 }
- n 2 − n + 41 { \ displaystyle n ^ { 2 } – n + 41 }
cho giá trị là số nguyên tố với
1
≤
n
≤
40
{\displaystyle 1\leq n\leq 40}
n
{\displaystyle n}
lớn hơn 40.[85][86] Việc tìm ra giải thích cho hiện tượng này chính là tiền đề của lý thuyết số đại số với số Heegner và bài toán lớp số.[87] Giả thuyết F của Hardy–Littlewood dự đoán mật độ số nguyên tố trong các giá trị của đa thức bậc hai với hệ số nguyên về mặt tích phân logarit và hệ số của đa thức. Không có đa thức bậc hai nào được chứng minh là chỉ cho các giá trị nguyên tố.[88]
Xoắn Ulam sắp xếp những số tự nhiên thành một mặt phẳng hai chiều, xoắn ở những hình vuông vắn đồng tâm quanh điểm gốc với số nguyên tố được ghi lại. Dễ thấy trong ví dụ này, những số nguyên tố chỉ tập trung chuyên sâu ở một số ít đường chéo nhất định, ý niệm rằng có 1 số ít đa thức bậc hai cho giá trị nguyên tố tiếp tục hơn những đa thức khác. [ 88 ]
Hàm zeta và giả thuyết Riemann[sửa|sửa mã nguồn]
Đồ thị giá trị tuyệt đối của hàm zeta
Giả thuyết Riemann (1859) là một trong những bài toán chưa được giải nổi tiếng nhất toán học và một là trong bảy bài toán thiên niên kỷ, yêu cầu tìm các nghiệm số của hàm zeta Riemann
ζ
(
s
)
{\displaystyle \zeta (s)}
s
{\displaystyle s}
- ζ ( s ) = ∑ n = 1 ∞ 1 n s = ∏ p nguyên tố 1 1 − p − s. { \ displaystyle \ zeta ( s ) = \ sum _ { n = 1 } ^ { \ infty } { \ frac { 1 } { n ^ { s } } } = \ prod _ { p { \ text { nguyên tố } } } { \ frac { 1 } { 1 – p ^ { – s } } }. }
Sự bằng nhau này giữa một tổng và một tích (do Euler tìm ra) được gọi là tích Euler.[89] Tích Euler có thể được suy ra từ định lý cơ bản của số học và cho thấy sự liên hệ giữa hàm zeta và số nguyên tố.[90] Nó dẫn đến một cách chứng minh khác về sự tồn tại vô số số nguyên tố: nếu chỉ có một số hữu hạn số nguyên tố thì dấu bằng giữa tổng và tích cũng xảy ra tại
s
=
1
{\displaystyle s=1}
1
+
1
2
+
1
3
+
…
{\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }
Giả thuyết Riemann phát biểu rằng nghiệm số của hàm zeta là toàn bộ những số âm chẵn hoặc những số phức với phần thực bằng 50%. [ 92 ] Chứng minh bắt đầu của định lý số nguyên tố được dựa trên dạng không ngặt nghèo của giả thuyết này cho rằng không có nghiệm số nào có phần thực bằng 1, [ 93 ] [ 94 ] mặc dầu còn có thêm một số ít cách chứng tỏ cơ bản khác. [ 95 ] Hàm đếm số nguyên tố hoàn toàn có thể được màn biểu diễn bởi công thức tường minh của Riemann thành một tổng mà trong đó, mỗi số hạng đến từ một nghiệm số của hàm zeta : số hạng chính của tổng là tích phân logarit và những số hạng còn lại làm cho giá trị của tổng giao động quanh số hạng chính đó. [ 96 ] Trong trường hợp này, những nghiệm số làm ảnh hưởng tác động đến sự phân phối những số nguyên tố. Nếu giả thuyết Riemann là đúng, độ xê dịch đó sẽ nhỏ lại và sự phân phối tiệm cận những số nguyên tố được cho bởi định lý số nguyên tố cũng đúng trên những khoảng chừng nhỏ hơn rất nhiều ( có độ dài gần bằng căn bậc hai của x { \ displaystyle x } so với khoảng chừng nằm gần 1 số ít x { \ displaystyle x } ). [ 94 ]
Đại số trừu tượng[sửa|sửa mã nguồn]
Số học mô đun và trường hữu hạn[sửa|sửa mã nguồn]
Số học mô đun là một dạng khác của số học thông thường chỉ dùng các số
{
0
,
1
,
2
,
…
,
n
−
1
}
{\displaystyle \{0,1,2,\dots ,n-1\}}
n
{\displaystyle n}
được gọi là mô đun. Bất kỳ số tự nhiên nào khác đều có thể được ánh xạ vào hệ thống này bằng cách thay nó bằng số dư của nó khi được chia bởi
n
{\displaystyle n}
.[97] Mô đun tổng, hiệu và tích được tính bằng cách thực hiện phép thế bằng số dư trong phép chia của tổng, hiệu hoặc tích các số nguyên thông thường.[98] Sự bằng nhau giữa các số nguyên có liên quan đến khái niệm đồng dư trong số học mô đun:
x
{\displaystyle x}
và
y
{\displaystyle y}
x
≡
y
mod
n
{\displaystyle x\equiv y{\bmod {n}}}
n
{\displaystyle n}
cho số dư bằng nhau.[99] Tuy nhiên, trong hệ thống số đó, chỉ có thể xảy ra phép chia cho một số khác 0 khi và chỉ khi mô đun là số nguyên tố. Chẳng hạn, với mô đun 7, có thể tồn tại phép chia cho 3:
2
/
3
≡
3
mod
7
{\displaystyle 2/3\equiv 3{\bmod {7}}}
2
≡
9
mod
7
{\displaystyle 2\equiv 9{\bmod {7}}}
2
/
3
≡
x
mod
6
{\displaystyle 2/3\equiv x{\bmod {6}}}
Bằng số học mô đun, có thể suy ra được một số định lý về số nguyên tố. Ví dụ, định lý nhỏ Fermat phát biểu rằng nếu
a
≢
0
{\displaystyle a\not \equiv 0}
p
{\displaystyle p}
) thì
a
p
−
1
≡
1
{\displaystyle a^{p-1}\equiv 1}
p
{\displaystyle p}
).[101] Lấy tổng trên tất cả giá trị của
a
{\displaystyle a}
, ta được phương trình
- ∑ a = 1 p − 1 a p − 1 ≡ ( p − 1 ) ⋅ 1 ≡ − 1 ( mod p ), { \ displaystyle \ sum _ { a = 1 } ^ { p-1 } a ^ { p-1 } \ equiv ( p-1 ) \ cdot 1 \ equiv – 1 { \ pmod { p } }, }
đúng khi
p
{\displaystyle p}
là số nguyên tố. Giả thuyết Giuga cho rằng phương trình này là điều kiện đủ để
p
{\displaystyle p}
là số nguyên tố.[102] Theo định lý Wilson, một số nguyên
p
>
1
{\displaystyle p>1}
p
{\displaystyle p}
. Với một hợp số
n
=
r
⋅
s
{\displaystyle \;n=r\cdot s\;}
(
n
−
1
)
!
{\displaystyle (n-1)!}
(
n
−
1
)
!
≡
−
1
(
mod
n
)
{\displaystyle (n-1)!\equiv -1{\pmod {n}}}
Cấp
p
{\displaystyle p}
-adic
ν
p
(
n
)
{\displaystyle \nu _{p}(n)}
n
{\displaystyle n}
là số lần xuất hiện của
p
{\displaystyle p}
trong phân tích nguyên tố của
n
{\displaystyle n}
. Khái niệm này có thể được mở rộng cho số hữu tỉ: cấp
p
{\displaystyle p}
-adic của một phân số
m
/
n
{\displaystyle m/n}
ν
p
(
m
)
−
ν
p
(
n
)
{\displaystyle \nu _{p}(m)-\nu _{p}(n)}
p
{\displaystyle p}
-adic
|
q
|
p
{\displaystyle |q|_{p}}
q
{\displaystyle q}
là
|
q
|
p
=
p
−
ν
p
(
q
)
{\displaystyle |q|_{p}=p^{-\nu _{p}(q)}}
p
{\displaystyle p}
-adic của nó thì các thừa số
p
{\displaystyle p}
trong phân tích nguyên tố của số nguyên đó bị khử và chỉ còn lại các thừa số nguyên tố khác. Giống như khi đo khoảng cách giữa hai số thực bằng giá trị tuyệt đối thông thường, khoảng cách giữa hai số hữu tỉ có thể được đo bằng độ dài
p
{\displaystyle p}
-adic, tức là giá trị tuyệt đối
p
{\displaystyle p}
-adic của hiệu hai số đó. Theo định nghĩa khoảng cách đó, hai số được gọi là gần nhau (có khoảng cách nhỏ) khi hiệu giữa chúng có thể chia hết bởi một lũy thừa bậc cao của
p
{\displaystyle p}
. Bằng cùng một cách mà số thực được tạo thành từ số hữu tỉ và khoảng cách giữa chúng cùng một số giá trị giới hạn được thêm vào để hợp lại thành một trường đầy đủ, các số hữu tỉ với khoảng cách
p
{\displaystyle p}
có thể được mở rộng sang một trường đầy đủ khác được gọi là số
p
{\displaystyle p}
-adic.[104][105]
Các khái niệm về cấp, giá trị tuyệt đối và trường không thiếu suy ra từ chúng hoàn toàn có thể được khái quát hóa cho trường số đại số và định chuẩn của chúng ( ánh xạ nhất định từ nhóm nhân của trường đó sang một nhóm cộng được sắp toàn phần ), giá trị tuyệt đối ( ánh xạ nhân nhất định từ trường đó sang số thực ), [ 104 ] và vị trí ( sự lan rộng ra thành một trường vừa đủ từ một tập trù mật cho trước ). [ 106 ] Chẳng hạn, sự lan rộng ra từ tập số hữu tỉ sang tập số thực là một vị trí mà tại đó khoảng cách giữa hai số là giá trị tuyệt đối thường thì của hiệu hai số đó. Ánh xạ tương ứng sang một nhóm cộng là logarit của giá trị tuyệt đối đó, mặc dầu nó không thỏa mãn nhu cầu tổng thể nhu yếu của một định chuẩn. Theo định lý Ostrowski, trước khái niệm tự nhiên về tương tự, số thực và số p { \ displaystyle p } – adic cùng cấp và giá trị tuyệt đối của chúng là định chuẩn, giá trị tuyệt đối và vị trí duy nhất trên tập số hữu tỉ. [ 104 ] Nguyên lý Hasse cho phép giải nhiều bài toán trên số hữu tỉ bằng cách hợp những nghiệm từ những vị trí của chúng lại với nhau, một lần nữa nhấn mạnh vấn đề tầm quan trọng của số nguyên tố trong kim chỉ nan số. [ 107 ]
Phần tử nguyên tố trong vành[sửa|sửa mã nguồn]
Vành giao hoán là một cấu trúc đại số có định nghĩa phép cộng, phép trừ và phép nhân. Tập số nguyên là một vành và số nguyên tố trong tập đó đã được khái quát hóa sang lý thuyết vành với thuật ngữ phần tử nguyên tố và phần tử tối giản. Một phần tử
p
{\displaystyle p}
của vành
R
{\displaystyle R}
p
{\displaystyle p}
chia hết tích
x
y
{\displaystyle xy}
R
{\displaystyle R}
thì nó cũng chia hết ít nhất một trong hai phần tử
x
{\displaystyle x}
và
y
{\displaystyle y}
. Một phần tử được gọi là phần tử tối giản nếu nó không phải phần tử đơn vị, cũng không phải là tích của hai phần tử khác phần tử đơn vị. Trong vành số nguyên, các phần tử nguyên tố và tối giản tạo thành cùng một tập hợp
- { …, − 11, − 7, − 5, − 3, − 2, 2, 3, 5, 7, 11, … }. { \ displaystyle \ { \ dots, – 11, – 7, – 5, – 3, – 2,2,3,5,7,11, \ dots \ } \ ,. }
Trong một vành bất kể, mọi thành phần nguyên tố đều là thành phần tối giản. Phát biểu ngược lại của nó chỉ đúng trong miền nghiên cứu và phân tích nhân tử duy nhất. [ 108 ]
Định lý cơ bản của số học là đúng (theo định nghĩa) trong miền phân tích nhân tử duy nhất. Ví dụ về một miền như thế là vành số nguyên Gauss
Z
[
i
]
{\displaystyle \mathbb {Z} [i]}
![{\displaystyle \mathbb {Z} [i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffa94e9e2e6d9e5e5373d5fafb954b902743fde "Số nguyên tố là gì? 201")
a
+
b
i
{\displaystyle a+bi}
i
{\displaystyle i}
a
{\displaystyle a}
và
b
{\displaystyle b}
là số nguyên bất kỳ. Các phần tử nguyên tố của vành đó được gọi là số nguyên tố Gauss. Một số nguyên tố trong vành số nguyên có thể không phải là số nguyên tố trong vành số nguyên Gauss; chẳng hạn, số 2 có thể được viết thành tích của hai số nguyên tố Gauss
1
+
i
{\displaystyle 1+i}
1
−
i
{\displaystyle 1-i}
p
{\displaystyle p}
có thể được biểu diễn thành tổng của hai số chính phương,
p
=
x
2
+
y
2
{\displaystyle p=x^{2}+y^{2}}
p
=
(
x
+
i
y
)
(
x
−
i
y
)
{\displaystyle p=(x+iy)(x-iy)}
p
{\displaystyle p}
đồng dư với 1 mod 4.[110]
Không phải mọi vành đều là miền phân tích nhân tử duy nhất. Chẳng hạn, trong vành các số
a
+
b
−
5
{\displaystyle a+b{\sqrt {-5}}}
a
{\displaystyle a}
và
b
{\displaystyle b}
là số nguyên), số 21 có hai cách phân tích:
21
=
3
⋅
7
=
(
1
+
2
−
5
)
(
1
−
2
−
5
)
{\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}
Phổ của một vành là một khoảng trống hình học mà những điểm trong đó là những i-đê-an nguyên tố của vành đó. [ 112 ] Thuật ngữ này giúp ích nhiều cho hình học đại số và nhiều khái niệm tương quan khác cũng Open trong hình học và kim chỉ nan số. Chẳng hạn, sự nghiên cứu và phân tích hoặc phân loại i-đê-an nguyên tố khi vận dụng trong một trường lan rộng ra, một bài toán cơ bản của kim chỉ nan số đại số, thì có tương đương với sự phân loại trong hình học. Các khái niệm này thậm chí còn còn hoàn toàn có thể tương hỗ giải một số ít bài toán đặc biệt quan trọng tương quan đến số nguyên trong kim chỉ nan số. Ví dụ, hoàn toàn có thể dùng i-đê-an nguyên tố trong vành số nguyên của trường số bậc hai để chứng tỏ luật tương hỗ bậc hai, một phát biểu về sự sống sót của biểu thức căn bậc hai mô đun một số nguyên tố nguyên. [ 113 ] Những cố gắng nỗ lực bắt đầu để chứng tỏ định lý cuối của Fermat đã dẫn đến sự sinh ra khái niệm số nguyên tố chính quy, những số nguyên tố nguyên tương quan đến sự không sống sót nghiên cứu và phân tích nhân tử duy nhất trong trường số nguyên chia đường tròn. [ 114 ] Bài toán có bao nhiêu số nguyên tố nguyên hoàn toàn có thể được nghiên cứu và phân tích thành một tích gồm nhiều i-đê-an nguyên tố trong một trường số đại số được xử lý bằng định lý tỷ lệ Chebotarev mà khi được vận dụng cho số nguyên chia đường tròn thì có trường hợp đặc biệt quan trọng là định lý Dirichlet về số nguyên tố trong cấp số cộng. [ 115 ]
Lý thuyết nhóm[sửa|sửa mã nguồn]
Trong lý thuyết nhóm hữu hạn, định lý Sylow phát biểu rằng nếu lũy thừa của một số nguyên tố
p
n
{\displaystyle p^{n}}
p
n
{\displaystyle p^{n}}
. Theo định lý Lagrange, một nhóm với cấp nguyên tố là nhóm cyclic, và theo định lý Burnside thì một nhóm có cấp chia hết được bởi đúng hai số nguyên tố là nhóm giải được.[116]
Phương pháp tính[sửa|sửa mã nguồn]
Bánh răng nhỏ trong một thiết bị nông nghiệp có 13 răng ( là số nguyên tố ) và bánh răng vừa có 21 răng ( nguyên tố cùng nhau với 13 ) .Trong một thời hạn dài, kim chỉ nan số nói chung và ngành điều tra và nghiên cứu số nguyên tố nói riêng từng được xem là ví dụ tầm cỡ về toán học thuần túy khi không có ứng dụng nào ngoài khoanh vùng phạm vi toán học, [ b ] ngoại trừ việc dùng những bánh răng với số răng là số nguyên tố để hạn chế mài mòn. [ 117 ] Thậm chí, 1 số ít nhà kim chỉ nan số như nhà toán học người Anh G. H. Hardy còn tự hào về chính họ khi làm những khu công trình điều tra và nghiên cứu trọn vẹn không có ý nghĩa quân sự gì. [ 118 ]Góc nhìn này đã bị xóa bỏ vào những năm 1970, khi số nguyên tố đã hoàn toàn có thể được dùng làm cơ sở để tạo ra những thuật toán mật mã hóa khóa công khai minh bạch. [ 32 ] Những ứng dụng này đã góp thêm phần tăng cường hoạt động giải trí điều tra và nghiên cứu thuật toán triển khai phép tính trên số nguyên tố và những giải pháp kiểm tra tính nguyên tố của 1 số ít. Thuật toán kiểm tra tính nguyên tố cơ bản nhất, giải thuật chia thử, quá chậm so với số rất lớn. Một nhóm thuật toán văn minh hoàn toàn có thể vận dụng được cho một số ít bất kể, trong khi còn có những thuật toán hiệu suất cao hơn dành cho những nhóm số đặc biệt quan trọng. Đa số thuật toán kiểm tra tính nguyên tố chỉ cho biết nguồn vào của chúng có phải là số nguyên tố hay không. Một số đoạn chương trình khác còn xuất ra một ( hoặc tổng thể ) thừa số nguyên tố từ đầu vào là hợp số và được gọi là thuật toán phân tích số nguyên. Số nguyên tố cũng có ứng dụng trong điện toán như giá trị tổng kiểm, bảng băm và bộ sinh số giả ngẫu nhiên .
Giải thuật chia thử[sửa|sửa mã nguồn]
Phương pháp đơn giản nhất để kiểm tra tính nguyên tố của một số nguyên
n
{\displaystyle n}
cho trước được gọi là giải thuật chia thử. Thuật toán này chia
n
{\displaystyle n}
cho tất cả số nguyên từ 2 đến căn bậc hai của
n
{\displaystyle n}
. Khi có bất kỳ số nguyên nào chia hết
n
{\displaystyle n}
thì
n
{\displaystyle n}
là hợp số, ngược lại thì nó là số nguyên tố. Các số lớn hơn căn bậc hai đó không cần được kiểm tra, vì khi
n
=
a
⋅
b
{\displaystyle n=a\cdot b}
a
{\displaystyle a}
và
b
{\displaystyle b}
nhỏ hơn hoặc bằng căn bậc hai của
n
{\displaystyle n}
. Một dạng tối ưu khác là chỉ kiểm tra các thừa số nguyên tố trong khoảng đó.[119] Chẳng hạn, để kiểm tra xem 37 có phải là số nguyên tố hay không, thuật toán này chia nó cho các số nguyên tố trong khoảng từ 2 đến √37, đó là số 2, 3 và 5. Cả ba phép chia đều có số dư khác 0 nên 37 chính là số nguyên tố.
Phương pháp này dù đơn thuần nhưng nó không trong thực tiễn khi kiểm tra tính nguyên tố của những số nguyên lớn, vì số phép chia tăng dần theo cấp số nhân khi số chữ số của số nguyên đó càng nhiều. [ 120 ] Tuy nhiên, giải thuật chia thử vẫn được sử dụng để tìm nhanh hợp số với thừa số nhỏ trước khi vận dụng những giải pháp phức tạp hơn so với những số vượt qua được giải thuật đó. [ 121 ]
Sàng Eratosthenes bắt đầu với tất cả các số đều không được đánh dấu (màu xám). Sàng này tìm số đầu tiên không được đánh dấu (màu tối) và đánh dấu bình phương của nó và tất cả các bội lớn hơn sau đó là hợp số (màu sáng hơn). Sau khi đã đánh dấu các bội của 2 (đỏ), 3 (xanh lá), 5 (xanh dương) và 7 (vàng), tất cả các số nguyên tố lớn đến căn bậc hai của kích thước bảng đều đã được xét, và tất cả các số còn lại chưa được đánh dấu (11, 13,…) đều là số nguyên tố (màu cánh sen).
Trước khi máy tính sinh ra, nhiều bảng số liệt kê toàn bộ số nguyên tố hoặc nghiên cứu và phân tích nguyên tố đến một số lượng giới hạn cho trước đã được phát hành thoáng rộng. [ 122 ] Phương pháp cổ xưa nhất để lập list số nguyên tố được gọi là sàng Eratosthenes. [ 123 ] Hình minh họa bên phải cho thấy một dạng tối ưu của chiêu thức này. [ 124 ] Một sàng khác hiệu suất cao hơn để xử lý bài toán đó là sàng Atkin. [ 125 ] Trong toán học nâng cao, triết lý sàng vận dụng những giải pháp tương tự như vào nhiều bài toán khác. [ 126 ]
Kiểm tra tính nguyên tố và chứng tỏ tính nguyên tố[sửa|sửa mã nguồn]
Một số thuật toán hiện đại nhanh nhất để giải quyết bài toán về tính nguyên tố của một số
n
{\displaystyle n}
bất kỳ cho trước là các thuật toán xác suất (Monte Carlo), nghĩa là nó có một khả năng nhỏ ngẫu nhiên cho câu trả lời sai.[127] Chẳng hạn, kiểm tra Solovay–Strassen với một số cho trước
p
{\displaystyle p}
chọn ngẫu nhiên một số
a
{\displaystyle a}
trong khoảng từ 2 đến
p
−
2
{\displaystyle p-2}
a
(
p
−
1
)
/
2
±
1
{\displaystyle a^{(p-1)/2}\pm 1}
p
{\displaystyle p}
hay không.[c] Nếu đúng là như vậy thì nó trả lời “có” và ngược lại thì nó trả lời “không”. Nếu
p
{\displaystyle p}
đúng là số nguyên tố thì nó luôn trả lời “có”, nhưng nếu
p
{\displaystyle p}
là hợp số thì nó trả lời “có” với xác suất lớn nhất là 1/2 và “không” với xác suất nhỏ nhất là 1/2.[128] Nếu thuật toán này được lặp lại
n
{\displaystyle n}
lần trong cùng một số, xác suất lớn nhất để một hợp số vượt qua được thuật toán mọi lần là
1
/
2
n
{\displaystyle 1/2^{n}}
trái lại, một số ít thuật toán khác bảo vệ rằng câu vấn đáp luôn luôn đúng : số nguyên tố sẽ luôn luôn được xác lập là số nguyên tố và hợp số sẽ luôn luôn được xác lập là hợp số. Chẳng hạn, phát biểu này là đúng so với giải thuật chia thử. Những thuật toán với đầu ra bảo vệ đúng chuẩn gồm có thuật toán tất định như phép kiểm tra tính nguyên tố AKS, [ 130 ] và những thuật toán Las Vegas ngẫu nhiên mà trong đó những lựa chọn ngẫu nhiên của thuật toán không tác động ảnh hưởng gì đến tác dụng sau cuối, ví dụ điển hình như một số ít dạng của phép chứng tỏ tính nguyên tố bằng đường cong elliptic. [ 127 ] Khi chiêu thức đường cong elliptic Tóm lại rằng 1 số ít là số nguyên tố, nó cũng xuất ra một ghi nhận tính nguyên tố hoàn toàn có thể được xác nhận nhanh gọn. [ 131 ] Kỹ thuật đường cong elliptic là nhanh nhất trong số những thuật toán với độ đúng mực tuyệt đối, nhưng thời hạn thực thi chỉ được đo dựa trên thực nghiệm thay vì lập luận chứng minh. Kiểm tra AKS có độ phức tạp giám sát được chứng tỏ bằng lập luận toán học nhưng hoạt động giải trí chậm hơn so với kỹ thuật đường cong elliptic. [ 132 ] Các giải pháp này hoàn toàn có thể được dùng để tạo ra những số nguyên tố lớn bằng cách tạo và kiểm tra những số ngẫu nhiên đến khi tìm được một số nguyên tố ; khi đó, một thuật toán kiểm tra Tỷ Lệ hoàn toàn có thể nhanh gọn loại đi hầu hết hợp số trước khi một thuật toán ” chắc như đinh đúng ” được dùng để xác nhận lại rằng những số còn lại là số nguyên tố. [ d ]
Bảng dưới đây liệt kê một số thuật toán như vậy. Thời gian hoạt động được cho theo số được kiểm tra
n
{\displaystyle n}
và số vòng lặp
k
{\displaystyle k}
(đối với thuật toán xác suất). Đồng thời,
ε
{\displaystyle \varepsilon }
log
{\displaystyle \log }
n
{\displaystyle n}
và
k
{\displaystyle k}
.
Các thuật toán đặc biệt quan trọng và số nguyên tố lớn nhất đã biết[sửa|sửa mã nguồn]
Cùng với những thuật toán nói trên vận dụng được cho bất kể số tự nhiên nào, một vài số với dạng đặc biệt quan trọng còn hoàn toàn có thể được kiểm tra tính nguyên tố nhanh hơn. Ví dụ, kiểm tra Lucas – Lehmer hoàn toàn có thể xác lập được một số Mersenne ( lũy thừa của 2 trừ 1 ) có phải là số nguyên tố hay không một cách tất định với thời hạn bằng với một vòng lặp của kiểm tra Miller – Rabin. [ 137 ] Đó là nguyên do kể từ năm 1992 ( tính đến tháng 12 năm 2018 ) số nguyên tố lớn nhất đã biết luôn là một số nguyên tố Mersenne. [ 138 ] Có giả thuyết cho rằng có vô số số nguyên tố Mersenne. [ 139 ]Bảng dưới đây liệt kê những số nguyên tố lớn nhất đã biết theo nhiều dạng khác nhau. Một vài trong số đó được tìm thấy qua điện toán phân tán. Năm 2009, dự án Bất Động Sản Great Internet Mersenne Prime Search đã được trao phần thưởng 100.000 đô la Mỹ cho số nguyên tố tiên phong có tối thiểu 10 triệu chữ số thập phân. [ 140 ] Tổ chức Biên giới Điện tử cũng có phần thưởng lần lượt là 150.000 và 250.000 đô la dành cho số nguyên tố có tối thiểu 100 triệu và 1 tỷ chữ số. [ 141 ]
Phân tích số nguyên[sửa|sửa mã nguồn]
Cho một hợp số
n
{\displaystyle n}
, công việc xuất ra một (hoặc tất cả) thừa số nguyên tố được gọi là phân tích của
n
{\displaystyle n}
. Công việc này khó hơn đáng kể so với kiểm tra tính nguyên tố,[147] và mặc dù tồn tại nhiều thuật toán phân tích nhưng chúng đều chậm hơn so với các phương pháp nhanh nhất để kiểm tra tính nguyên tố. Giải thuật chia thử và thuật toán RHO có thể được dùng để tìm các nhân tử rất nhỏ của
n
{\displaystyle n}
,[121] và thuật toán phân tích bằng đường cong elliptic có thể hiệu quả khi
n
{\displaystyle n}
có các nhân tử lớn vừa phải.[148] Một số phương pháp phù hợp đối với số lớn bất kỳ không phụ thuộc vào độ lớn của nhân tử bao gồm sàng cấp hai và sàng trường số thông thường. Giống như kiểm tra tính nguyên tố, có một số thuật toán phân tích yêu cầu đầu vào có dạng đặc biệt, trong đó có sàng trường số đặc biệt.[149] Tính đến tháng 2 năm 2020 số lớn nhất được phân tích bằng một thuật toán thông thường là RSA-250, một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn.[150]
Thuật toán Shor được cho phép nghiên cứu và phân tích bất kể số nguyên nào với số bước đa thức trong một máy tính lượng tử. [ 151 ] Tuy nhiên, với công nghệ tiên tiến lúc bấy giờ thì thuật toán này chỉ hoạt động giải trí được với những số rất nhỏ. Tính đến tháng 10 năm 2012 số lớn nhất được nghiên cứu và phân tích bằng thuật toán Shor trong một máy tính lượng tử là 21. [ 152 ]
Ứng dụng khác trong điện toán[sửa|sửa mã nguồn]
Một số thuật toán mật mã hóa khóa công khai, chẳng hạn như RSA và trao đổi khóa Diffie−Hellman được dựa trên số nguyên tố lớn (phổ biến nhất là số nguyên tố 2048 bit).[153] RSA dựa vào giả thiết rằng thực hiện phép nhân hai số lớn
x
{\displaystyle x}
và
y
{\displaystyle y}
dễ hơn nhiều so với khi tính
x
{\displaystyle x}
và
y
{\displaystyle y}
(giả sử là hai số nguyên tố cùng nhau) nếu chỉ biết một tích
x
y
{\displaystyle xy}
.[32] Trao đổi khóa Diffie−Hellman dựa vào thực tế rằng có một số thuật toán hiệu quả đối với lũy thừa mô đun (tính
a
b
mod
c
{\displaystyle a^{b}{\bmod {c}}}
Số nguyên tố được sử dụng tiếp tục trong bảng băm. Chẳng hạn giải pháp bắt đầu của Carter và Wegman so với băm phổ quát được dựa vào việc tính hàm băm bằng cách chọn ngẫu nhiên hàm tuyến tính mô đun số nguyên tố lớn. Carter và Wegman đã khái quát hóa giải pháp này cho băm k { \ displaystyle k } – độc lập bằng cách sử dụng đa thức bậc cao mô đun số nguyên tố lớn. [ 155 ] Cũng như trong hàm băm, số nguyên tố được dùng trong kích cỡ của bảng băm dựa trên dò cấp hai để bảo vệ rằng chuỗi dò bao trùm hết bảng đó. [ 156 ]
Một số phương pháp giá trị tổng kiểm được dựa trên kiến thức toán học về số nguyên tố. Chẳng hạn giá trị tổng kiểm dùng trong ISBN được xác định bằng cách lấy tổng của tất cả các chữ số (ngoài chữ số cuối cùng) mô đun 11. Vì 11 là số nguyên tố nên phương pháp này có thể phát hiện các chữ số bị sai và chuyển vị của các chữ số liền kề nhau.[157] Adler-32, một công cụ kiểm tra tổng kiểm khác, sử dụng số học mô đun 65521, số nguyên tố lớn nhất nhỏ hơn
2
16
{\displaystyle 2^{16}}
Các ứng dụng khác[sửa|sửa mã nguồn]
Số nguyên tố là chủ đề trọng tâm của kim chỉ nan số và có nhiều ứng dụng trong những nghành nghề dịch vụ khác của toán học, trong đó có đại số trừu tượng và hình học cơ bản. Ví dụ, hoàn toàn có thể đặt một số lượng số nguyên tố những điểm trên mặt phẳng hai chiều sao cho không có ba điểm nào thẳng hàng, hoặc sao cho một tam giác bất kể với ba đỉnh là ba trong số những điểm đó có kích cỡ lớn. [ 161 ] Một ví dụ khác là tiêu chuẩn Eisenstein, dùng để kiểm tra xem một đa thức có tối giản hay không dựa vào tính chia hết của những thông số cho một số nguyên tố và bình phương của nó. [ 162 ]
Tổng link của hai nút thắt nguyên tốKhái niệm số nguyên tố quan trọng đến mức nó đã được khái quát hóa sang những nhánh khác của toán học. Thông thường, ” nguyên tố ” có nghĩa là ” tối thiểu ” hoặc ” không khai triển, nghiên cứu và phân tích được ” trong trường hợp thích hợp. Ví dụ, trường nguyên tố của một trường cho trước là trường con nhỏ nhất của trường đã cho có chứa cả 0 và 1. Nó hoàn toàn có thể là trường số hữu tỉ hoặc một trường hữu hạn có số lượng thành phần là số nguyên tố. [ 163 ] Một nghĩa thứ hai ám chỉ rằng bất kể đối tượng người dùng nào cũng đều có một cách nghiên cứu và phân tích duy nhất thành những thành phần nguyên tố. Chẳng hạn, trong kim chỉ nan nút thắt, nút thắt nguyên tố là một nút thắt không nghiên cứu và phân tích được, nghĩa là nó không hề được viết thành tổng link của hai nút thắt không tầm thường. Mỗi nút thắt bất kể có một cách màn biểu diễn duy nhất thành tổng link của những nút thắt nguyên tố. [ 164 ] Phân tích nguyên tố của 3 – đa tạp là ví dụ khác của dạng này. [ 165 ]Cùng với toán học và điện toán, số nguyên tố có mối liên hệ với cơ học lượng tử và là hình ảnh ẩn dụ trong nghệ thuật và thẩm mỹ và văn học. Chúng cũng có ứng dụng trong sinh học tiến hóa để lý giải vòng đời của liên họ Ve sầu .
Đa giác vẽ được và phân loại đa giác[sửa|sửa mã nguồn]
Một ngũ giác đều được vẽ bằng thước thẳng và compa. Tính chất này do 5 là số nguyên tố Fermat .Số Fermat là những số có dạng
- F k = 2 2 k + 1, { \ displaystyle F_ { k } = 2 ^ { 2 ^ { k } } + 1, }
với
k
{\displaystyle k}
là số nguyên không âm.[f] Chúng được đặt tên theo Pierre de Fermat, người đã dự đoán rằng tất cả các số dạng này đều là số nguyên tố. Năm số Fermat đầu tiên – 3, 5, 17, 257 và 65.537 – đều là số nguyên tố,[166] nhưng
F
5
{\displaystyle F_{5}}
n
{\displaystyle n}
-giác đều có thể vẽ được bằng thước thẳng và compa khi và chỉ khi tập hợp các thừa số nguyên tố lẻ của
n
{\displaystyle n}
(nếu có) chỉ gồm các số nguyên tố Fermat.[167] Tương tự, một
n
{\displaystyle n}
-giác đều có thể vẽ được bằng thước, compa và thước góc phần ba khi và chỉ khi tập hợp các thừa số nguyên tố của
n
{\displaystyle n}
có chứa số 2 hoặc số 3 cùng một tập hợp (có thể rỗng) các số nguyên tố Pierpont, số nguyên tố có dạng
2
a
3
b
+
1
{\displaystyle 2^{a}3^{b}+1}
Có thể chia một đa giác lồi bất kể thành n { \ displaystyle n } đa giác lồi nhỏ hơn với diện tích quy hoạnh và chu vi bằng nhau khi n { \ displaystyle n } là lũy thừa của một số nguyên tố, nhưng chưa rõ đặc thù này thế nào với những giá trị khác của n { \ displaystyle n }. [ 169 ]
Cơ học lượng tử[sửa|sửa mã nguồn]
Bắt đầu từ khu công trình của Hugh Montgomery và Freeman Dyson vào những năm 1970, nhiều nhà toán học và vật lý suy đoán rằng nghiệm số của hàm zeta Riemann có liên hệ với mức nguồn năng lượng của mạng lưới hệ thống lượng tử. [ 170 ] [ 171 ] Số nguyên tố cũng có ý nghĩa quan trọng trong khoa học thông tin lượng tử nhờ vào những cấu trúc toán học như cơ sở không lệch qua lại và SIC-POVM ( độ đo giá trị toán tử dương đối xứng không thiếu thông tin ). [ 172 ] [ 173 ]
Chu kỳ tiến hóa của liên họ ve sầu chi Magicicada ở Bắc Mỹ có liên quan đến số nguyên tố.[174] Các côn trùng này sống phần lớn cuộc đời dưới dạng ấu trùng dưới lòng đất. Chúng chỉ phát triển dần và chui lên mặt đất sau 7, 13 hoặc 17 năm, từ đó chúng bay, sinh sản và chết sau nhiều nhất vài tuần. Các nhà sinh học giả thiết rằng tính nguyên tố của chu kỳ sinh sản là để tránh đồng bộ với chu kỳ của động vật ăn thịt.[175][176] Ngược lại, chu kỳ ra hoa nhiều năm của tre được cho là số nhẵn, chỉ có các thừa số nguyên tố nhỏ trong phân tích của nó.[177]
Nghệ thuật và văn học[sửa|sửa mã nguồn]
Số nguyên tố đã làm ảnh hưởng đến nhiều nghệ sĩ và nhà văn. Nhà soạn nhạc người Pháp Olivier Messiaen sử dụng số nguyên tố để sáng tác nhạc qua “hiện tượng tự nhiên”. Trong một số sáng tác như La Nativité du Seigneur (1935) và Quatre études de rythme (1949–1950), ông đồng thời áp dụng nhạc tố với độ dài cho bởi các số nguyên tố khác nhau để tạo những nhịp điệu đặc biệt: số 41, 43, 47 và 53 xuất hiện trong khúc luyện thứ ba “Neumes rythmiques”. Theo Messiaen, phong cách sáng tác này “lấy cảm hứng từ vận động tự nhiên, vận động theo hướng tự do và khác biệt”.[178]
Trong tiểu thuyết khoa học viễn tưởng Contact (1985), nhà khoa học Carl Sagan gợi ý rằng phân tích nguyên tố có thể được dùng để tạo mặt phẳng ảnh hai chiều khi liên lạc với người ngoài hành tinh, một ý tưởng mà ông cùng nhà thiên văn người Hoa Kỳ Frank Drake phát triển từ năm 1975.[179] Trong tiểu thuyết The Curious Incident of the Dog in the Night-Time (Bí ẩn về con chó lúc nửa đêm) của Mark Haddon, tác giả đánh số các mục của câu chuyện bằng các số nguyên tố liên tiếp để truyền đạt trạng thái tinh thần của nhân vật chính, một cậu bé có năng khiếu toán học mắc hội chứng Asperger.[180] Số nguyên tố là hình ảnh ẩn dụ cho sự cô đơn trong tiểu thuyết La Solitudine dei Numeri Primi (Nỗi cô đơn của các số nguyên tố) của Paolo Giordano, ở đó chúng được mô tả là “người ngoài cuộc” trong các số nguyên.[181]
Liên kết ngoài[sửa|sửa mã nguồn]
Xem thêm: Chính sách ngự binh ư nông là gì?
Source: https://tbdn.com.vn
Category: 1000 Câu Hỏi Vì Sao
