โหนดและนกของตัวเลขสองตัว อัลกอริธึมแบบยุคลิด ตัวคูณร่วมน้อย (LCM)

หมายเลขที่สอง: ข=

ตัวคั่นหลักพันไม่มีตัวคั่นช่องว่าง "´

ผลลัพธ์:

ใหญ่ที่สุด ตัวหารร่วมจีซีดี( ก,ข)=6

ตัวคูณร่วมน้อยของ LCM( ก,ข)=468

ยิ่งใหญ่ที่สุด จำนวนธรรมชาติโดยที่ตัวเลข a และ b หารกันโดยไม่มีเศษ เรียกว่า ตัวหารร่วมมาก(GCD) ของตัวเลขเหล่านี้ เขียนแทนด้วย gcd(a,b), (a,b), gcd(a,b) หรือ hcf(a,b)

ตัวคูณร่วมน้อย LCM ของจำนวนเต็มสองตัว a และ b คือจำนวนธรรมชาติที่น้อยที่สุดที่หารด้วย a และ b ลงตัวโดยไม่มีเศษ แสดงว่า LCM(a,b) หรือ lcm(a,b)

เรียกจำนวนเต็ม a และ b สำคัญซึ่งกันและกันถ้าไม่มีตัวหารร่วมกันนอกจาก +1 และ −1

ตัวหารร่วมมาก

ให้สองอันเลย ตัวเลขบวก ก 1 และ ก 2 1) จำเป็นต้องค้นหาตัวหารร่วมของตัวเลขเหล่านี้ เช่น หาตัวเลขดังกล่าว λ ซึ่งแบ่งตัวเลข ก 1 และ ก 2 ในเวลาเดียวกัน มาอธิบายอัลกอริทึมกัน

1) ในบทความนี้ เราจะเข้าใจว่าคำว่า number เป็นจำนวนเต็ม

อนุญาต ก 1 ≥ ก 2 และปล่อยให้

ที่ไหน ม 1 , ก 3 เป็นจำนวนเต็มบางตัว ก 3 <ก 2 (ส่วนที่เหลือของดิวิชั่น ก 1 ต่อ ก 2 ควรน้อยกว่านี้ ก 2).

สมมุติว่า λ แบ่ง ก 1 และ ก 2 แล้ว λ แบ่ง ม 1 ก 2 และ λ แบ่ง ก 1 −ม 1 ก 2 =ก 3 (ข้อความที่ 2 ของบทความ “การหารของตัวเลข การทดสอบการหารลงตัว”) ตามมาด้วยตัวหารร่วมทุกตัว ก 1 และ ก 2 คือตัวหารร่วม ก 2 และ ก 3. สิ่งที่ตรงกันข้ามก็เป็นจริงเช่นกันหาก λ ตัวหารร่วม ก 2 และ ก 3 แล้ว ม 1 ก 2 และ ก 1 =ม 1 ก 2 +ก 3 ก็หารด้วย λ - ดังนั้นตัวหารร่วม ก 2 และ ก 3 เป็นตัวหารร่วมด้วย ก 1 และ ก 2. เพราะ ก 3 <ก 2 ≤ก 1 แล้วเราก็บอกได้ว่าคำตอบของโจทย์การหาตัวหารร่วมของตัวเลข ก 1 และ ก 2 ลดเหลือเป็นปัญหาที่ง่ายกว่าในการหาตัวหารร่วมของตัวเลข ก 2 และ ก 3 .

ถ้า ก 3 ≠0 เราก็หารได้ ก 2 บน ก 3. แล้ว

,

ที่ไหน ม 1 และ ก 4 เป็นจำนวนเต็มบางตัว ( กเหลืออีก 4 นัดจากดิวิชั่น ก 2 บน ก 3 (ก 4 <ก 3)). ด้วยเหตุผลเดียวกัน เราก็ได้ข้อสรุปว่าตัวหารร่วมของตัวเลข ก 3 และ ก 4 เกิดขึ้นพร้อมกับตัวหารร่วมของตัวเลข ก 2 และ ก 3 และยังมีตัวหารร่วมด้วย ก 1 และ ก 2. เพราะ ก 1 , ก 2 , ก 3 , ก 4, ... คือจำนวนที่ลดลงอย่างต่อเนื่อง และเนื่องจากมีจำนวนเต็มระหว่างจำนวนจำกัด ก 2 และ 0 จากนั้นในบางขั้นตอน n, ส่วนที่เหลือของการแบ่ง กไม่มี ก n+1 จะเท่ากับศูนย์ ( ก n+2 =0)

.

ตัวหารร่วมทุกตัว λ ตัวเลข ก 1 และ ก 2 เป็นตัวหารของตัวเลขด้วย ก 2 และ ก 3 , ก 3 และ ก 4 , .... กและ ก n+1 . บทสนทนาก็เป็นจริงเช่นกัน นั่นคือตัวหารร่วมของตัวเลข กและ ก n+1 ก็เป็นตัวหารของตัวเลขเช่นกัน ก n−1 และ กไม่ , .... , ก 2 และ ก 3 , ก 1 และ ก 2. แต่ตัวหารร่วมของตัวเลข กและ ก n+1 คือตัวเลข ก n+1 เพราะ กและ ก n+1 หารด้วย ก n+1 (จำไว้ว่า ก n+2 =0) เพราะฉะนั้น ก n+1 ก็เป็นตัวหารของตัวเลขเช่นกัน ก 1 และ ก 2 .

