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

อ่าน 8 นาที

จำนวนเต็มที่ไม่มีตัวหารร่วมที่เท่ากัน

ใน ทฤษฎีจำนวน จำนวนเต็ม สอง จำนวน a และ b เป็น จำนวน เฉพาะ สัมพัทธ์ หรือ จำนวนเฉพาะซึ่งกันและกัน หากจำนวนเต็มบวกเพียงจำนวนเดียวที่เป็น ตัวหาร ของทั้งสองจำนวนนั้นคือ 1 [ 1 ]...

จำนวนเต็มที่ไม่มีตัวหารร่วมที่เท่ากัน

ในทฤษฎีจำนวน จำนวนเต็ม สองจำนวนaและbเป็นจำนวนเฉพาะสัมพัทธ์หรือจำนวนเฉพาะซึ่งกันและกันหากจำนวนเต็มบวกเพียงจำนวนเดียวที่เป็นตัวหารของทั้งสองจำนวนนั้นคือ 1 [ 1 ]ดังนั้นจำนวนเฉพาะ ใดๆ ที่หารa ลงตัว จะไม่หารb ลงตัว และในทางกลับกัน นี่เทียบเท่ากับตัวหารร่วมมาก (GCD) ของทั้งสองจำนวนนั้นคือ 1 [ 2 ]นอกจากนี้ยังกล่าวได้ว่าa เป็นจำนวนเฉพาะของbหรือa เป็นจำนวนเฉพาะสัมพัทธ์ กับ b

เลข 8 และ 9 เป็นจำนวนเฉพาะสัมพัทธ์กัน แม้ว่าเมื่อพิจารณาแยกกันแล้ว ทั้งสองเลขจะไม่ใช่จำนวนเฉพาะก็ตาม เนื่องจาก 1 เป็นตัวหารร่วมเพียงตัวเดียวของทั้งสองเลข ในทางกลับกัน 6 และ 9 ไม่ใช่จำนวนเฉพาะสัมพัทธ์กัน เพราะทั้งสองเลขหารด้วย 3 ลงตัว โดยนิยามแล้ว ตัวเศษและตัวส่วนของเศษส่วนอย่างง่ายจะเป็นจำนวนเฉพาะสัมพัทธ์กัน

สัญลักษณ์และการทดสอบ

เมื่อจำนวนเต็มaและbเป็นจำนวนเฉพาะสัมพัทธ์ วิธีมาตรฐานในการแสดงข้อเท็จจริงนี้ในสัญลักษณ์ทางคณิตศาสตร์คือการระบุว่าตัวหารร่วมมากที่สุดของพวกมันคือหนึ่ง โดยใช้สูตรgcd( a , b ) = 1หรือ( a , b ) = 1ในตำราConcrete Mathematics ปี 1989 ของพวกเขา Ronald Graham , Donald KnuthและOren Patashnikได้เสนอสัญลักษณ์ทางเลือกเพื่อระบุว่าaและb เป็นจำนวนเฉพาะสัมพัทธ์ กันและให้ใช้คำว่า "จำนวนเฉพาะ" แทนคำว่าจำนวนเฉพาะสัมพัทธ์ (เช่นaเป็นจำนวนเฉพาะของb ) [ 3 ]

วิธีที่รวดเร็วในการตรวจสอบว่าจำนวนสองจำนวนเป็นจำนวนเฉพาะสัมพัทธ์หรือไม่นั้น สามารถใช้ขั้นตอนวิธีของยุคลิดและรูปแบบที่เร็วกว่า เช่นขั้นตอนวิธีหารร่วมมากแบบไบนารีหรือขั้นตอนวิธีหารร่วมมากของเลห์เมอร์ได้

จำนวนของจำนวนเต็มที่เป็นจำนวนเฉพาะสัมพัทธ์กับจำนวนเต็มบวกnซึ่ง อยู่ระหว่าง 1 และnจะแสดงด้วยฟังก์ชันโทเทียนต์ของออยเลอร์หรือที่รู้จักกันในชื่อฟังก์ชันฟีของออยเลอร์φ ( n )

