กลับไปหน้าบทความ

อ่าน 4 นาที

ข้อสันนิษฐานฟังก์ชันโทเทียนต์ของคาร์ไมเคิล

การคาดเดา/ฟังก์ชันการคูณ/ปัญหาที่แก้ไม่ได้ในทฤษฎีจำนวน

ในทางคณิตศาสตร์ข้อสันนิษฐานเรื่องฟังก์ชันโทเทียนต์ของคาร์ไมเคิลเกี่ยวข้องกับความหลากหลายของค่าของฟังก์ชันโทเทียนต์ของออยเลอร์φ(n){\displaystyle \varphi

ข้อสันนิษฐานฟังก์ชันโทเทียนต์ของคาร์ไมเคิล

ในทางคณิตศาสตร์ข้อสันนิษฐานเรื่องฟังก์ชันโทเทียนต์ของคาร์ไมเคิลเกี่ยวข้องกับความหลากหลายของค่าของฟังก์ชันโทเทียนต์ของออยเลอร์φ(n){\displaystyle \varphi (n)}ซึ่งนับจำนวนเต็มที่น้อยกว่าและเป็นจำนวนเฉพาะสัมพัทธ์กับn{\displaystyle n}ระบุว่า สำหรับทุกๆn{\displaystyle n}มีจำนวนเต็มอื่นอย่างน้อยหนึ่งจำนวนn{\displaystyle m\neq n}โดยที่φ()=φ(n){\displaystyle \varphi (m)=\varphi (n)}โร เบิร์ต คาร์ไมเคิล เป็นคนแรกที่กล่าวถึง ข้อสันนิษฐานนี้ในปี 1907 แต่ในฐานะทฤษฎีบท มากกว่าข้อสันนิษฐาน อย่างไรก็ตาม การพิสูจน์ของเขามีข้อบกพร่อง และในปี 1922 เขาจึงถอนคำกล่าวอ้างของเขาและ ระบุว่าข้อสันนิษฐานนี้เป็นปัญหาที่ยังไม่มีคำตอบ

ตัวอย่าง

ฟังก์ชันโทเทียนต์φ(n){\displaystyle \varphi (n)}เท่ากับ 2 เมื่อn{\displaystyle n}คือค่าใดค่าหนึ่งในสามค่า ได้แก่ 3, 4 และ 6 ดังนั้น ถ้าเราเลือกค่าใดค่าหนึ่งในสามค่านี้เป็นn{\displaystyle n}จากนั้นสามารถใช้ค่าใดค่าหนึ่งจากสองค่าที่เหลือเป็นค่าได้{\displaystyle m}ซึ่งφ()=φ(n){\displaystyle \varphi (m)=\varphi (n)}.

ในทำนองเดียวกัน ค่าโทเทียนต์จะเท่ากับ 4 เมื่อn{\displaystyle n}คือค่าหนึ่งในสี่ค่า ได้แก่ 5, 8, 10 และ 12 และมีค่าเท่ากับ 6 เมื่อn{\displaystyle n}คือค่าใดค่าหนึ่งในสี่ค่า ได้แก่ 7, 9, 14 และ 18 ในแต่ละกรณีจะมีค่ามากกว่าหนึ่งค่าn{\displaystyle n}มีค่าเท่ากันของφ(n){\displaystyle \varphi (n)}.

ข้อสันนิษฐานนี้กล่าวว่าปรากฏการณ์ค่าซ้ำนี้เกิดขึ้นกับทุกๆn{\displaystyle n}.

เค{\displaystyle k}ค่านิยมn{\displaystyle n}โดยที่φ(n)=เค{\displaystyle \varphi (n)=k}(ลำดับA032447ในOEIS )จำนวนค่าดังกล่าว(ลำดับA014197ในOEIS )
11, 22
23, 4, 63
45, 8, 10, 124
67, 9, 14, 184
815, 16, 20, 24, 305
1011, 222
1213, 21, 26, 28, 36, 426
1617, 32, 34, 40, 48, 606
1819, 27, 38, 544
2025, 33, 44, 50, 665
2223, 462
2435, 39, 45, 52, 56, 70, 72, 78, 84, 9010
2829, 582
3031, 622
3251, 64, 68, 80, 96, 102, 1207
3637, 57, 63, 74, 76, 108, 114, 1268
4041, 55, 75, 82, 88, 100, 110, 132, 1509
4243, 49, 86, 984
4469, 92, 1383
4647, 942
4865, 104, 105, 112, 130, 140, 144, 156, 168, 180, 21011
5253, 1062
5481, 1622
5687, 116, 1743
5859, 1182
6061, 77, 93, 99, 122, 124, 154, 186, 1989
6485, 128, 136, 160, 170, 192, 204, 2408
6667, 1342
7071, 1422
7273, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 27017

ขอบเขตล่าง

มีขอบเขตล่างที่ สูงมาก สำหรับข้อสันนิษฐานของคาร์ไมเคิล ซึ่งค่อนข้างง่ายต่อการกำหนด คาร์ไมเคิลเองได้พิสูจน์แล้วว่าตัวอย่างค้านใดๆ ต่อข้อสันนิษฐานของเขา (นั่นคือ ค่า)n{\displaystyle n}โดยที่φ(n){\displaystyle \varphi (n)}ค่า (ซึ่งแตกต่างจากค่า totient ของจำนวนอื่นๆ ทั้งหมด) จะต้องมีค่าอย่างน้อย10³⁷และวิกเตอร์ คลีได้ขยายผลลัพธ์นี้ไปถึง10⁴⁰⁰ขอบเขตล่างของ10107{\displaystyle 10^{10^{7}}}ได้รับมาจาก Schlafly และWagonและขอบเขตล่างของ101010{\displaystyle 10^{10^{10}}}ได้รับการตัดสินโดยเควิน ฟอร์ดในปี 1998 [ 1 ]

เทคนิคการคำนวณที่อยู่เบื้องหลังขอบเขตล่างเหล่านี้ขึ้นอยู่กับผลลัพธ์สำคัญบางประการของ Klee ซึ่งทำให้สามารถแสดงได้ว่าตัวอย่างค้านที่เล็กที่สุดจะต้องหารลงตัวด้วยกำลังสองของจำนวนเฉพาะที่หารค่าโทเทียนต์ของมัน ผลลัพธ์ของ Klee บ่งชี้ว่า 8 และจำนวนเฉพาะของแฟร์มาต์ (จำนวนเฉพาะในรูปแบบ )22เค+1{\displaystyle 2^{2^{k}}+1}) ยกเว้น 3 ไม่สามารถหารตัวอย่างค้านที่เล็กที่สุดได้ ดังนั้น การพิสูจน์ข้อสันนิษฐานจึงเทียบเท่ากับการพิสูจน์ว่าข้อสันนิษฐานนั้นเป็นจริงสำหรับจำนวนเต็มทั้งหมดที่สอดคล้องกับ 4  (mod  8)