โปรดทราบว่าหมายเลข ก n+1 เป็นตัวหารที่มากที่สุดของตัวเลข กและ ก n+1 เนื่องจากตัวหารที่ยิ่งใหญ่ที่สุด ก n+1 คือตัวมันเอง ก n+1 . ถ้า ก n+1 สามารถแสดงเป็นผลคูณของจำนวนเต็มได้ จากนั้นตัวเลขเหล่านี้ก็เป็นตัวหารร่วมของตัวเลขเช่นกัน ก 1 และ ก 2. ตัวเลข กเรียกว่า n+1 ตัวหารร่วมมากตัวเลข ก 1 และ ก 2 .

ตัวเลข ก 1 และ ก 2 อาจเป็นจำนวนบวกหรือลบก็ได้ ถ้าตัวเลขตัวใดตัวหนึ่งมีค่าเท่ากับศูนย์ ตัวหารร่วมมากของตัวเลขเหล่านี้จะเท่ากับค่าสัมบูรณ์ของอีกจำนวนหนึ่ง ตัวหารร่วมมากที่สุดของจำนวนศูนย์นั้นไม่ได้ถูกกำหนดไว้

อัลกอริทึมข้างต้นเรียกว่า อัลกอริทึมแบบยุคลิดเพื่อหาตัวหารร่วมมากของจำนวนเต็มสองตัว

ตัวอย่างการหาตัวหารร่วมมากของตัวเลขสองตัว

ค้นหาตัวหารร่วมมากของตัวเลขสองตัว 630 และ 434

• ขั้นตอนที่ 1 หารตัวเลข 630 ด้วย 434 ส่วนที่เหลือคือ 196
• ขั้นตอนที่ 2 หารตัวเลข 434 ด้วย 196 ส่วนที่เหลือคือ 42
• ขั้นตอนที่ 3 หารตัวเลข 196 ด้วย 42 ส่วนที่เหลือคือ 28
• ขั้นตอนที่ 4 หารตัวเลข 42 ด้วย 28 ส่วนที่เหลือคือ 14
• ขั้นตอนที่ 5 หารตัวเลข 28 ด้วย 14 ส่วนที่เหลือคือ 0

ในขั้นตอนที่ 5 ส่วนที่เหลือของการหารคือ 0 ดังนั้น ตัวหารร่วมมากของตัวเลข 630 และ 434 จึงเป็น 14 โปรดทราบว่าตัวเลข 2 และ 7 ก็เป็นตัวหารของตัวเลข 630 และ 434 เช่นกัน

ตัวเลขโคไพรม์

คำนิยาม 1. ให้ตัวหารร่วมมากของตัวเลข ก 1 และ ก 2 เท่ากับหนึ่ง จากนั้นจึงเรียกหมายเลขเหล่านี้ หมายเลขโคไพรม์โดยไม่มีตัวหารร่วมกัน

ทฤษฎีบท 1. ถ้า ก 1 และ ก 2 หมายเลขโคไพรม์ และ λ ตัวเลขจำนวนหนึ่ง แล้วก็ตัวหารร่วมของตัวเลข แล 1 และ ก 2 เป็นตัวหารร่วมของตัวเลขด้วย λ และ ก 2 .

การพิสูจน์. พิจารณาอัลกอริทึมแบบยุคลิดในการค้นหาตัวหารร่วมมากของตัวเลข ก 1 และ ก 2 (ดูด้านบน)

.

จากเงื่อนไขของทฤษฎีบท จะได้ว่าตัวหารร่วมมากของจำนวนนั้นเป็นไปตามนั้น ก 1 และ ก 2 และดังนั้น กและ ก n+1 คือ 1 นั่นคือ ก n+1 = 1

ลองคูณความเท่าเทียมกันทั้งหมดนี้ด้วย λ , แล้ว

.

ให้ตัวหารร่วม ก 1 λ และ ก 2 ใช่ δ - แล้ว δ มาเป็นตัวคูณใน ก 1 λ , ม 1 ก 2 λ และใน ก 1 λ -ม 1 ก 2 λ =ก 3 λ (ดู "การหารตัวเลข" คำแถลง 2) ต่อไป δ มาเป็นตัวคูณใน ก 2 λ และ ม 2 ก 3 λ และดังนั้นจึงรวมเป็นปัจจัยใน ก 2 λ -ม 2 ก 3 λ =ก 4 λ .

เมื่อให้เหตุผลเช่นนี้ เราก็มั่นใจว่า δ มาเป็นตัวคูณใน ก n−1 λ และ ม n−1 ก n λ และด้วยเหตุนี้จึงเข้า ก n−1 λ −ม n−1 ก n λ =ก n+1 λ - เพราะ ก n+1 =1 แล้ว δ มาเป็นตัวคูณใน λ - ดังนั้นจำนวน δ เป็นตัวหารร่วมของตัวเลข λ และ ก 2 .

ให้เราพิจารณากรณีพิเศษของทฤษฎีบท 1

ผลที่ตามมา 1. อนุญาต กและ คจำนวนเฉพาะค่อนข้างมาก ข- แล้วผลิตภัณฑ์ของพวกเขา เครื่องปรับอากาศเป็นจำนวนเฉพาะเทียบกับ ข.