เซตของจำนวนเต็มอาจเรียกว่าเป็นจำนวนเฉพาะสัมพัทธ์ได้ ถ้าสมาชิกในเซตนั้นไม่มีตัวประกอบร่วมที่เป็นบวกใดๆ นอกจาก 1 เงื่อนไขที่เข้มงวดกว่าสำหรับเซตของจำนวนเต็มคือ จำนวนเฉพาะสัมพัทธ์แบบคู่ ซึ่งหมายความว่าa และ b เป็นจำนวนเฉพาะสัมพัทธ์กันสำหรับทุกคู่( a , b )ของจำนวนเต็มที่แตกต่างกันในเซต เซต{2, 3, 4}เป็นจำนวนเฉพาะสัมพัทธ์ แต่ไม่ใช่จำนวนเฉพาะสัมพัทธ์แบบคู่ เนื่องจาก 2 และ 4 ไม่ใช่จำนวนเฉพาะสัมพัทธ์กัน

คุณสมบัติ

เลข 1 และ -1 เป็นจำนวนเต็มเพียงสองจำนวนเท่านั้นที่เป็นจำนวนเฉพาะสัมพัทธ์กับจำนวนเต็มทุกจำนวน และเป็นจำนวนเต็มเพียงสองจำนวนเท่านั้นที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 0

มีหลายเงื่อนไขที่เทียบเท่ากับการที่aและbเป็นจำนวนเฉพาะสัมพัทธ์:

ผลที่ตามมาของประเด็นที่สามคือ ถ้าaและbเป็นจำนวนเฉพาะสัมพัทธ์ และbrbs (mod a )แล้วrs (mod a ) [ 5 ]นั่นคือ เราสามารถ "หารด้วยb " เมื่อทำงานแบบโมดูลัสa ยิ่งไปกว่า นั้นถ้าb 1 , b 2เป็นจำนวนเฉพาะสัมพัทธ์กับa ทั้งคู่ ผลคูณของพวกมัน b 1 b 2ก็เป็นจำนวนเฉพาะสัมพัทธ์กับ a เช่นกัน(กล่าวคือ โมดูลัสaเป็นผลคูณขององค์ประกอบที่ผกผันได้ และดังนั้นจึงผกผันได้) [ 6 ]สิ่งนี้ยังเป็นผลมาจากประเด็นแรกโดยทฤษฎีบทของยูคลิดซึ่งระบุว่า ถ้าจำนวนเฉพาะpหารผลคูณbcแล้วp จะหารตัวประกอบ b, cอย่าง น้อยหนึ่งตัว

จากข้อแรก ถ้าaและbเป็นจำนวนเฉพาะสัมพัทธ์แล้ว กำลังใดๆ ของa kและb m ก็เป็นจำนวนเฉพาะสัมพัทธ์เช่น กัน

ถ้าaและbเป็นจำนวนเฉพาะสัมพัทธ์ และaหารผลคูณbc ลงตัว แล้วaจะหารcลงตัว[ 7 ]สิ่งนี้สามารถมองได้ว่าเป็นการขยายความของทฤษฎีบทของยูคลิด

รูปที่ 1. ตัวเลข 4 และ 9 เป็นจำนวนเฉพาะสัมพัทธ์ ดังนั้น เส้นทแยงมุมของตาราง 4 × 9 จึงไม่ตัดกับจุดอื่นใดในตาราง

จำนวนเต็มaและbเป็นจำนวนเฉพาะสัมพัทธ์ก็ต่อเมื่อจุดที่มีพิกัด( a , b )ในระบบพิกัดคาร์ทีเซียนนั้น "มองเห็นได้" ผ่านเส้นตรงที่ไม่มีสิ่งกีดขวางจากจุดกำเนิด(0, 0)ในความหมายที่ว่าไม่มีจุดใดที่มีพิกัดเป็นจำนวนเต็มอยู่บนส่วนของเส้นตรงระหว่างจุดกำเนิดและ( a , b ) (ดูรูปที่ 1)

ในแง่ที่สามารถระบุได้อย่างแม่นยำความน่าจะเป็นที่จำนวนเต็มสองจำนวนที่สุ่มเลือกมาจะเป็นจำนวนเฉพาะสัมพัทธ์คือ6/ π²ซึ่งประมาณ 61% (ดูหัวข้อ§ความน่าจะเป็นของจำนวนเฉพาะสัมพัทธ์ด้านล่าง)