ผลลัพธ์อื่นๆ

ฟอร์ดพิสูจน์แล้วว่าหากมีตัวอย่างค้านต่อข้อสันนิษฐาน สัดส่วนบวก (ในแง่ของความหนาแน่นเชิงอะซิมโทติก) ของจำนวนเต็มก็ถือเป็นตัวอย่างค้านเช่นกัน[ 1 ]

แม้ว่าข้อสันนิษฐานนี้จะเป็นที่เชื่อกันอย่างกว้างขวาง แต่คาร์ล โพเมอรองซ์ได้ให้เงื่อนไขที่เพียงพอสำหรับจำนวนเต็มn{\displaystyle n}เพื่อเป็นตัวอย่างค้านต่อข้อสันนิษฐาน( Pomerance 1974 )ตามเงื่อนไขนี้n{\displaystyle n}เป็นตัวอย่างค้าน ถ้าสำหรับจำนวนเฉพาะทุกตัวพี{\displaystyle p}โดยที่พี1{\displaystyle p-1}แบ่งแยกφ(n){\displaystyle \varphi (n)},พี2{\displaystyle p^{2}}แบ่งแยกn{\displaystyle n}อย่างไรก็ตามโพเมอรองซ์แสดงให้เห็นว่าการมีอยู่ของจำนวนเต็มดังกล่าวเป็นไปได้ยากมาก โดยพื้นฐานแล้ว สามารถแสดงได้ว่าถ้าเงื่อนไขแรกเป็นจริงเค{\displaystyle k}จำนวนเฉพาะพี{\displaystyle p}สอดคล้องกับ 1  (มอด q{\displaystyle q}) (ที่ไหนq{\displaystyle q}(เป็นจำนวนเฉพาะ) ทั้งหมดมีค่าน้อยกว่าqเค+1{\displaystyle q^{k+1}}ดังนั้น จำนวนเต็มดังกล่าวจะต้องหารลงตัวด้วยจำนวนเฉพาะทุกจำนวน และด้วยเหตุนี้จึงไม่มีอยู่จริง ไม่ว่าในกรณีใด การพิสูจน์ว่าตัวอย่างค้านของ Pomerance ไม่มีอยู่จริงนั้นยังห่างไกลจากการพิสูจน์ข้อสันนิษฐานของ Carmichael มาก อย่างไรก็ตาม หากมันมีอยู่จริง ก็จะมีตัวอย่างค้านมากมายนับไม่ถ้วนตามที่ Ford กล่าวไว้

อีกวิธีหนึ่งในการกล่าวถึงสมมติฐานของคาร์ไมเคิลคือ ถ้า เอ(เอฟ){\displaystyle A(f)}หมายถึงจำนวนเต็มบวกn{\displaystyle n}ซึ่งφ(n)=เอฟ{\displaystyle \varphi (n)=f}, แล้วเอ(เอฟ){\displaystyle A(f)}ไม่สามารถเท่ากับ 1 ได้เลย ในทำนองเดียวกันวาคลาฟ เซียร์ปินสกีตั้งข้อสันนิษฐานว่า จำนวนเต็มบวกทุกจำนวนที่ไม่ใช่ 1 จะปรากฏเป็นค่าของเอ(เอฟ){\displaystyle A(f)}ซึ่งเป็นข้อสันนิษฐานที่ได้รับการพิสูจน์ในปี 1999 โดยเควิน ฟอร์ด[ 2 ]

หมายเหตุ

  • กาย, ริชาร์ด เค. (2004), ปัญหาที่ยังแก้ไม่ตกในทฤษฎีจำนวน (  ฉบับที่ 3), สปริงเกอร์-เวอร์แลก , B39, ISBN 978-0-387-20860-2, Zbl 1058.11001 .
  • Klee, VL Jr. (1947), "เกี่ยวกับสมมติฐานของ Carmichael", Bulletin of the American Mathematical Society , 53 (12): 1183– 1186, doi : 10.1090/S0002-9904-1947-08940-0 , MR 0022855 , Zbl 0035.02601  .
  • Pomerance, Carl (1974), "เกี่ยวกับสมมติฐานของ Carmichael" (PDF) , Proceedings of the American Mathematical Society , 43 (2): 297– 298, doi : 10.2307/2038881 , JSTOR 2038881 , Zbl 0254.10009  .
  • ซานดอร์, โยซเซฟ; Crstici, Borislav (2004), คู่มือทฤษฎีจำนวน II , Dordrecht: Kluwer Academic, หน้า228– 229, ISBN  978-1-4020-2546-4, Zbl 1079.11001 .
  • Schlafly, A.; Wagon, S. (1994), "สมมติฐานของ Carmichael เกี่ยวกับฟังก์ชัน Euler เป็นจริงต่ำกว่า 10 10,000,000 ", Mathematics of Computation , 63 (207): 415– 419, doi : 10.2307/2153585 , JSTOR 2153585 , MR 1226815 , Zbl 0801.11001   .
  • ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Carmichael%27s_totient_function_conjecture&oldid=1328820454 "

    สรุปเนื้อหา

    ข้อมูลสำคัญจากบทความ

    ข้อมูลสำคัญเกี่ยวกับ ข้อสันนิษฐานฟังก์ชันโทเทียนต์ของคาร์ไมเคิล

    ในทางคณิตศาสตร์ข้อสันนิษฐานเรื่องฟังก์ชันโทเทียนต์ของคาร์ไมเคิลเกี่ยวข้องกับความหลากหลายของค่าของฟังก์ชันโทเทียนต์ของออยเลอร์φ(n){\displaystyle \varphi

    ตัวอย่าง

    ฟังก์ชันโทเทียนต์ φ ( n ) {\displaystyle \varphi (n)} เท่ากับ 2 เมื่อ n {\displaystyle n} คือค่าใดค่าหนึ่งในสามค่า ได้แก่ 3, 4 และ 6 ดังนั้น ถ้าเราเลือกค่าใดค่าหนึ่งในสามค่านี้เป็น n {\displaystyle n} จากนั้นสามารถใช้ค่าใดค่าหนึ่งจากสองค่าที่เหลือเป็นค่าได้ ม...

    ขอบเขตล่าง

    มี ขอบเขตล่างที่ สูงมาก สำหรับข้อสันนิษฐานของคาร์ไมเคิล ซึ่งค่อนข้างง่ายต่อการกำหนด คาร์ไมเคิลเองได้พิสูจน์แล้วว่าตัวอย่างค้านใดๆ ต่อข้อสันนิษฐานของเขา (นั่นคือ ค่า) n {\displaystyle n} โดยที่ φ ( n ) {\displaystyle \varphi (n)} ค่า (ซึ่งแตกต่างจากค่า totient...

    ผลลัพธ์อื่นๆ

    ฟอร์ดพิสูจน์แล้วว่าหากมีตัวอย่างค้านต่อข้อสันนิษฐาน สัดส่วนบวก (ในแง่ของความหนาแน่นเชิงอะซิมโทติก) ของจำนวนเต็มก็ถือเป็นตัวอย่างค้านเช่นกัน [ 1 ]