จริงหรือ. จากทฤษฎีบท 1 เครื่องปรับอากาศและ ขมีตัวหารร่วมเหมือนกันกับ คและ ข- แต่ตัวเลข คและ ขค่อนข้างง่าย เช่น มีตัวหารร่วมเพียงตัวเดียวคือ 1. แล้ว เครื่องปรับอากาศและ ขมีตัวหารร่วมร่วมตัวเดียวคือ 1 ดังนั้น เครื่องปรับอากาศและ ขเรียบง่ายซึ่งกันและกัน

ผลที่ตามมา 2. อนุญาต กและ ขตัวเลขโคไพรม์แล้วปล่อยให้ ขแบ่ง อาก้า- แล้ว ขแบ่งและ เค.

จริงหรือ. จากเงื่อนไขการอนุมัติ อาก้าและ ขมีตัวหารร่วมกัน ข- โดยอาศัยทฤษฎีบทที่ 1 ขจะต้องเป็นตัวหารร่วม ขและ เค- เพราะฉะนั้น ขแบ่ง เค.

ข้อพิสูจน์ที่ 1 สามารถสรุปได้

ผลที่ตามมา 3. 1. ให้ตัวเลข ก 1 , ก 2 , ก 3 , ..., ก m เป็นจำนวนเฉพาะสัมพันธ์กับจำนวน ข- แล้ว ก 1 ก 2 , ก 1 ก 2 · ก 3 , ..., ก 1 ก 2 ก 3 ··· ก m ผลคูณของจำนวนเหล่านี้เป็นจำนวนเฉพาะสัมพันธ์กับจำนวนนั้น ข.

2. ขอให้เรามีตัวเลขสองแถว

โดยให้ทุกจำนวนในชุดแรกเป็นจำนวนเฉพาะในอัตราส่วนของทุกจำนวนในชุดที่สอง แล้วสินค้า

คุณต้องค้นหาตัวเลขที่หารด้วยตัวเลขเหล่านี้แต่ละตัว

ถ้าจำนวนนั้นหารด้วย ก 1 ก็จะมีรูปแบบ ซา 1 ที่ไหน สหมายเลขบางอย่าง ถ้า ถามเป็นตัวหารร่วมมากของตัวเลข ก 1 และ ก 2 แล้ว

ที่ไหน ส 1 เป็นจำนวนเต็ม แล้ว

เป็น ผลคูณร่วมน้อยของตัวเลข ก 1 และ ก 2 .

ก 1 และ ก 2 ค่อนข้างเป็นจำนวนเฉพาะ จากนั้นก็เป็นตัวคูณร่วมน้อยของจำนวนนั้น ก 1 และ ก 2:

เราจำเป็นต้องหาตัวคูณร่วมน้อยของจำนวนเหล่านี้

จากที่กล่าวมาข้างต้นจะเป็นไปตามจำนวนทวีคูณใดๆ ก 1 , ก 2 , ก 3 ต้องเป็นจำนวนทวีคูณ ε และ ก 3 และกลับ. ให้ตัวคูณร่วมน้อยของตัวเลข ε และ ก 3 ใช่ ε 1. ต่อไปเป็นทวีคูณของตัวเลข ก 1 , ก 2 , ก 3 , ก 4 ต้องเป็นจำนวนทวีคูณ ε 1 และ ก 4. ให้ตัวคูณร่วมน้อยของตัวเลข ε 1 และ ก 4 ใช่ ε 2. ดังนั้นเราจึงพบว่ามีจำนวนทวีคูณทั้งหมด ก 1 , ก 2 , ก 3 ,...,ก m ตรงกับผลคูณของจำนวนหนึ่ง ε n ซึ่งเรียกว่าตัวคูณร่วมน้อยของจำนวนที่กำหนด

ในกรณีพิเศษเมื่อมีตัวเลข ก 1 , ก 2 , ก 3 ,...,ก m ค่อนข้างเป็นจำนวนเฉพาะ จากนั้นก็เป็นตัวคูณร่วมน้อยของจำนวนนั้น ก 1 , ก 2 ดังแสดงข้างต้น มีรูปแบบ (3) ต่อไปตั้งแต่ ก 3 ไพรม์สัมพันธ์กับตัวเลข ก 1 , ก 2 แล้ว ก 3 จำนวนเฉพาะ ก 1 · ก 2 (ข้อพิสูจน์ 1) หมายถึงตัวคูณร่วมน้อยของตัวเลข ก 1 ,ก 2 ,ก 3 เป็นตัวเลข ก 1 · ก 2 · ก 3. เมื่อพิจารณาในทำนองเดียวกัน เราก็ได้ข้อความต่อไปนี้

คำแถลง 1. ตัวคูณร่วมน้อยของจำนวนโคไพรม์ ก 1 , ก 2 , ก 3 ,...,ก m เท่ากับผลคูณของมัน ก 1 · ก 2 · ก 3 ··· กม.

คำแถลง 2. จำนวนใดๆ ที่หารด้วยจำนวนโคไพรม์แต่ละตัวลงตัว ก 1 , ก 2 , ก 3 ,...,ก m ก็หารด้วยผลคูณของมันได้เช่นกัน ก 1 · ก 2 · ก 3 ··· กม.