จำนวนธรรมชาติ สอง จำนวน aและbเป็นจำนวนเฉพาะสัมพัทธ์ก็ต่อเมื่อจำนวน2a 1และ2b 1เป็นจำนวนเฉพาะสัมพัทธ์[ 8 ] เป็นการสรุปทั่วไปของเรื่องนี้ ซึ่งได้มาจาก ขั้นตอนวิธีของยุคลิดในฐานn > 1ได้อย่างง่ายดาย:

ความเป็นจำนวนเฉพาะร่วมในเซต

เซตของจำนวนเต็มอาจเรียกว่าเป็นจำนวนเฉพาะสัมพัทธ์หรือจำนวนเฉพาะสัมพัทธ์แบบเซตได้ถ้าตัวหารร่วมมากที่สุดของสมาชิกทั้งหมดในเซตนั้นคือ 1 ตัวอย่างเช่น จำนวนเต็ม 6, 10, 15 เป็นจำนวนเฉพาะสัมพัทธ์ เพราะ 1 เป็นจำนวนเต็มบวกเพียงจำนวนเดียวที่หารจำนวนเหล่านี้ลงตัว

ถ้าจำนวนเต็มทุกคู่ในเซตเป็นจำนวนเฉพาะสัมพัทธ์กัน เซตนั้นจะเรียกว่าเป็นเซตเฉพาะสัมพัทธ์แบบเป็นคู่ (หรือจำนวนเฉพาะสัมพัทธ์แบบเป็น คู่ หรือจำนวนเฉพาะสัมพัทธ์แบบร่วมกัน ) เงื่อนไขความเป็นจำนวนเฉพาะสัมพัทธ์แบบเป็นคู่มีความเข้มงวดกว่าความเป็นจำนวนเฉพาะสัมพัทธ์แบบทั้งเซต กล่าวคือ เซตจำกัดที่เป็นจำนวนเฉพาะสัมพัทธ์แบบเป็นคู่ทุกเซตก็จะเป็นจำนวนเฉพาะสัมพัทธ์แบบทั้งเซตด้วย แต่ในทางกลับกันนั้นไม่เป็นจริง ตัวอย่างเช่น จำนวนเต็ม 4, 5, 6 เป็นจำนวนเฉพาะสัมพัทธ์แบบทั้งเซต (เพราะจำนวนเต็มบวกเพียงจำนวนเดียวที่หารทั้ง สามจำนวนลงตัว คือ 1) แต่ไม่ใช่ จำนวนเฉพาะสัมพัทธ์ แบบเป็นคู่ (เพราะห.ร.ม. ของ 4, 6 = 2 )

แนวคิดเรื่องจำนวนเฉพาะคู่กันมีความสำคัญในฐานะสมมติฐานในผลลัพธ์หลายอย่างในทฤษฎีจำนวน เช่นทฤษฎีบทเศษเหลือของจีน

เป็นไปได้ที่เซตของจำนวนเต็มอนันต์จะเป็นจำนวนเฉพาะสัมพัทธ์กันเป็นคู่ๆ ตัวอย่างที่โดดเด่น ได้แก่ เซตของจำนวนเฉพาะทั้งหมด เซตของสมาชิกในลำดับของซิลเวสเตอร์และเซตของจำนวนแฟร์มาต์ทั้งหมด

ความน่าจะเป็นของจำนวนเฉพาะร่วม

เมื่อกำหนดจำนวนเต็มสองจำนวน คือ aและb ที่สุ่มเลือกมา การถามว่าโอกาสที่aและb จะเป็นจำนวนเฉพาะสัมพัทธ์กันนั้นมีมากน้อยเพียงใด ในการพิจารณานี้ การใช้คุณสมบัติที่ว่า aและbเป็นจำนวนเฉพาะสัมพัทธ์กันก็ต่อเมื่อไม่มีจำนวนเฉพาะใดหารทั้งสองจำนวนลงตัวนั้นสะดวกกว่า (ดู ทฤษฎีบทพื้นฐานทางเลขคณิต )

