Wiki - KEONHACAI COPA

Số Carmichael

Trong lý thuyết số, số Carmichael là một hợp số thỏa mãn quan hệ đồng dư số học mô-đun :

cho tất cả các số nguyên nguyên tố cùng nhau với .[1] Chúng được đặt tên theo Robert Carmichael . Số Carmichael là tập con K 1 của các số Knödel . Thuật ngữ "số Carmichael" được NGWH Beeger đưa ra vào năm 1950 (Oysetein Ore đã gọi chúng là số F vào năm 1948).

Tương tự, số Carmichael là một hợp số thỏa mãn

cho tất cả các số nguyên . [2]

Tổng quan[sửa | sửa mã nguồn]

Định lý nhỏ của Fermat phát biểu rằng nếu psố nguyên tố thì với bất kỳ số nguyên b nào, số b p − b là bội số của p . Số Carmichael là hợp số có thuộc tính này. Số Carmichael còn được gọi là giả Fermat hoặc giả Fermat tuyệt đối . Một số Carmichael sẽ vượt qua bài kiểm tra Fermat cho mọi cơ số b nguyên tố cùng nhau với số đó, mặc dù nó không thực sự là số nguyên tố. Điều này làm cho các phép thử dựa trên Định lý Nhỏ của Fermat kém hiệu quả hơn các phép thử nguyên tố có khả năng xảy ra mạnh như phép thử tính nguyên tố Baillie – PSW và phép thử tính nguyên tố Miller – Rabin .

Tuy nhiên, không có số Carmichael nào là giả Euler – Jacobi hoặc giả mạnh đối với mọi nguyên tố cùng nhau với nó .[3] Vì vậy, về lý thuyết, Euler hoặc một phép thử nguyên tố có khả năng xảy ra mạnh có thể chứng minh rằng số Carmichael trên thực tế là hợp số.

Arnault [4] đưa ra số Carmichael gồm 397 chữ số đó là giả mạnh đối với tất cả các số nguyên tố nhỏ hơn 307:

Khi

29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883


là một số nguyên tố gồm 131 chữ số. là thừa số nguyên tố nhỏ nhất của , vì vậy số Carmichael này cũng là một giả (không nhất thiết phải mạnh) đối với tất cả các số nhỏ hơn .

Khi số lượng ngày càng lớn, số lượng số Carmichael ngày càng ít. Ví dụ: có 20.138.200 số Carmichael từ 1 đến 10 21 (xấp xỉ một trong 50 nghìn tỷ (5 · 10 13 ) số).

Khám phá[sửa | sửa mã nguồn]

Korselt là người đầu tiên quan sát các tính chất cơ bản của số Carmichael, nhưng ông không đưa ra bất kỳ ví dụ nào. Năm 1910, Carmichael [5] tìm ra con số đầu tiên và nhỏ nhất như vậy, 561, giải thích cho cái tên "số Carmichael".

Václav Šimerka liệt kê bảy số Carmichael đầu tiên


Sáu số Carmichael tiếp theo là :

Bảy số Carmichael đầu tiên này, từ 561 đến 8911, đều do nhà toán học người Séc Václav Šimerka (de; cs) tìm ra vào năm 1885 [6] (trước đó không chỉ Carmichael mà còn cả Korselt, mặc dù Šimerka không tìm thấy bất cứ điều gì giống như tiêu chí của Korselt). [7] Tuy nhiên các phát hiện của ông không được chú ý.

J. Chernick [8] đã chứng minh một định lý vào năm 1939 có thể được sử dụng để xây dựng một tập con các số Carmichael. Con số là một số Carmichael nếu ba phần tử của nó đều là số nguyên tố. Liệu công thức này có tạo ra số lượng Carmichael vô hạn hay không là một câu hỏi mở (mặc dù nó được ngụ ý bởi phỏng đoán của Dickson ).

Paul Erds lập luận rằng có vô số con số Carmichael. Năm 1994 WR (Đỏ) Alford, Andrew Granville và Carl Pomerance sử dụng một giới hạn trên hằng số Olson để chỉ ra rằng thực sự tồn tại vô số số Carmichael. Cụ thể, họ đã cho thấy với số đủ lớn, Có ít nhất Carmichael số từ 1 đến [9]

Thomas Wright đã chứng minh rằng nếu nguyên tố cùng nhau, thì có vô hạn số Carmichael có dạng , khi . [10]

Löh và Niebuhr năm 1992 đã tìm thấy một số Carmichael rất lớn, bao gồm một số có 1.101.518 thừa số và hơn 16 triệu chữ số. Điều này đã được thay đổi thành 10,333,229,505 thừa số nguyên tố và 295,486,761,787 chữ số, [11] vì vậy số Carmichael lớn nhất đã biết lớn hơn nhiều so với số nguyên tố lớn nhất đã biết .

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 . Boston, MA: Birkhäuser. ISBN 978-0-8176-3743-9. Zbl 0821.11001.
  2. ^ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective . New York: Springer. tr. 133. ISBN 978-0387-25282-7.
  3. ^ D. H. Lehmer (1976). “Strong Carmichael numbers”. J. Austral. Math. Soc. 21 (4): 508–510. doi:10.1017/s1446788700019364. Lehmer proved that no Carmichael number is an Euler-Jacobi pseudoprime to every base relatively prime to it. He used the term strong pseudoprime, but the terminology has changed since then. Strong pseudoprimes are a subset of Euler-Jacobi pseudoprimes. Therefore, no Carmichael number is a strong pseudoprime to every base relatively prime to it.
  4. ^ F. Arnault (tháng 8 năm 1995). “Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases”. Journal of Symbolic Computation. 20 (2): 151–161. doi:10.1006/jsco.1995.1042.
  5. ^ R. D. Carmichael (1910). “Note on a new number theory function”. Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/s0002-9904-1910-01892-9.
  6. ^ V. Šimerka (1885). “Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)”. Časopis Pro Pěstování Matematiky a Fysiky. 14 (5): 221–225. doi:10.21136/CPMF.1885.122245.
  7. ^ Lemmermeyer, F. (2013). “Václav Šimerka: quadratic forms and factorization”. LMS Journal of Computation and Mathematics. 16: 118–129. doi:10.1112/S1461157013000065.
  8. ^ Chernick, J. (1939). “On Fermat's simple theorem” (PDF). Bull. Amer. Math. Soc. 45 (4): 269–274. doi:10.1090/S0002-9904-1939-06953-X.
  9. ^ W. R. Alford; Andrew Granville; Carl Pomerance (1994). “There are Infinitely Many Carmichael Numbers” (PDF). Annals of Mathematics. 140 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.
  10. ^ Thomas Wright (2013). “Infinitely many Carmichael Numbers in Arithmetic Progressions”. Bull. London Math. Soc. 45 (5): 943–952. arXiv:1212.5850. doi:10.1112/blms/bdt013.
  11. ^ W.R. Alford; và đồng nghiệp (2014). “Constructing Carmichael numbers through improved subset-product algorithms”. Math. Comp. 83 (286): 899–915. arXiv:1203.6664. doi:10.1090/S0025-5718-2013-02737-8.
Wiki - Keonhacai copa chuyên cung cấp kiến thức thể thao, keonhacai tỷ lệ kèo, bóng đá, khoa học, kiến thức hằng ngày được chúng tôi cập nhật mỗi ngày mà bạn có thể tìm kiếm tại đây có nguồn bài viết: https://vi.wikipedia.org/wiki/S%E1%BB%91_Carmichael