ลองพิจารณาแก้ไขปัญหาต่อไปนี้ ก้าวของเด็กชายคือ 75 ซม. และก้าวของเด็กหญิงคือ 60 ซม. จำเป็นต้องหาระยะทางที่น้อยที่สุดที่ทั้งคู่ก้าวเดินเป็นจำนวนเต็ม

สารละลาย.เส้นทางทั้งหมดที่พวกเขาจะผ่านไปจะต้องหารด้วย 60 และ 70 ลงตัว เนื่องจากพวกเขาแต่ละคนจะต้องเดินเป็นจำนวนเต็ม กล่าวอีกนัยหนึ่ง คำตอบต้องเป็นจำนวนทวีคูณของทั้ง 75 และ 60

ขั้นแรก เราจะเขียนผลคูณทั้งหมดของเลข 75 เราได้:

• 75, 150, 225, 300, 375, 450, 525, 600, 675, … .

ทีนี้ลองเขียนตัวเลขที่จะเป็นตัวคูณของ 60 กัน เราได้:

• 60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .

ตอนนี้เราพบตัวเลขที่อยู่ในทั้งสองแถวแล้ว

• ผลคูณร่วมของตัวเลขจะเป็น 300, 600 เป็นต้น

จำนวนที่น้อยที่สุดคือ 300 ในกรณีนี้จะเรียกว่าตัวคูณร่วมน้อยของตัวเลข 75 และ 60

เมื่อกลับไปสู่สภาพของปัญหา ระยะทางที่น้อยที่สุดที่ผู้ชายจะต้องเดินเป็นจำนวนเต็มคือ 300 ซม. เด็กชายจะครอบคลุมเส้นทางนี้ใน 4 ขั้นตอน และเด็กผู้หญิงจะต้องเดิน 5 ก้าว

การหาตัวคูณร่วมน้อย

• ผลคูณร่วมน้อยของจำนวนธรรมชาติสองตัว a และ b คือจำนวนธรรมชาติที่น้อยที่สุดที่เป็นจำนวนทวีคูณของทั้ง a และ b

เพื่อที่จะหาตัวคูณร่วมน้อยของตัวเลขสองตัวนั้น ไม่จำเป็นต้องจดจำนวนทวีคูณทั้งหมดของตัวเลขเหล่านี้ติดกัน

คุณสามารถใช้วิธีการต่อไปนี้

วิธีหาตัวคูณร่วมน้อย

ก่อนอื่น คุณต้องแยกตัวประกอบตัวเลขเหล่านี้เป็นตัวประกอบเฉพาะก่อน

• 60 = 2*2*3*5,
• 75=3*5*5.

ทีนี้ลองเขียนปัจจัยทั้งหมดที่อยู่ในส่วนขยายของตัวเลขแรก (2,2,3,5) และเพิ่มปัจจัยที่ขาดหายไปทั้งหมดจากการขยายตัวเลขที่สอง (5)

ผลลัพธ์ที่ได้คือชุดของจำนวนเฉพาะ: 2,2,3,5,5 ผลคูณของตัวเลขเหล่านี้จะเป็นตัวประกอบร่วมที่น้อยที่สุดสำหรับตัวเลขเหล่านี้ 2*2*3*5*5 = 300

รูปแบบทั่วไปสำหรับการค้นหาตัวคูณร่วมน้อย

• 1. แบ่งตัวเลขให้เป็นตัวประกอบเฉพาะ
• 2. เขียนปัจจัยเฉพาะที่เป็นส่วนหนึ่งของปัจจัยเหล่านั้น
• 3. เพิ่มปัจจัยเหล่านี้ทั้งหมดที่อยู่ในการขยายตัวของปัจจัยอื่น ๆ แต่ไม่ใช่ในปัจจัยที่เลือก
• 4. หาผลคูณของตัวประกอบทั้งหมดที่จดไว้

วิธีนี้เป็นสากล สามารถใช้ค้นหาตัวคูณร่วมน้อยของจำนวนธรรมชาติจำนวนเท่าใดก็ได้

เพื่อให้เข้าใจวิธีคำนวณ LCM คุณต้องกำหนดความหมายของคำว่า "หลายรายการ" ก่อน

ผลคูณของ A คือจำนวนธรรมชาติที่หารด้วย A ลงตัวโดยไม่มีเศษ ดังนั้น จำนวนที่เป็นทวีคูณของ 5 จึงถือเป็น 15, 20, 25 และอื่นๆ

ตัวหารของจำนวนเฉพาะอาจมีจำนวนจำกัด แต่ตัวคูณมีจำนวนไม่จำกัด

ผลคูณร่วมของจำนวนธรรมชาติคือจำนวนที่หารลงตัวได้โดยไม่เหลือเศษ

วิธีค้นหาตัวคูณร่วมน้อยของตัวเลข

ตัวคูณร่วมน้อย (LCM) ของตัวเลข (สอง สาม หรือมากกว่า) คือจำนวนธรรมชาติที่น้อยที่สุดที่หารด้วยจำนวนเหล่านี้ทั้งหมด

หากต้องการค้นหา LOC คุณสามารถใช้ได้หลายวิธี

สำหรับจำนวนน้อย จะสะดวกที่จะจดจำนวนทวีคูณของตัวเลขเหล่านี้ลงในบรรทัดจนกว่าคุณจะพบตัวที่เหมือนกัน หลายรายการแสดงด้วยอักษรตัวใหญ่ K