โดยทั่วไป ความน่าจะเป็นที่จำนวนใดๆ จะหารลงตัวด้วยจำนวนเฉพาะ (หรือจำนวนเต็มใดๆ) pคือ⁠ ⁠ตัวอย่างเช่น จำนวนเต็มลำดับที่ 7 ทุกจำนวนจะหารลงตัวด้วย 7 ดังนั้น ความน่าจะเป็นที่จำนวนสองจำนวนจะหารลงตัวด้วยp ทั้งคู่ คือ⁠ ⁠และความน่าจะเป็นที่อย่างน้อยหนึ่งจำนวนไม่หารลงตัวคือ⁠ ⁠ ชุดเหตุการณ์การหารลงตัวใดๆ ที่เกี่ยวข้องกับจำนวนเฉพาะที่แตกต่างกันจะเป็นอิสระต่อกัน ตัวอย่างเช่น ในกรณีที่มีสองเหตุการณ์ จำนวนหนึ่งจะหารลงตัวด้วยจำนวนเฉพาะpและqก็ต่อเมื่อมันหารลงตัวด้วยpq เท่านั้น เหตุการณ์หลังมีความน่าจะเป็น⁠ ⁠ หากเราตั้งสมมติฐานแบบฮิวริสติกว่าการให้เหตุผลดังกล่าวสามารถขยายไปยังเหตุการณ์การหารลงตัวจำนวนอนันต์ได้ เราจะเดาได้ว่าความน่าจะเป็นที่จำนวนสองจำนวนเป็นจำนวนเฉพาะสัมพัทธ์นั้นกำหนดโดยผลคูณของจำนวนเฉพาะทั้งหมด

ในที่นี้ζหมายถึงฟังก์ชันซีตาของรีมันน์เอกลักษณ์ที่เชื่อมโยงผลคูณเหนือจำนวนเฉพาะกับζ (2)เป็นตัวอย่างของผลคูณออยเลอร์และการประเมินค่าของζ (2)เป็นπ 2 /6คือปัญหาบาเซิล ซึ่ง เลออนฮาร์ด ออยเลอร์ได้แก้ไขในปี 1735

ไม่มีวิธีใดที่จะเลือกจำนวนเต็มบวกแบบสุ่มเพื่อให้จำนวนเต็มบวกแต่ละจำนวนเกิดขึ้นด้วยความน่าจะเป็นเท่ากัน แต่ข้อความเกี่ยวกับ "จำนวนเต็มที่เลือกแบบสุ่ม" เช่นที่กล่าวมาข้างต้น สามารถทำให้เป็นทางการได้โดยใช้แนวคิดของความหนาแน่นตามธรรมชาติ สำหรับจำนวนเต็มบวก Nแต่ละจำนวนให้P Nเป็นความน่าจะเป็นที่จำนวนสองจำนวนที่เลือกแบบสุ่มใน N เป็นจำนวนเฉพาะสัมพัทธ์ แม้ว่าP Nจะไม่เท่ากับ6/ π/ 2อย่างแน่นอน แต่ด้วยงาน[ a ] เราสามารถแสดง ได้ ว่าในลิมิตเมื่อความน่าจะ เป็น P Nเข้าใกล้6/ π/ 2

โดยทั่วไปแล้ว ความน่าจะเป็นที่ จำนวนเต็ม kที่เลือกแบบสุ่มจะเป็นจำนวนเฉพาะร่วมกันในแต่ละเซตคือ⁠ ⁠ [ 9 ]

การสร้างคู่จำนวนเฉพาะสัมพัทธ์ทั้งหมด

ต้นไม้มีรากอยู่ที่ (2, 1) ราก (2, 1) ถูกทำเครื่องหมายด้วยสีแดง ลูกทั้งสามของมันแสดงด้วยสีส้ม รุ่นที่สามเป็นสีเหลือง และเป็นเช่นนี้ต่อไปตามลำดับสีรุ้ง

