ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบยุคลิด"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล แก้หมายเหตุ |
เพิ่มข้อมูล |
||
บรรทัด 17:
เมื่อ[[ส่วนขยายของขั้นตอนวิธีแบบยุคลิด|ย้อนขั้นตอนวิธีแบบยุคลิด]] ตัวหารร่วมมากสามารถเขียนในรูป[[ผลรวมเชิงเส้น]]ของสองจำนวนที่นำมาดำเนินการ แต่ละจำนวนคูณกับ[[จำนวนเต็ม]] เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ{{nowrap|21 {{=}} [5 × 105] + [(−2) × 252]}} สมบัตินี้เรียกว่า[[เอกลักษณ์ของเบซู]]
==พื้นฐาน — ตัวหารร่วมมาก==
{{main|ตัวหารร่วมมาก}}
ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของ[[จำนวนธรรมชาติ]]สองจำนวน ''a'' และ ''b'' ค่าตัวหารร่วมมาก ''g'' เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง ''a'' และ ''b'' ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ '''ตัวประกอบร่วมค่ามากสุด'' ({{lang-en|greatest common factor,GCF}})''''', '''ตัวประกอบร่วมค่ามากสุด''({{lang-en|highest common factor,HCF}})''''' และ '''''greatest common measure''''' (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย หรม.(''a'', ''b'') หรือ (''a'', ''b''),<ref>{{Harvnb|Stark|1978|p=16}}</ref> แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น [[เวกเตอร์พิกัด]]สองมิติ
ถ้า หรม.(''a'', ''b'') = 1 แล้ว ''a'' กับ ''b'' เป็น[[จำนวนเฉพาะสัมพัทธ์]]<ref>{{Harvnb|Stark|1978|p=21}}</ref> ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า ''a'' หรือ ''b'' เป็น[[จำนวนเฉพาะ]]เองแต่อย่างใด<ref>{{Harvnb|LeVeque|1996|p=32}}</ref> เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน
| |||