ตัวอย่างเช่น สามารถเขียนผลคูณของ 4 ได้ดังนี้:

เค (4) = (8,12, 16, 20, 24, ...)

เค (6) = (12, 18, 24, ...)

ดังนั้น คุณจะเห็นว่าตัวคูณร่วมน้อยของตัวเลข 4 และ 6 คือหมายเลข 24 สัญกรณ์นี้ทำได้ดังนี้:

ล.ซม.(4, 6) = 24

หากตัวเลขมีขนาดใหญ่ ให้ค้นหาผลคูณร่วมของตัวเลขสามตัวขึ้นไป ควรใช้วิธีอื่นในการคำนวณ LCM

เพื่อที่จะทำงานให้สำเร็จ คุณต้องแยกตัวประกอบตัวเลขที่กำหนดให้เป็นตัวประกอบเฉพาะ

ก่อนอื่นคุณต้องเขียนการสลายตัวของจำนวนที่ใหญ่ที่สุดในบรรทัดและที่เหลือ - ด้านล่าง

การสลายตัวของแต่ละตัวเลขอาจมีปัจจัยหลายประการที่แตกต่างกัน

ตัวอย่างเช่น ลองแยกตัวเลข 50 และ 20 ให้เป็นตัวประกอบเฉพาะ

ในการขยายจำนวนที่น้อยกว่า คุณควรเน้นปัจจัยที่ขาดหายไปในการขยายจำนวนที่มากที่สุดตัวแรก แล้วจึงบวกเข้าไป ในตัวอย่างที่นำเสนอ มีสองอันที่หายไป

ตอนนี้คุณสามารถคำนวณตัวคูณร่วมน้อยของ 20 และ 50 ได้แล้ว

ค.ศ.(20, 50) = 2 * 5 * 5 * 2 = 100

ดังนั้นผลคูณของตัวประกอบเฉพาะของจำนวนที่มากกว่าและตัวประกอบของจำนวนที่สองที่ไม่รวมอยู่ในการขยายของจำนวนที่มากกว่าจะเป็นตัวคูณร่วมน้อย

หากต้องการค้นหา LCM ของตัวเลขสามตัวขึ้นไป คุณควรแยกตัวประกอบทั้งหมดให้เป็นตัวประกอบเฉพาะ เช่นในกรณีก่อนหน้านี้

ตามตัวอย่าง คุณสามารถค้นหาตัวคูณร่วมน้อยของตัวเลข 16, 24, 36 ได้

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

ดังนั้น มีเพียงสองสองจากการขยายตัวของสิบหกเท่านั้นที่ไม่รวมอยู่ในการแยกตัวประกอบของจำนวนที่มากกว่า (หนึ่งอยู่ในการขยายตัวของยี่สิบสี่)

ดังนั้นจึงจำเป็นต้องเพิ่มเข้าไปในการขยายจำนวนที่มากขึ้น