จำนวนเฉพาะสัมพัทธ์บวกทุกคู่( m , n ) (โดยที่m > n ) สามารถจัดเรียงเป็นต้นไม้ไตรภาค สมบูรณ์ที่ไม่ทับซ้อนกันสองต้น โดยต้นหนึ่งเริ่มต้นจาก(2, 1) (สำหรับคู่เลขคู่-เลขคี่และเลขคี่-เลขคู่) [ 10 ]และอีกต้นหนึ่งเริ่มต้นจาก(3, 1) (สำหรับคู่เลขคี่-เลขคี่) [ 11 ]ลูกของแต่ละจุดยอด( m , n )จะถูกสร้างขึ้นดังนี้:

  • สาขาที่ 1:
  • สาขาที่ 2:
  • สาขาที่ 3:

แผนการนี้ครอบคลุมทุกด้านและไม่มีส่วนที่ซ้ำซ้อน โดยไม่มีสมาชิกที่ไม่ถูกต้อง สามารถพิสูจน์ได้โดยการสังเกตว่า ถ้าเป็นคู่จำนวนเฉพาะสัมพัทธ์กับแล้ว

  • ถ้าเช่นนั้น เป็นบุตรของสาขาที่ 3
  • ถ้าเช่นนั้นเป็นลูกของสาขาที่ 2
  • ถ้าเช่นนั้นจะเป็นลูกของสาขาที่ 1

ในทุกกรณีคู่จำนวนเฉพาะสัมพัทธ์ที่ "เล็กกว่า" จะมีกระบวนการ "คำนวณหาพ่อ" ซึ่งจะหยุดได้ก็ต่อเมื่อหรือในกรณีเหล่านี้ ความเป็นจำนวนเฉพาะสัมพัทธ์ หมายความว่าคู่ดังกล่าวเป็นหรือ

อีกวิธีหนึ่ง (ที่ง่ายกว่ามาก) ในการสร้างต้นไม้ของคู่จำนวนเฉพาะสัมพัทธ์บวก( m , n ) (โดยที่m > n ) คือการใช้ตัวสร้างสองตัวคือ และโดยเริ่มจากรากต้นไม้ไบนารีที่ได้ ซึ่งเรียกว่าต้นไม้ Calkin–Wilfนั้นครอบคลุมทุกคู่จำนวนเฉพาะสัมพัทธ์และไม่ซ้ำซ้อน ซึ่งสามารถอธิบายได้ดังนี้ เมื่อกำหนดคู่จำนวนเฉพาะสัมพัทธ์แล้ว เราจะใช้หรือ ซ้ำๆ โดย ขึ้นอยู่กับว่าวิธีใดให้คู่จำนวนเฉพาะสัมพัทธ์บวกที่มีm > nเนื่องจากมีเพียงวิธีเดียวเท่านั้นที่ให้ผลลัพธ์เช่นนั้น ต้นไม้จึงไม่ซ้ำซ้อน และเนื่องจากด้วยกระบวนการนี้ เราจะไปถึงรากอย่างแน่นอน ต้นไม้จึงครอบคลุมทุกคู่จำนวนเฉพาะสัมพัทธ์

แอปพลิเคชัน

ในการออกแบบเครื่องจักร การสึกหรอ ของเฟือง ที่สม่ำเสมอและเป็นเนื้อเดียวกัน นั้น สามารถทำได้โดยการเลือกจำนวนฟันของเฟืองสองตัวที่ขบกันให้มีจำนวนฟันที่สัมพันธ์กันเป็นจำนวนฟันหลัก (prime) เมื่อ ต้องการ อัตราทดเกียร์ 1:1 อาจใส่เฟืองที่มีจำนวนฟันสัมพันธ์กันเป็นจำนวนฟันหลัก (prime) เข้าไประหว่างเฟืองสองตัวที่มีขนาดเท่ากันนั้น

ใน การเข้ารหัสลับก่อนยุคคอมพิวเตอร์ เครื่อง เข้ารหัส Vernamบางเครื่องรวมลูปเทปกุญแจที่มีความยาวต่างกันหลายลูปเข้าด้วยกันเครื่องโรเตอร์ หลายเครื่อง รวมโรเตอร์ที่มีจำนวนฟันต่างกัน การรวมกันแบบนี้จะได้ผลดีที่สุดเมื่อความยาวทั้งหมดเป็นจำนวนเฉพาะสัมพัทธ์กันเป็นคู่ๆ[ 12 ] [ 13 ] [ 14 ] [ 15 ]

การสรุปโดยทั่วไป

แนวคิดนี้สามารถขยายไปใช้กับโครงสร้างพีชคณิตอื่นๆ ได้นอกเหนือจากนั้นตัวอย่างเช่นพหุนามที่มีตัวหารร่วมมากที่สุดคือ 1 เรียกว่าพหุนามเฉพาะสัมพัทธ์

ความเป็นจำนวนเฉพาะร่วมในไอเดียลวงแหวน

ไอเดียล สอง ตัว AและBในวงแหวนสลับที่Rเรียกว่าเป็นไอเดียลเฉพาะตัว (หรือไอเดียลสูงสุดร่วม ) ถ้านี่เป็นการขยายความเอกลักษณ์ของเบซูต์ : ด้วยนิยามนี้ไอเดียลหลัก สองตัว ( a ) และ ( b ) ในวงแหวนของจำนวนเต็มจะเป็นไอเดียลเฉพาะตัวก็ต่อเมื่อa และ b เป็นไอเดียลเฉพาะตัว นอกจากนี้ ถ้าไอเดียลAและBของRเป็นไอเดียลเฉพาะตัวแล้ว ถ้าCเป็นไอเดียลที่สามซึ่งAประกอบด้วยBCแล้วAจะประกอบด้วยCทฤษฎีบทเศษเหลือของจีนสามารถขยายความไปยังวงแหวนสลับที่ใดๆ ได้โดยใช้ไอเดียลเฉพาะตัว

ดูเพิ่มเติม

หมายเหตุ

  1. ^ทฤษฎีบทนี้ได้รับการพิสูจน์โดย Ernesto Cesàroในปี 1881 สำหรับรายละเอียดการพิสูจน์ โปรดดู Hardy & Wright 2008ทฤษฎีบทที่ 332

เอกสารอ้างอิง

อ่านเพิ่มเติม

  • ลอร์ด, นิค (มีนาคม 2551), "การสร้างลำดับจำนวนเฉพาะร่วมอนันต์แบบเอกรูป", Mathematical Gazette , 92 : 66–70.
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Coprime_integers&oldid=1358743500 "

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ จำนวนเต็มที่ไม่มีตัวหารร่วมที่เท่ากัน

ใน ทฤษฎีจำนวน จำนวนเต็ม สอง จำนวน a และ b เป็น จำนวน เฉพาะ สัมพัทธ์ หรือ จำนวนเฉพาะซึ่งกันและกัน หากจำนวนเต็มบวกเพียงจำนวนเดียวที่เป็น ตัวหาร ของทั้งสองจำนวนนั้นคือ 1 [ 1 ]...

สัญลักษณ์และการทดสอบ

เมื่อจำนวนเต็ม a และ b เป็นจำนวนเฉพาะสัมพัทธ์ วิธีมาตรฐานในการแสดงข้อเท็จจริงนี้ใน สัญลักษณ์ทางคณิตศาสตร์ คือการระบุว่าตัวหารร่วมมากที่สุดของพวกมันคือหนึ่ง โดยใช้สูตร gcd( a , b ) = 1 หรือ ( a , b ) = 1 ในตำรา Concrete Mathematics ปี 1989 ของพวกเขา Ronald...

คุณสมบัติ

เลข 1 และ -1 เป็นจำนวนเต็มเพียงสองจำนวนเท่านั้นที่เป็นจำนวนเฉพาะสัมพัทธ์กับจำนวนเต็มทุกจำนวน และเป็นจำนวนเต็มเพียงสองจำนวนเท่านั้นที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 0

ความเป็นจำนวนเฉพาะร่วมในเซต

เซตของจำนวนเต็มอาจเรียกว่าเป็น จำนวนเฉพาะสัมพัทธ์ หรือ จำนวนเฉพาะสัมพัทธ์แบบเซตได้ ถ้า ตัวหารร่วมมาก ที่สุด ของสมาชิกทั้งหมดในเซตนั้นคือ 1 ตัวอย่างเช่น จำนวนเต็ม 6, 10, 15 เป็นจำนวนเฉพาะสัมพัทธ์ เพราะ 1 เป็นจำนวนเต็มบวกเพียงจำนวนเดียวที่หารจำนวนเหล่านี้ลงตัว...