ล.ซม.(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

มีกรณีพิเศษในการพิจารณาตัวคูณร่วมน้อย ดังนั้น หากตัวเลขตัวใดตัวหนึ่งสามารถหารด้วยอีกตัวหนึ่งโดยไม่มีเศษเหลือ จำนวนที่มากกว่านั้นก็จะเป็นตัวคูณร่วมน้อย

ตัวอย่างเช่น LCM ของสิบสองและยี่สิบสี่คือยี่สิบสี่

หากจำเป็นต้องค้นหาตัวคูณร่วมน้อยของจำนวนโคไพรม์ที่ไม่มีตัวหารเหมือนกัน LCM จะเท่ากับผลคูณของจำนวนนั้น

ตัวอย่างเช่น LCM (10, 11) = 110

แต่จำนวนธรรมชาติจำนวนมากก็หารด้วยจำนวนธรรมชาติอื่นๆ ด้วยเช่นกัน

ตัวอย่างเช่น:

จำนวน 12 หารด้วย 1, 2, 3, 4, 6, 12 ลงตัว;

เลข 36 หารด้วย 1, 2, 3, 4, 6, 12, 18, 36 ลงตัว

ตัวเลขที่จำนวนหารด้วยจำนวนเต็มลงตัว (สำหรับ 12 ได้แก่ 1, 2, 3, 4, 6 และ 12) เรียกว่า ตัวหารของตัวเลข- ตัวหารของจำนวนธรรมชาติ ก- เป็นจำนวนธรรมชาติที่หารจำนวนที่กำหนด กไร้ร่องรอย เรียกว่าจำนวนธรรมชาติที่มีตัวหารมากกว่าสองตัว คอมโพสิต .

โปรดทราบว่าตัวเลข 12 และ 36 มีตัวประกอบร่วมกัน ตัวเลขเหล่านี้ได้แก่ 1, 2, 3, 4, 6, 12 ตัวหารที่ยิ่งใหญ่ที่สุดของตัวเลขเหล่านี้คือ 12 ตัวหารร่วมของตัวเลขสองตัวนี้ กและ ข- คือจำนวนที่ใช้หารตัวเลขที่ให้มาทั้งสองจำนวนโดยไม่มีเศษเหลือ กและ ข.

ทวีคูณทั่วไปตัวเลขหลายตัวคือตัวเลขที่หารด้วยตัวเลขเหล่านี้แต่ละตัว ตัวอย่างเช่นตัวเลข 9, 18 และ 45 มีผลคูณร่วมของ 180 แต่ 90 และ 360 ก็เป็นตัวคูณร่วมเช่นกัน ในบรรดาตัวคูณร่วมทั้งหมด จะมีตัวคูณที่เล็กที่สุดเสมอ ในกรณีนี้คือ 90 เรียกว่าหมายเลขนี้ เล็กที่สุดตัวคูณร่วม (CMM).

LCM จะเป็นจำนวนธรรมชาติที่ต้องมากกว่าจำนวนที่ใหญ่ที่สุดของจำนวนที่กำหนดไว้เสมอ

ตัวคูณร่วมน้อย (LCM) คุณสมบัติ.

การสับเปลี่ยน:

การเชื่อมโยง:

โดยเฉพาะอย่างยิ่ง ถ้า และ เป็นจำนวนเฉพาะ ดังนั้น:

ตัวคูณร่วมน้อยของจำนวนเต็มสองตัว มและ nเป็นตัวหารของตัวคูณร่วมอื่นๆ ทั้งหมด มและ n- นอกจากนี้ เซตของตัวคูณร่วม มเกิดขึ้นพร้อมกับเซตทวีคูณของ LCM( ม).

เส้นกำกับสำหรับสามารถแสดงในรูปของฟังก์ชันเชิงทฤษฎีจำนวนบางตัวได้

ดังนั้น, ฟังก์ชันเชบีเชฟ- และยัง:

ตามมาจากคำจำกัดความและคุณสมบัติของฟังก์ชัน Landau กรัม(n).

สิ่งที่ตามมาจากกฎการกระจายตัวของจำนวนเฉพาะ

การหาตัวคูณร่วมน้อย (LCM)

NOC( ก, ข) สามารถคำนวณได้หลายวิธี:

1. หากทราบตัวหารร่วมที่ยิ่งใหญ่ที่สุด คุณสามารถใช้การเชื่อมโยงกับ LCM ได้:

2. ปล่อยให้การสลายตัวตามบัญญัติของตัวเลขทั้งสองเป็นตัวประกอบเฉพาะ:

ที่ไหน หน้า 1 ,...,หน้า- จำนวนเฉพาะต่างๆ และ วัน 1 ,...,งและ อี 1 ,...,เช่น เค— จำนวนเต็มที่ไม่เป็นลบ (สามารถเป็นศูนย์ได้ถ้าจำนวนเฉพาะที่สอดคล้องกันไม่อยู่ในส่วนขยาย)

จากนั้น NOC ( ก,ข) คำนวณโดยสูตร:

กล่าวอีกนัยหนึ่ง การสลายตัวของ LCM ประกอบด้วยปัจจัยเฉพาะทั้งหมดที่รวมอยู่ในการสลายตัวของตัวเลขอย่างน้อยหนึ่งรายการ ก, ขและใช้เลขชี้กำลังที่ใหญ่ที่สุดจากสองตัวคูณของตัวคูณนี้

ตัวอย่าง:

การคำนวณตัวคูณร่วมน้อยของตัวเลขหลายตัวสามารถลดลงเป็นการคำนวณ LCM ของตัวเลขสองตัวตามลำดับได้หลายรายการ:

กฎ.หากต้องการค้นหา LCM ของชุดตัวเลข คุณต้องมี:

- แยกตัวเลขออกเป็นปัจจัยเฉพาะ

- ถ่ายโอนการสลายตัวที่ใหญ่ที่สุด (ผลคูณของตัวประกอบของจำนวนที่มากที่สุดของตัวที่กำหนด) ไปยังปัจจัยของผลิตภัณฑ์ที่ต้องการแล้วบวกปัจจัยจากการสลายตัวของตัวเลขอื่น ๆ ที่ไม่ปรากฏในตัวเลขแรกหรือปรากฏในนั้น น้อยลง;

— ผลคูณผลลัพธ์ของตัวประกอบเฉพาะจะเป็น LCM ของตัวเลขที่กำหนด

จำนวนธรรมชาติตั้งแต่สองตัวขึ้นไปจะมี LCM ของตัวเอง ถ้าตัวเลขไม่ทวีคูณกันหรือไม่มีตัวประกอบเหมือนกันในการขยาย LCM จะเท่ากับผลคูณของตัวเลขเหล่านี้

ตัวประกอบเฉพาะของจำนวน 28 (2, 2, 7) จะถูกเสริมด้วยตัวประกอบของ 3 (จำนวน 21) ผลคูณที่ได้ (84) จะเป็นจำนวนที่น้อยที่สุดที่หารด้วย 21 และ 28 ลงตัว

ตัวประกอบเฉพาะของจำนวนที่มากที่สุด 30 จะถูกเสริมด้วยตัวประกอบ 5 ของจำนวน 25 ผลลัพธ์ที่ได้ 150 จะมากกว่าจำนวนที่ใหญ่ที่สุด 30 และหารด้วยจำนวนที่กำหนดทั้งหมดโดยไม่มีเศษเหลือ นี่คือผลคูณที่เล็กที่สุดที่เป็นไปได้ (150, 250, 300...) ซึ่งเป็นผลคูณของตัวเลขที่ระบุทั้งหมด

ตัวเลข 2,3,11,37 เป็นจำนวนเฉพาะ ดังนั้น LCM ของพวกมันจึงเท่ากับผลคูณของตัวเลขที่กำหนด

กฎ- ในการคำนวณ LCM ของจำนวนเฉพาะ คุณต้องคูณตัวเลขเหล่านี้ทั้งหมดเข้าด้วยกัน

ตัวเลือกอื่น:

หากต้องการค้นหาตัวคูณร่วมน้อย (LCM) ของตัวเลขหลายตัว คุณต้องมี:

1) แทนแต่ละตัวเลขเป็นผลคูณของตัวประกอบเฉพาะ ตัวอย่างเช่น

504 = 2 2 2 3 3 7,

2) เขียนกำลังของตัวประกอบเฉพาะทั้งหมด:

504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,

3) เขียนตัวหารเฉพาะ (ตัวคูณ) ของแต่ละตัวเลขเหล่านี้

4) เลือกระดับที่ยิ่งใหญ่ที่สุดของแต่ละอันซึ่งพบได้ในการขยายตัวเลขเหล่านี้ทั้งหมด

5) คูณพลังเหล่านี้

ตัวอย่าง- ค้นหา LCM ของตัวเลข: 168, 180 และ 3024

สารละลาย- 168 = 2 2 2 3 7 = 2 3 3 1 7 1,

180 = 2 2 3 3 5 = 2 2 3 2 5 1,

3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1.

เราเขียนกำลังที่ยิ่งใหญ่ที่สุดของตัวหารเฉพาะทั้งหมดแล้วคูณมัน:

NOC = 2 4 3 3 5 1 7 1 = 15120

คำนิยาม.เรียกจำนวนธรรมชาติที่ใหญ่ที่สุดโดยการนำตัวเลข a และ b มาหารกันโดยไม่มีเศษเหลือ ตัวหารร่วมมาก (GCD)ตัวเลขเหล่านี้

ลองหาตัวหารร่วมมากของตัวเลข 24 และ 35 กัน
ตัวหารของ 24 คือตัวเลข 1, 2, 3, 4, 6, 8, 12, 24 และตัวหารของ 35 คือตัวเลข 1, 5, 7, 35
เราจะเห็นว่าตัวเลข 24 และ 35 มีตัวหารร่วมเพียงตัวเดียวคือหมายเลข 1 ตัวเลขดังกล่าวเรียกว่า สำคัญซึ่งกันและกัน.

คำนิยาม.เรียกว่าจำนวนธรรมชาติ สำคัญซึ่งกันและกันถ้าตัวหารร่วมมาก (GCD) คือ 1

ตัวหารร่วมมาก (GCD)สามารถพบได้โดยไม่ต้องเขียนตัวหารทั้งหมดของตัวเลขที่กำหนด

แยกตัวประกอบตัวเลข 48 และ 36 เราจะได้:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
จากปัจจัยต่างๆ ที่รวมอยู่ในการขยายตัวเลขตัวแรก เราจะขีดฆ่าปัจจัยที่ไม่รวมอยู่ในการขยายตัวเลขตัวที่สอง (เช่น สองสอง)
ตัวประกอบที่เหลือคือ 2 * 2 * 3 ผลคูณคือ 12 จำนวนนี้คือตัวหารร่วมมากของตัวเลข 48 และ 36 นอกจากนี้ยังพบตัวหารร่วมมากของตัวเลขสามตัวขึ้นไปด้วย

เพื่อค้นหา ตัวหารร่วมมาก

2) จากปัจจัยที่รวมอยู่ในการขยายของตัวเลขใดจำนวนหนึ่งเหล่านี้ ให้ขีดฆ่าปัจจัยที่ไม่รวมอยู่ในการขยายของตัวเลขอื่น
3) ค้นหาผลคูณของปัจจัยที่เหลือ

หากตัวเลขที่กำหนดทั้งหมดหารด้วยหนึ่งในนั้นลงตัว แสดงว่าจำนวนนี้คือ ตัวหารร่วมมากตัวเลขที่กำหนด
ตัวอย่างเช่น ตัวหารร่วมที่ยิ่งใหญ่ที่สุดของตัวเลข 15, 45, 75 และ 180 คือเลข 15 เนื่องจากตัวเลขอื่นๆ ทั้งหมดหารด้วยตัวมันเองได้: 45, 75 และ 180

ตัวคูณร่วมน้อย (LCM)

คำนิยาม. ตัวคูณร่วมน้อย (LCM)จำนวนธรรมชาติ a และ b คือจำนวนธรรมชาติที่น้อยที่สุดซึ่งเป็นผลคูณของทั้ง a และ b ตัวคูณร่วมน้อย (LCM) ของตัวเลข 75 และ 60 สามารถหาได้โดยไม่ต้องจดจำนวนทวีคูณของตัวเลขเหล่านี้ติดกัน เมื่อต้องการทำเช่นนี้ ให้แยกตัวประกอบ 75 และ 60 เป็นตัวประกอบเฉพาะ: 75 = 3 * 5 * 5 และ 60 = 2 * 2 * 3 * 5
ลองเขียนปัจจัยที่รวมอยู่ในการขยายตัวเลขตัวแรกและเพิ่มปัจจัยที่หายไป 2 และ 2 จากการขยายตัวเลขที่สอง (เช่น เรารวมปัจจัยต่างๆ เข้าด้วยกัน)
เราได้ห้าปัจจัย 2 * 2 * 3 * 5 * 5 ซึ่งผลคูณคือ 300 จำนวนนี้เป็นตัวคูณร่วมน้อยของตัวเลข 75 และ 60

นอกจากนี้ยังค้นหาตัวคูณร่วมน้อยของตัวเลขสามตัวขึ้นไปด้วย

ถึง หาตัวคูณร่วมน้อยคุณต้องการจำนวนธรรมชาติหลายจำนวน:
1) แยกปัจจัยเหล่านั้นออกเป็นปัจจัยเฉพาะ
2) เขียนปัจจัยที่รวมอยู่ในการขยายตัวเลขตัวใดตัวหนึ่ง
3) เพิ่มปัจจัยที่ขาดหายไปจากการขยายตัวเลขที่เหลือ
4) ค้นหาผลคูณของปัจจัยผลลัพธ์

โปรดทราบว่าหากตัวเลขตัวใดตัวหนึ่งหารด้วยตัวเลขอื่นๆ ทั้งหมด ตัวเลขนี้จะเป็นตัวคูณร่วมน้อยของตัวเลขเหล่านี้
ตัวอย่างเช่น ตัวคูณร่วมน้อยของตัวเลข 12, 15, 20 และ 60 คือ 60 เพราะหารด้วยตัวเลขเหล่านั้นทั้งหมด

พีทาโกรัส (ศตวรรษที่ 6 ก่อนคริสต์ศักราช) และนักเรียนของเขาศึกษาคำถามเรื่องการหารตัวเลขลงตัว พวกเขาเรียกตัวเลขที่เท่ากับผลรวมของตัวหารทั้งหมด (โดยไม่มีตัวตัวเลขเอง) ว่าเป็นจำนวนสมบูรณ์ ตัวอย่างเช่น ตัวเลข 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) นั้นสมบูรณ์แบบ จำนวนสมบูรณ์ถัดไปคือ 496, 8128, 33,550,336 ชาวพีทาโกรัสรู้เพียงเลขสมบูรณ์สามตัวแรกเท่านั้น ที่สี่ - 8128 - กลายเป็นที่รู้จักในศตวรรษที่ 1 n. จ. ที่ห้า - 33,550,336 - ถูกค้นพบในศตวรรษที่ 15 ภายในปี 1983 ตัวเลขสมบูรณ์ 27 ตัวเป็นที่รู้จักแล้ว แต่นักวิทยาศาสตร์ยังไม่ทราบว่ามีจำนวนสมบูรณ์คี่หรือมีจำนวนสมบูรณ์มากที่สุดหรือไม่
ความสนใจของนักคณิตศาสตร์โบราณในเรื่องจำนวนเฉพาะนั้นเกิดจากการที่จำนวนใดๆ ที่เป็นจำนวนเฉพาะหรือสามารถแสดงเป็นผลคูณของจำนวนเฉพาะได้ กล่าวคือ จำนวนเฉพาะเป็นเหมือนก้อนอิฐที่ใช้สร้างจำนวนธรรมชาติที่เหลือ
คุณอาจสังเกตเห็นว่าจำนวนเฉพาะในชุดของจำนวนธรรมชาติเกิดขึ้นไม่เท่ากัน ในบางส่วนของอนุกรมจะมีมากกว่า บางส่วนมีน้อยกว่า แต่ยิ่งเราเลื่อนไปตามชุดตัวเลขมากขึ้นเท่าใด จำนวนเฉพาะที่พบได้น้อยก็จะยิ่งมากขึ้นเท่านั้น คำถามเกิดขึ้น: มีจำนวนเฉพาะตัวสุดท้าย (ใหญ่ที่สุด) หรือไม่? ยูคลิด นักคณิตศาสตร์ชาวกรีกโบราณ (ศตวรรษที่ 3 ก่อนคริสต์ศักราช) ในหนังสือของเขาเรื่อง “องค์ประกอบ” ซึ่งเป็นตำราคณิตศาสตร์หลักมาเป็นเวลาสองพันปี ได้พิสูจน์ว่ามีจำนวนเฉพาะจำนวนอนันต์ กล่าวคือ ด้านหลังจำนวนเฉพาะทุกตัวจะมีจำนวนเฉพาะที่มากกว่านั้นอีก ตัวเลข.
ในการค้นหาจำนวนเฉพาะ เอราทอสเธเนส นักคณิตศาสตร์ชาวกรีกอีกคนหนึ่งในยุคเดียวกันได้คิดวิธีนี้ขึ้นมา เขาจดตัวเลขทั้งหมดตั้งแต่ 1 ถึงจำนวนใดจำนวนหนึ่ง แล้วขีดฆ่าตัวหนึ่งซึ่งไม่ใช่จำนวนเฉพาะหรือจำนวนประกอบ แล้วขีดฆ่าตัวเลขทั้งหมดที่ตามหลัง 2 ออกไป (จำนวนที่เป็นทวีคูณของ 2 เช่น 4, 6 , 8 ฯลฯ) ตัวเลขตัวแรกที่เหลือหลังจาก 2 คือ 3 จากนั้น หลังจากสอง ตัวเลขทั้งหมดที่ตามมาหลัง 3 (ตัวเลขที่เป็นทวีคูณของ 3 เช่น 6, 9, 12 เป็นต้น) จะถูกขีดฆ่าออก ท้ายที่สุดแล้วมีเพียงจำนวนเฉพาะเท่านั้นที่ยังคงไม่ถูกข้าม